2016 Beaver Computing Challenge
(Grade 9 & 10)
Questions, Answers, Explanations, and Connections
2016 Beaver Computing Challenge
(Grade 9 & 10)
Questions, Answers, Explanations, and Connections
Boxes are shown below. Each box is labeled with its mass in kilograms.
Xena the delivery beaver fills out a form to order boxes. For example, to order boxes totalling exactly 9 kilograms, she fills out the form as follows:
| ✓ | ✓ | |||
| 16 | 8 | 4 | 2 | 1 |
How should she fill out the form to order boxes totaling exactly 20 kilograms?
| ✓ | ✓ | ✓ | ||
| 16 | 8 | 4 | 2 | 1 |
| ✓ | ✓ | |||
| 16 | 8 | 4 | 2 | 1 |
| ✓ | ✓ | |||
| 16 | 8 | 4 | 2 | 1 |
| ✓ | ✓ | ✓ | ✓ | |
| 16 | 8 | 4 | 2 | 1 |
(C)
| ✓ | ✓ | |||
| 16 | 8 | 4 | 2 | 1 |
Only \(4 + 16 = 20\) from the possible choices.
Computers rely on binary numbers, which are base-2 numbers.
Since computers rely on electricity to operate, and electricity is most easily measured as either being “on” or “off”, we have two possible values we can keep track of: we use 0 to represent “off” and 1 to represent “on”. If we could keep track of two electrical components, then we could have four states:
Notice that we could write these more succinctly as 00, 11, 10 and 01.
For each component we add, we double the number of states. For example, to add another component, giving us three total, we would have each of the above state configurations with the third component off and each with the third component on giving a total of 8 states. In this manner, we can have 2, 4, 8, 16, \(\ldots\) possible states. All of these are powers of two.
Canada
Roberta Beaver has purchased an old computer that only allows one digit after the decimal point in any calculation. Anything after that digit is removed. Sometimes this results in an error which is the difference between the stored value and the exact value.
For example, if we try to compute \(\frac{7}{5}\) on Roberta’s machine, this will be stored as \(1.4\) which is the exact value of \(\frac{7}{5}\). This gives an error of 0. However, if we compute \(\frac{7}{4}\), this will be stored as \(1.7\) since \(\frac{7}{4}=1.75\) and “\(5\)” will be removed from the end. This gives an error of \(0.05\).
Extra digits are removed after every operation. For example, when Roberta computes \(\left({\frac{3}{2}}\right)\times\left(\frac{2}{3}\right)\), she computes \(\frac{3}{2}\) to give \(1.5\), then \(\frac{2}{3}\) to give \(0.6\), and then \(1.5 \times 0.6\) to give \(0.9\). This gives an error of \(0.1\).
If Roberta computes \(\left(\left(\frac{10}{3}\right)\times\left(\frac{10}{3}\right)\right)\times 9\), what is the error?
(C) 2.8
Notice that \((\frac{10}{3})\) will be stored as \(3.3\). Then \((\frac{10}{3})\times(\frac{10}{3}) = 3.3 \times 3.3\) will be stored as \(10.8\). Then \(10.8\times 9 = 97.2\) which will be stored as \(97.2\). However, the correct value is \((\frac{100}{9})\times 9 = 100\). This gives an error of \(100-97.2 = 2.8\).
Computers have a fixed amount of memory and can only store a finite amount of information. So when computer chips are designed, a minimum and maximum size is imposed on stored integers. Thus when fractions are placed in memory, not every digit can be stored which means round-off errors occur. These errors can accumulate and large calculations can become quite inaccurate.
Computer scientists study how to minimize the errors introduced in some algorithms in order to make the end results closer to the exact answer. Specifically, computer scientists store real numbers and fractions using floating-point numbers. A floating-point number is composed of two components: a fixed number of significant digits and an exponent. For example, the number 1.2345 might be stored with the significant digits 12345 and the exponent \(-4\), since \(12345 \times 10^{-4} = 1.2345\). Using floating-points allows mathematicians and computer scientists to develop numerically stable algorithms where errors do not propagate.
Canada
Beavers are preparing for a Food Festival. They would like to bake a cake but their baker is on vacation.
Keith decides to try to bake the cake. He remembers that it is important to add five essential ingredients in the correct order.
When he gets to the garden shown below, he finds a white piece of paper beside all but one ingredient. The paper shows which ingredient must be added next.
So, for example, a yellow five-petal flower must be added immediately after a pine cone. And, since there is no paper beside the strawberry, it must be added last.
Which ingredient must be added first?
(B)
If Keith starts with the red four-petal flower, he can add all five ingredients in the right order. He will add the red four-petal flower, then the apple, then the pine cone, then the yellow five-petal flower, then finally the strawberry. If he had started with the strawberry, he could not have continued to the next ingredient because there is no paper beside it. If he had started with the apple, he would have skipped the red four-petal flower. If he had started with the pine cone, he would have skipped the red four-petal flower and the apple.
Alternatively, you could start with the last ingredient, the strawberry, and work backwards. The ingredient before the strawberry must be the yellow five-petal flower since that has the paper with the strawberry beside it. The ingredient before the yellow five-petal flower must be the pine cone. The ingredient before the pine cone is the apple and the ingredient before the apple is the red four-petal flower.
Computer scientists have developed data structures which allow computers to store information in ways that are efficient for inserting, deleting and retrieving.
The data structure modelled here is called a linked list in which there can be an arbitrary number of items.
A linked list is a linear collection of data elements that consist of an item and a pointer indicating the next item in the linked list. The first item of the linked list, often called the head, is very important: the list starts from the head and it is the only point which allows access to every element in the list.
The recipe here is stored as a linked list. The ingredients are the items and each slip of paper is the pointer to the next item in the list. The head must be the ingredient which is not referred to by any paper, but is accompanied by a paper.
Hungary
The BeaverBall is a toy operated by remote control which can be used to move the toy in four possible directions:
The BeaverBall operates inside a tower with its initial position shown below.
If the BeaverBall moves to a white square, it drops down one level falling directly onto the square below. The BeaverBall ignores commands that cause it to move outside the tower.
Which of the following lists of directions will cause the BeaverBall to reach the GOAL?
(D) E, N, W, S, N, E, W
(A) The BeaverBall does not reach the bottom level (it cannot move in direction W and so ignores the final two W commands). Each square below represents a level of the tower. The topmost level is represented on the left. The BeaverBall starts on the bottom left square.
(B) The BeaverBall reaches the bottom level but ends on a square that is not the GOAL square.
(C) The BeaverBall reaches the bottom level but ends on a square that is not the GOAL square.
(D) The BeaverBall ends at the GOAL. So, this is the correct answer.
A computer program is a sequence of instructions from a set of possibilities. This task requires one to write a computer program in a very simple programming language that consists of only four possible commands N, S, E, W. This situation introduces one important element of many computer programming languages – sequential composition, which means following commands one after another in order.
Japan
Agents Boris and Bertha communicate using secret messages.
For example, Boris wants to communicate the following message to Bertha.
MEETBILLYBEAVERAT6
He writes each character in a 4 column grid from left-to-right and row-by-row starting from the top. He puts an X in any unused spaces in the bottom row. The result is shown below.
Then he creates the encrypted message by reading the characters from top-to-bottom and column-by-column starting from the left:
MBYVTEIBE6ELERXTLAAX
Bertha then uses the exact same method to reply to Boris. The encrypted message she sends to him is:
OIERKLTEILH!WBEX
What was the original message sent by Bertha? (It does not contain an X.)
B) OKIWILLBETHERE!
You can determine the original message by entering the encrypted message into the grid from top to bottom and column by column. This gives:
Then reading from left-to-right and row-by-row gives:
OKIWILLBETHERE!
We do not always want messages sent across networks to be read if they are intercepted. These messages might contain a password or other private information. Therefore, a message is sometimes encrypted. For this to work, the recipient needs to be able to decrypt this encrypted message and discover the original secret message. However, it should not be possible for an adversary who finds the encrypted message to also recover the original secret message.
The method to encrypt and decrypt is called a cipher. There are many types of ciphers. The one used in this task is called a transposition cipher as it rearranges the letters in the original message to create the secret message. The study of ciphers is called cryptography. Modern cryptography is a big area of research and involves more complicated ciphers based on hard mathematical problems.
United Kingdom
Beaver Bob’s friends have invited him to dinner in Beaver Town at 7:00 pm. He leaves his house (Beaver Bob’s house) at 10:00 am. Bob wants to buy a gift for his friends at the Beaver Market. He also needs to pick up his son Rob at Beaver School before he drives to Beaver Town. It does not matter whether he buys the gift or picks up his son first. Bob’s car currently has enough fuel left to drive for 4 hours so he also needs to visit the Gas Station to refuel his car. Once he refuels his car, he can drive for another 9 hours. The time in hours it takes to travel between locations is indicated on the map. Bob can arrive early at his friends’ place but he cannot be late.
Which route should Bob follow after leaving his house?
(C) Beaverlake \(\rightarrow\) Gas Station \(\rightarrow\) Beaver Tower \(\rightarrow\) Beaver Market \(\rightarrow\) Beaver Forest \(\rightarrow\) Beaver School \(\rightarrow\) Beaver Town
This route takes 8.4 hours so Bob arrives at 6:24 p.m. and will be in time for dinner.
You can walk through all the options to get to the correct answer. While doing so, you will notice that (B) does not visit the Gas Station at all and (D) would get to the Gas Station after 4.1 hours, so Bob will run out of gas before reaching the station.
After comparing (A) with (C), you will see that route (A) will take 10.9 hours, so Bob will be late. Only (C) will get Bob to the party on time.
The search for an optimal path is a typical optimization question in computer science. Dijkstra’s algorithm is a famous algorithm to find a shortest path from a starting point to an ending point through a network.
However in this case, there are two constraints: you have to be at a specific place in at most 4 hours and you have to be at the final place in a total of at most 9 hours. So to find the optimal route you would have to filter out all routes that do not satisfy these two constraints.
Switzerland
Leslie the Beaver must drag logs one at a time through the system of canals and stations shown below. The logs must be dragged through canals in the direction of the arrows. The number in each arrow is the maximum total number of logs that can ever be dragged through the corresponding canal.
What is the maximum number of logs that Leslie can drag from the start station to the terminal station?
(B) 5
Consider the following solution, where the first number on each arrow shows the number of logs that Leslie carries over each canal and the second number shows its maximum capacity:
We see that two logs can be dragged along the three top canals. Two other logs can be dragged along the bottom canals. A fourth log can be dragged along the first two bottom canals, then up a canal and finally to the terminal station. This shows that it is possible for Leslie to drag five logs. To see that this is an upper bound, notice the dashed line. Each log must be dragged across this line in order to reach the terminal station. So at most \(2+1+2=5\) total logs can reach the terminal station.
The problem of finding a maximum-flow in a network is common in computer science. A famous theorem (Ford-Fulkerson, 1956) says that the maximum flow (how many logs are dragged over canals) is given by the capacity of the minimum cut (dashed line), which if removed would disconnect the source (start station) from the sink (terminal station).
A common example is the Internet, where we want to move as much data as possible between routers. Other examples include image processing, airline scheduling, network reliability, and distributed computing. In most of these applications, and particularly for the Internet, solving this problem quickly is important since the Internet is composed of millions of such nodes, each with a capacity, so routing through routers in this network needs to be done as efficiently as possible.
Canada
Cindy wrote a computer program which can be used to paint a chain of squares and triangles.
The following instructions make the program draw single shapes:
There is also a repeat instruction \(N[I]\) where \(N\) is a number and \(I\) is a sequence of instructions. This command makes the program repeat the instruction sequence \(I\) exactly \(N\) times in a row.
For example, the instruction sequence s 2[T t] S makes the program paint this chain:
Which instruction sequence will make the program paint the following chain?
(C) S 3[t s T] t S
It’s easy to see that (A) and (B) are incorrect. A starts with a small square while the chain starts with a big square. The second figure from the end of (B) is a big triangle while the chain contains a small triangle at that position. The answers (C) and (D) only differ in the number of repetitions. The chain contains three copies of the shape sequence: small triangle, small square, big triangle. Therefore (D) (which repeats it only twice) is incorrect.
Another way to work out the answer is to paint down the chain created by each of the answers:
(A) makes the program paint this chain:
(B) makes the program paint this chain:
(C) makes the program paint the correct chain:
(D) makes the program paint this chain:
We then compare these chains with the chain that we want to create.
In this task small programs are written to paint chains. A program is a sequence of instructions. A computer executes the instructions in this sequence one by one. A program does exactly what you tell it to do, even if this is not what you actually wanted. A computer is not able to detect your programming mistake.
An instruction sequence that is part of a program, is called block. The “repeat instruction,” which can be used to execute a block several times, is usually called a loop. Most programming languages provide loops, conditionals (execution of instructions depending on certain conditions) and subroutines (instructions composed of other instructions).
Slovakia
Three robots work as a team in the warehouse shown below. The warehouse is a 6-by-6 grid.
When the team gets a direction symbol (N, S, E, or W), each robot moves one grid square in that direction at the same time.
After following a list of direction symbols, each robot picks up whatever object there might be in the same square as the robot. The robots do not pick up any other objects they encounter during their movements. The robots ignore movements that make them move outside the boundaries of the grid.
For example, if we give the list N, N, S, S, E to the team, then robot A will pick up a cone, robot B will pick up a ring, and robot C will pick up a cone.
What list can be sent to the team so that the team picks up exactly a sphere, a ring, and a cone?
(B) N, E, E, S, E
When robots or computers work together at the same time, we say that they are working in parallel.
If we have a small number of robots or computers working in parallel, we could give each of them a different list of instructions. However, if we have thousands or millions of computers working together then it is not practical to write separate instructions for each. We have to give large groups of them the exact same instructions. For example, the Tianhe-2 supercomputer has 3 million separate computing cores that can be used to work together on solving a single complicated problem.
In this task, we have the potential for an additional complication. The robots are working in the same space, and their instructions must be prepared more carefully to ensure that they do not crash into each other or otherwise block one another. Preparing parallel instructions in such a situation is an extremely challenging aspect of computer science called concurrent programming.
Ireland
The mayor of Beaverville is looking for volunteer firefighters. A map showing the possible volunteers’ homes and how they are connected by roads is shown below. He wants to ensure that every home in the town is either the home of a volunteer or is connected by a single road to the home of a volunteer.
What is the minimum number of volunteers the mayor needs?
(C) 3
There are two houses that have only one road leading from them. Since each of them needs to either be a firefighter or be next to a firefighter, we need to take one of Ann or Bob as well as one of Gus or Hal. Taking Bob and Hal is better since they are adjacent to more homes and there is no disadvantage to taking them. Notice that no matter what combination of the above is used: either Ann and Gus, Ann and Hal, Bob and Gus, or Bob and Hal, none of these cover every house and thus, we will need more than two houses. This means, if we can find a set that works for three houses, we will have found the minimum and we will be done.
After taking Bob and Hal, we see that only the homes of Eve and Fay are not yet connected by a single road to to the home of a volunteer firefighter. Taking one of Cid or Ian fixes this. Thus, this can be done by having volunteer firefighters in three homes: Bob, Hal and Cid. Note that there are multiple solutions to this problem and this is only one such solution.
The houses and roads here are analogies for vertices and edges of a graph. The problem given here is called the minimum dominating set problem, an important problem in computer science. Determining where to place cameras for security purposes and figuring out how many restaurants to place in a neighbourhood to service everyone are two examples of this type of problem.
This problem is one of Richard Karp’s 21 NP-Complete Problems, meaning this is a problem which we believe, in general, does not have an efficient solution. Even though the problem of determining the minimal dominating set might not be feasible, finding a set that is “small enough" might be okay in practice.
A slightly related problem is the edge covering problem. Instead of asking for volunteers at houses, we could have asked the question on which roads should we put firefighter outposts so that each house is adjacent to a road with an outpost and so that we minimize the number of outposts. This problem, while similar, can actually be solved quickly.
Canada
The famous Blue Diamond was stolen from a museum. A thief swapped it for a cheap green imitation diamond.
The day it was stolen, 2000 people entered the diamond room one by one. Inspector Bebro must find the thief by interviewing some of these people. He has a list of all 2000 people in the order they entered the room. The only question he can ask a person is:
Was the diamond green or blue when you saw it?
The thief will lie and say green but everyone else will tell the truth.
Inspector Bebro is very clever and will use a strategy where the number of people interviewed is as small as possible. Which of the following statements can he say truthfully?
A) I can guarantee that I will find the thief by interviewing at most 20 people.
Number the people from 1 to 2000 in the order they entered the room. Surprisingly, inspector Bebro only needs to interrogate a very small fraction of people, by repeatedly halving the list in the following manner.
In both cases, the number of visitors that can possibly be the thief is reduced from 2000 to 1000. In other words, it is halved.
Next inspector Bebro asks the question to the “middle" person in the remaining list (i.e., number 1500 in the first case, number 500 in the second case). This again will allow him to divide the number of suspects by two.
Continuing in the same way, he will be able to reduce the number of suspects to 500, 250, 125, 63, 32, 16, 8, 4 and ultimately 2. When left with two suspects, he should pose the question to the first one. If he or she answers green, he or she is the thief, otherwise the other suspect is the thief. Inspector Bebro will therefore find the thief after interviewing only 11 people.
The idea of repeatably halving a set in which you are searching for a distinguished object, is an algorithm that is very common in computer science. The best known example of this is binary search in which you search for a specific entry in an ordered list. In our case we use binary search to find the first green element in a list of blue and green elements where all blue elements come first by repeatedly checking which half of the list the object must be in and repeatedly halving the search. The fact that there is a thief that lies, is an interesting twist. Note that the problem is unsolvable if we do not know in advance if the thief will lie or not.
Theoretical computer scientists are very interested in understanding which problems are unsolvable and for those that are not, finding the best or optimal algorithm.
Belgium
A maple tree 
is surrounded by two oak trees
and two palm trees
as
follows:
Five types of bananas, P, Q, R, S, T, are placed in the trees with a different type in each tree. The monkey is hungry and takes the same amount of time to eat any banana. The monkey starts on a tree and begins by eating a banana. The monkey then swings to other trees and eats bananas on those trees. It takes the monkey
The monkey eats bananas of type P, Q, S, R, T, R, P in that order.
What types of bananas can possibly be in the maple tree if the total amount of time the monkey swings is as small as possible?
(B) P or S or T
The given sequence P, Q, S, R, T, R, P visits all the banana types, with six swings P-Q, Q-S, S-R, R-T, T-R, R-P. For this sequence of bananas, the monkey swings to each tree at least once and from each tree at least once. Since this includes the maple tree, and the monkey swings six times, it must swing for a total of at least \(4(2)+2(3)=14\) seconds.
The following arrangements of bananas show that this is possible if the maple tree is P, S or T:
 |
 |
 |
We can count in each case to check that the monkey will swing for a total of 14 seconds given each of the above arrangements.
The monkey swings to R twice and leaves R twice so if the banana in the maple tree is R, then the monkey will swing for at least \(2(2)+4(3)=16\) seconds.
If the banana in the maple tree is Q, then to obtain a total time of 14 seconds, the monkey must take two seconds to swing from each of S to R, R to T and R to P. This means that the bananas S, T and P are all palm trees or all oak trees which is impossible.
In summary, 14 seconds is the smallest possible number of seconds the monkey can swing and this can happen if and only if the banana in the middle tree is P, S or T.
This problem involves finding the best, or optimal, solution to a problem. Computers are often used to find the maximum or minimum value of some measurement. In this case, we might think of the trees as applications on a touch screen and the monkey swinging as the movement of a human finger from one application to another. A user interface designer might be interested in how to arrange the applications for a common sequence of operations so as to require as little time as possible.
Canada
A family of five beavers is moving into a new 4-level underground apartment that looks like the figure below. Each circle in the figure represents a space and each line represents a one-meter long tunnel.
The beavers want to choose spaces for their bedrooms. If a space is remodelled into a bedroom, all of the spaces in the lower levels connected to that bedroom can no longer be used.
Each beaver has their own daily routine and goes out of their bedroom several times a day.
If we want to minimize the total distance that all beavers travel in one day, at which level should Sarah’s bedroom be located?
(C) The 3rd level
Since we want to minimize the total distance all the beavers travel, the beaver that goes out most frequently should be as close to the top as possible.
You can rule out answers A and B as follows:
(A) is incorrect. If you assign a bedroom on the first floor, all other floors can’t be used anymore.
(B) is incorrect as well. If you assign a bedroom on the second floor, it has to go to Mommy because she travels the most. The other space on the second level must be empty, because there is more than one person who needs a bedroom.
Then, you have to decide if (C) or (D) is best. You want to place as many beavers as possible on the third floor, but you don’t have rooms enough for all of them. Two should be placed on the fourth floor, but that should be the beavers that travel the least, which in this case are Brian and Liam. This leaves Daddy, Mommy and Sarah on the third floor. If we put Sarah on the fourth floor, then one of Brian or Liam would have to go on the third floor which would result in more travel time than the configuration below.
M: Mommy; D: Daddy; S: Sarah; B: Brian; L: Liam
The task is similar to a text compression problem in computer science. The goal is to minimize the total length for encoded text, that is, the most frequent text should be encoded in the shortest code. To know how long the shortest code (route in this case) will be, computer scientists often use the Huffman Coding Algorithm to determine a solution. First, we sort the five beavers by their travel frequency in descending order. Then we merge the two beavers with the smallest frequencies and create a new node (room) with a frequency which is equal to their sum. Third, we repeat the second step until all beavers are merged. The diagram below shows the result of this process. We can determine what level Sarah’s room should be located by counting from the top node down to the node marked with the letter \(S\).
M: Mommy; D: Daddy; S: Sarah; B: Brian; L: Liam
Taiwan
Kiki and Wiwi are playing L-Game on a 4x4 board. The player who can no longer play a piece loses. They take turns placing L-shaped pieces one at a time with Kiki playing first so that
The diagram below illustrates a possible board after each player has placed a piece once.
Starting from an entirely empty board, how many of Kiki’s nine possible first moves guarantee that Kiki will win no matter what?
(B) 1
The correct answer is B. By placing a piece in the middle position, Kiki is guaranteed to win the game. No matter how Wiwi places a piece on his or her first turn, Kiki can only place a piece in the top left corner on her second turn. Then Wiwi cannot place a piece according to the rules. If Kiki places a piece in any other position on his/her first turn, then there is always at least one way that he/she can lose the game. The following diagram details some of the possibilities and symmetry can be used to rule out many of the positions.
All the possibilities in a game can be represented by a diagram like the one in the explanation above. In this game tree, a root node corresponds to the initial state of the board. Then, for each possible move, arrows point to the resulting new state of the board. The full tree is built by continuing in this way. A game tree is a special type of directed graph.
A game tree can be built and searched in order to play or study the game. Depending on the type of problem, it is sometimes more useful to explore neighbour nodes first before moving to neighbours on the next level (breadth-first search, or BFS), while sometimes it is more useful to explore as far as possible along each branch before backtracking (depth-first search, or DFS). These two search strategies have different advantages and computer memory requirements which can make one more beneficial than the other in certain situations. These searches were part of what Deep Blue used to play and beat Garry Kasparov in Chess in the 1990s.
Taiwan
Betaro Beaver discovered five types of magic potions with the following effects:
Betaro put each magic potion into a different cup and additionally put water into a sixth cup. Betaro labelled the cups A to F and forgot to record which cup contains which magic potion!
Betaro called Taki for help. She solved the problem by experimenting on three of their other friends:
Which one of the cups contains pure water?
(D) Cup D
Experiment 1 has three effects. Therefore, there is no pure water in Experiment 1. Experiment 2 and 3 both have two effects so the lone cup with pure water must be used in both these experiments. Cup D is the only common cup between these two experiments so it contains pure water.
Alternatively, from Experiment 1 we know that Cup A does not contain pure water or the potion that colours eyes white. So by Experiment 2, cup D must contain pure water or the potion that colours eyes white. Similarly, by Experiment 3, cup D must contain pure water or the potion that makes whiskers curly. These last two statements can only be true if cup D is pure water.
In this problem we have a collection of facts that we need to extract new information from. This can be done using logical reasoning. Logic plays an important role in computer science. The smallest unit a computer works with is a bit, which has a value of 1 (true) or 0 (false). All other information in a computer is stored using a specific combination of bits. The computer uses logic to figure out what decisions it should follow, and each of these decisions is based on whether certain bits are set to true (1) or false (0).
Japan