2018 Beaver Computing Challenge
(Grade 5 & 6)
Questions, Answers, Explanations, and Connections
2018 Beaver Computing Challenge
(Grade 5 & 6)
Questions, Answers, Explanations, and Connections
Joni Beaver uses rope to mark groups of trees. The rope forms a very tight loop so that each tree either touches the rope or is entirely inside the loop. Below is an example where the rope touches exactly 5 trees when viewed from above.
How many trees will the rope touch if the trees are arranged as follows (when viewed from above)?
(C) 6
We can count the trees touching the rope in the picture below.
This problem is known as finding the convex hull of a set of points. One way to define this is the polygon with the smallest area which contains all the points in the set. The word convex means extending outward or curving out, and any two points within a convex shape, when drawn on paper, can be connected with a straight line which is inside of the shape. The word hull here is used to describe the “shell" or “encasement", as in the hull of a ship or the hull of a seed, such as corn.
Finding the convex hull of a set of points is very useful:
Canada
Beavers play a simple game. The game always begins with this starting position:
From this starting position, rotation instructions are followed. All the rotations are clockwise and one quarter of a complete turn. The possible instructions are:
For example, if the first instruction is 2R, the top-left square will be Yellow as shown below.
From the starting position, what colours will the top-left square be after each of the instructions 1R, 2R, 2R, and 3R are followed in order?
(B) Red Blue Green Blue Red
The top-left square is Red for the starting position and the results after each rotation are shown below.
This problem involves following a series of steps and keeping track of the current state. The state could be what the current orientation looks like, or only what is in the top-left corner (which can be used to determine the position of the other three colours). The ordered sequence of instructions is an algorithm. The ability to execute algorithms and remember state is the defining property of a computer.
This problem also involves simplifying and applying reasoning, since a rotation by two 2R rotations, or 1R plus 3R rotations (for a total of 4R rotations) will yield the game in the same orientation as it started.
Canada
Consider these five statements describing the three robots below:
Bob and Moe are smiling.
Bob, Moe, and Lea each have two legs.
Moe has a round head and exactly one leg.
All three robots have five fingers.
Lea or Bob have their hands raised.
Which of these five statements are true?
2 and 3
1 and 3
1 and 5
None
(C) 1 and 5
We can see that all the robots are smiling so Statement 1 is true. Since Bob’s hands are raised, Statement 5 is true. Notice that Statements 2 is not true because Lea only has one leg. Statement 3 is not true because Moe has two legs. Finally, Statement 4 is not true because Moe has less than five fingers. (Lea also has less than five fingers.)
In computer science, boolean data has two values usually named true and false. These values are at the heart of logic. Many decisions in an algorithm are based on logic and boolean data.
Notice that the sentence “Bob and Moe are smiling" is true in this problem since both of Moe and Bob are smiling. Notice as well that this statement does not depend in any way on Lea. Being able to focus on the important information of a problem is a key concept in computational thinking. This process is sometimes called abstraction, which is where the most important details are focused on and irrelevant details are ignored in order to make solving the problem easier.
Latvia
Flora asked for three rows of flowers to be planted. These rows can be seen below:
However, Flora had asked that the white flower 
be closer to the fence than the blue flower 
in each row.
Which rows were planted according to what Flora asked for?
Only Row 1
Rows 1 and 2
Rows 1 and 3
All three rows
(C) Rows 1 and 3
When we examine each row then we can see that in rows 1 and 3, the white flower was planted located closer to the fence than the blue flower. In row 2, the blue flower is closer to the fence than the white flower.
This task focuses on understanding rules and logical reasoning. When specifications of problems are given to computer scientists, an important part of the software design process is to gather requirements for the software. For example, a client may ask that the output of the program be in a particular order, or that only certain pieces of data should be analyzed. It is worth spending time to understand and record specification and requirements because it decreases the chance of costly bugs or reprogramming.
Slovakia
Mark goes to a birthday party. A room at the party is decorated with balloons in rows:
Mark can’t see colours clearly. For him, yellow (C) looks the same as green (A), and blue (D) looks the same as red (B).
Which two rows of balloons look the same to Mark?
(D) Row 1 and Row 3
If we write out the symbols we get:
Then we substitute each C with A because these look the same to Mark:
We also substitute each D with B because these look the same to Mark:
Now, we can easily see that Row 1 and Row 3 look the same to Mark.
Lists of objects are one of the simplest data structures. Computer scientists use data structures to organize data so that common tasks involving the data can be performed efficiently.
A very common task involving lists is to simply compare them. To compare lists of the same length, you have to compare the corresponding objects in each list. When computer scientists write programs to compare complicated objects, such as newspaper stories or photographs of people, some differences have to be ignored, and some different things have to be treated as “the same.” In this task, we are given lists of balloons and two simple rules for what “the same” means. Ignoring irrelevant differences and looking for common elements is the process of abstraction, which computer scientists use to write algorithms that work on a variety of inputs.
Ireland
Beavers take part in an annual challenge. Starting from rock number 0, they jump clockwise from rock to rock. For example, if a beaver jumps 8 times, it ends up on rock number 3:
0 \(\rightarrow\) 1 \(\rightarrow\) 2 \(\rightarrow\) 3 \(\rightarrow\) 4 \(\rightarrow\) 0 \(\rightarrow\) 1 \(\rightarrow\) 2 \(\rightarrow\) 3
One of the beavers showed off and jumped an astonishing 129 times. On which rock did it end up?
(A) 4
If a beaver jumps 5 times, it ends up where it starts. Let’s call it a “lap". Since \(129 = 25 \times 5 + 4\), the beaver will do 25 laps and have 4 jumps left. In these last four jumps, the beaver goes from rock number 0 to rock number 4.
You may have seen this operation in math class before. It’s part of what you might know as Long Division or Euclidean division which calculates an integer quotient and a remainder.
In this case you’re asked to calculate the remainder of 129 when it is divided by 5. Since this operation is used very commonly in computers, it has a name: modulo operation. Usually “%" or “mod" is used as an operator. So, for our equation we could write: \(129\ \%\ 5 = 4\).
Typical applications of this operator are in programs containing loops (just like our beaver jumping in loops), and when variables overflow because they are too big. Modular arithmetic is also used heavily in cryptosystems, such as RSA cryptography, used to keep our passwords safe online.
Switzerland
James made 37 litres of lemonade at home and now he wants to bring it to a celebration at school. He has several empty bottles of various sizes but he wants to use the smallest number of them to bottle exactly 37 litres of lemonade.
He has one bottle of each of the following sizes:
What is the least number of bottles James needs to use?
(C) 3
James should use a 32-litre bottle, a 4-litre bottle and a 1-litre bottle. Notice that this is three bottles and \(32+4+1=37\).
There isn’t a 37-litre bottle so James must use more than one bottle. You can’t find two numbers (possibly the same) among the sizes \(1,2,4,8,16\) and \(32\) that add up to 37, so more than two sizes are needed. This means we know that three bottles is the least James can use.
The binary number system is central to computation and to computers. In the binary number system, there are only two digits: 0 and 1. Why? It is related to how the hardware in modern computers works. The key idea is that part of hardware can be “on” or “off" meaning it only has two possible states. All of this will change if and when quantum computers become commonplace in society.
The volume of the bottles keeps doubling in this task, just like the values of individual bits in a binary number. In computer science it is important to be able to convert numbers in one base (i.e., base ten) to another base (i.e., binary). When converting to binary, a simple trick is to select the largest bit that still fits in the number you are trying to convert.
United States
Every morning Maja decides what to wear for the day. She uses the following rules:
If she wears pants, then she wears a T-shirt that is blank or has stars.
If she wears a skirt, then she wears a T-shirt with a beaver logo.
If she wears a T-shirt that is blank or has stars, then she wears a jacket with a heart.
If she wears a jacket with a heart, then she wears a cap with a drawing.
Which of the following combinations can Maja wear?
(B)
Option B satisfies all four rules. Specifically, rule 1 does not apply because there are no pants in this combination, rule 2 is satisfied because the T-shirt in this combination has a beaver logo on it, rule 3 does not apply for the same reason, and rule 4 does apply because the jacket does not have a heart on it.
Option A violates rule 1. Option C violates rule 4. Option D violates rule 2.
In computer programming we often decide which actions have to be performed by checking some conditions. These actions often look like this:
“if" a special condition holds (e.g., a skirt has been chosen),
“then" some specific action is done (e.g., choose a T-shirt with a beaver logo).
Almost every programming language has a conditional statement or conditional expression, and these conditionals are used in almost every computer program.
Slovenia
Beavers live in a valley surrounded by mountains. In the valley, there is a lake. The lake is surrounded by fields with either trees or stones.
Every day, beavers flood all those fields with trees that are next to the lake or flooded fields. Fields with stones are not flooded.
For example, after one day, three fields will be flooded, as shown above.
After how many days in total will all the fields with trees be flooded?
4 days
5 days
6 days
7 days
(C) 6 days
Numbers in the picture below show flooded fields after the corresponding number of days.
Fields next to the lake are marked by 1. Then all unmarked fields with trees next to a field marked with 1 are marked with 2. This process is continued until all fields with trees are marked. Numbers in the picture below show on which day the field becomes flooded.
As we can see above, the last field with trees will be flooded after 6 days.
Computer scientists study different types of algorithms. An algorithm is a sequence of steps that solves a problem. This task demonstrates the wavefront algorithm which is used to scan an area divided into cells. You can think of this algorithm as taking a picture once per second when a stone is dropped in a still pool of water.
This scanning uses a breadth-first search (BFS) approach. A BFS algorithm begins at a cell called the root. Then, at each step, every cell next to previously visited cells (sometimes called the fringe) are visited. In this task, the cells correspond to fields and visiting a cell corresponds to flooding a field. When done carefully, BFS visits every cell in an area to be scanned exactly once. This is done in an organized way. In fact, as seen in the solution, cells can be numbered as they are visited. These numbers describe how far each cell is from the root. That is, BFS algorithms can be used to find the shortest paths from the root to all the other cells.
Lithuania
Sarah tries to throw five rings around a peg as part of a game. The following chart shows how points are earned each time a ring lands around the peg. Rings that do not land around the peg do not earn points.
| Toss | Points |
|---|---|
| First Toss | 5 |
| Second Toss | 4 |
| Third Toss | 3 |
| Fourth Toss | 2 |
| Fifth Toss | 1 |
The following picture illustrates the order in which Sarah threw her five rings. It also shows which ones landed around the peg and which ones did not land around the peg.
How many points did Sarah earn?
15
9
6
3
(C) 6
From the picture, we can determine which ring was tossed first, second, third, fourth and fifth. We can see that only the blue and green ring landed around the peg. All this is summarized in the table below.
| Toss | Ring | Landed Around Ring | Points |
|---|---|---|---|
| First Toss | Yellow | No | 0 |
| Second Toss | Blue | Yes | 4 |
| Third Toss | Pink | No | 0 |
| Fourth Toss | Green | Yes | 2 |
| Fifth Toss | Black | No | 0 |
| TOTAL | 6 | ||
The placement of the rings can be represented as a data structure known as a stack. A data structure is a way of organizing data to make certain operations (e.g. insertion, deletion, or retrieval) are as efficient as possible. A stack is based on the last-in first-out principle (LIFO). For example, if a ring were removed from the peg, the last one to be tossed would have to be removed first. Despite being a very simple idea, it is useful in many different situations, such as modelling subprograms can be called and returned from, how a stack of books can be reversed by moving the books one at a time, or finding your way through a maze.
Malaysia
Beavers play a word chain game. One beaver starts by saying a word. The other beaver must say a different word which begins with the last letter of the previous word. Then the first beaver says another word (which was not said yet) using this same rule, and so on. If a beaver is unable to say a new word, that beaver loses the game. These beavers do not know many words. In fact, they can draw their entire vocabulary like this:
Notice that an arrow out of a word points at the next possible word(s) that can be said.
What is the largest possible number of words that can be said in one game?
(C) 8
The beavers can use at most 8 words in one game. One example is:
lockjaw-wool-lumber-racquetball-log-gnaw-willow-wood
(Can you find another game of the same length?)
To be sure that 8 is the largest possible number of words, we have to convince ourselves that it is not possible to use all 9 words. Consider the words wood and wind. There is no word beginning with d, so if either of these words is said, it must be the last word of the game. Since there cannot be two words that are said last, it is not possible to use the entire vocabulary of 9 words.
In this problem, the drawing is a graph. We call the words vertices and we call the arrows edges. You are asked to find the length of the longest path in the graph.
Graphs appear almost anytime there are objects connected together in some way. Sometimes the vertices and edges actually look like the drawing in a graph. For example, we might think of a map where the vertices as cities and the edges as roads between the cities. Other times, the graph is more hidden as in this problem. Did you notice that all you need to solve this problem is the list of words themselves? You are probably glad that a picture was provided. This illustrates one way in which graphs are a powerful tool.
Finding the longest path in a graph is very well-studied. It is related to the famous Traveling Salesman Problem and other optimization problems problems involving paths which often appear in industrial problems.
Czech Republic
A beaver wants to build a dam to protect her house from a winter flood. She will use the log piles shown in the first figure (below on the left) to produce the dam shown in the second figure (below on the right). It takes 1 hour to move a pile of logs one square in a vertical direction on the figure, and 2 hours in a horizontal direction.
What is the minimum number of hours it will take to build the dam?
16
11
14
12
(D) 12
The figure above shows the solution which requires 12 hours to build the dam. This must be the best we can do if we only use vertical moves, but could we do better using some horizontal? Each horizontal move would have to save more than 2 vertical moves.
Notice that there is one pile in each “column". So if we move a pile horizontally, we would have to move another pile horizontally as well, in the opposite direction, to have one pile in each column again (or we would have to move the same pile back to its original column). You may also notice that every pile is located the same number of squares both vertically and horizontally from the river. This suggests that it will not help to make any horizontal moves.
To show conclusively that the proposed solution is the best we can do, we can use the last observation and examine each pile individually: for example, the fastest way to move the rightmost pile to any place on the river is to make two moves downwards. This is true for all piles: our solution moves each of them to a target position in the fastest possible way. There is no better way for any of the piles.
This task concerns optimization with constraints. Optimization is a problem frequently solved in computer science. Luckily, in the particular case presented in the task, the solution can be found and verified easily due to problem size, the positions of the piles, and difference in time required to move piles.
For example, if there were two piles in one column, one of them would certainly have to be moved horizontally, and finding the optimal solution would quickly become much more difficult. In general, searching for the optimal solution can take quite some time and require advanced techniques such as dynamic programming.
Turkey