2016 Beaver Computing Challenge
(Grade 7 & 8)
Questions, Answers, Explanations, and Connections
2016 Beaver Computing Challenge
(Grade 7 & 8)
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
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
An artist painted several images of a shaman. In her favourite image, the shaman
Which image is her favourite painting?
(D)
Notice that:
Notice that (D) does satisfy the specifications in that there is no stick, all buttons are done up and the parrot is in his left hand.
The problem is connected to binary logic, which is sometimes called Boolean algebra.
To solve the problem, we use conjunctions. A conjunction is a logical statement that uses the operator AND. The conjunction of a set of values is true if and only if all of the values are true. We can code the answer of each question either with either the value 0 (for false) or 1 (for true):
| Image | |
|
|
|
|---|---|---|---|---|
| Parrot in left hand | 1 | 0 | 1 | 1 |
| Does not hold a stick | 1 | 1 | 0 | 1 |
| Each button is buttoned | 0 | 1 | 1 | 1 |
Reading down each column, we can see that only the last column has true AND true AND true (sometimes written \(1 \wedge 1 \wedge 1\)), which means it satisfies all conditions.
Lithuania
Beaver neighbourhoods consist of rivers flowing between ponds. Patricia is grumpy and wants to build one dam in each neighbourhood that will cause trouble. That is, she wants to block a single river so that beavers will not be able to travel between all pairs of ponds in the neighbourhood.
In which of the following neighbourhoods is Patricia unable to build her dam?
(A)
If putting a dam in a river causes the trouble Patricia wants, we call it a weak link. The correct answer is (A). No matter which single river is blocked, there is still a route between any possible pair of ponds that avoids the dam. The other areas have the following weak links (see the dams in the picture): the middle river in the second picture, the left river in the third picture, the two middle rivers in the fourth picture. There is no weak link in the first picture.
Together, rivers and ponds form a networked system. In this question, the ponds are objects that are to be connected by the rivers.
The most common network used in computer science is the internet. The internet, computers, mobile phones, televisions, etc. are connected by telephone lines, cellphone towers, wireless connections, etc. Originally, the internet was established to connect universities. The architects of ARPANET, as it was called, wanted to ensure that connections between universities would not break down if just one link in their network failed. That is, the founders of the internet in the 1960s already thought of the possibility of weak links.
To deal with networked systems like the ponds and rivers in this task, computer scientists make use of graph theory. A graph is a collection of nodes (like the ponds) and edges (like the rivers). In computer science, graphs are used to model many kinds of networked systems, like communication networks or traffic networks. Many algorithms have been developed to solve problems with graphs. One of these problems is to find bridges in a graph which is exactly the problem of finding weak links in this task.
United States of America
You have a long roll of coloured paper for a party you are hosting. The paper consists of the following pattern repeated more than once:
A beaver cut out a section of the paper between pieces of length 11 and 6 as shown below.
(...paper cut out by beaver...)
Which of the following can be the length of the paper cut out by the beaver?
(A) 31
The first piece of the paper ends with YRR, meaning that the beaver has cut out at least one B. After that, it may have cut out any number of sequences of YRRB.
The right side of the cut out paper must end with YR, since the second piece begins with RB. So, the length of her piece of paper is \(1\) (for the first B) plus \(4\cdot X\) (where X is the number of repeated YRRB patterns) plus \(2\) (for the YR) giving \(4X+3\) as the total length of her paper.
Looking at the possible answers, we wish to determine which answer when subtracted by \(3\) gives a multiple of \(4\). A quick check shows that \(31-3=28\) and \(28 = 4\cdot 7\). None of the other answers give a multiple of \(4\) after subtracting \(3\).
Alternatively, we can notice that the length must be a multiple of 4. We know the lengths of the remaining pieces are 11 and 6, which adds to 17. We can try all four possible answers and determine that only \(17+31=48\) gives a multiple of 4.
Finding a pattern in information is important for a variety of problems. For instance, in the field of bioinformatics, sequences of DNA are composed of patterns, and finding repetitions or substrings that satisfy a certain property is an important research area in genetics and medicine. To solve these sorts of problems, we use text processing algorithms and pattern-matching programs to help determine whether certain strings appear in a sequence of text.
This problem also considers some abstraction: we take a sequence of information and generalize it into a formula or equation which we can solve. In order for computer scientists to solve problems, they need to take an explanation and convert it into something more concrete, formalized and mathematical in order to write a program to solve it.
Czech Republic
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
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
During his descent from the mountain top, the beaver, Theseas, is collecting wood for his lodge from several stations. Every station holds a different amount of wood. While he is descending, he cannot change direction and start climbing again, that is, he can only go in the directions of the arrows.
The paths between stations are given in the image below. Every circle is a station and the number in the circle represents the amount of wood available at that station.
What is the maximum total amount of wood that Theseas can collect during his descent?
(C) 21
The path is shown in the image below.
To see why there is no better path, notice that this path has a score of \(21\). Any better path cannot contain a \(1\) since the path length is \(5\) and if all the other stations had \(5\) logs, the total number of logs would be \(5+5+5+5+1 = 21\) which is not bigger than \(21\). Removing the ones from the diagram and looking at all remaining possible paths gives the paths: \[\{3,4,2,3,4\}, \{3,4,2,3,5\}, \{3,4,5,3,4\}, \{3,4,5,3,5\}, \{ 2,5,5,5,3\}, \{2,5,5,5,4\}\] and of these the paths, \(\{2,5,5,5,4\}\) gives the unique best score of \(21\).
In a triangular pyramid with \(n\) levels (the given problem is an example of a 6 level pyramid), there will be \(2^{n-1}\) different paths from the top to the bottom. For large values of \(n\), this gives too many possibilities to compute by hand or even by machine! Instead of calculating the total sum of every path, we can add to every station (or node) above the bottom level the maximum value of its two children, the nodes connected at a lower level. For example, let’s say we have the following pyramid with \(3\) levels:
Then we can reduce the pyramid by using the above algorithm to get a smaller pyramid given by the following graph, where 9 comes from adding \(3\) to the maximum of \(6\) and \(1\) and similarly \(7\) comes from adding \(5\) to the maximum of \(1\) and \(2\). Repeating this procedure reduces this pyramid to one node with value 11. Breaking down a problem into smaller subproblems is known as dynamic programming.
Cyprus
Five beavers happily live around a circular canal. They decided to have regular meetings at one of their residences. They want to minimize the total swimming distances for them to get to the meeting place.
At whose residence will the meeting take place?
(C) Bubba
The correct answer is C. Bubba will host the meeting. To see this, we can make a distance table to show how far each beaver is from each possible meeting place.
| To | ||||||
|---|---|---|---|---|---|---|
| Betty | Bobby | Ben | Bubba | Bart | ||
| From | Betty | 0 | 400 | 520 | 500 | 200 |
| Bobby | 400 | 0 | 120 | 200 | 500 | |
| Ben | 520 | 120 | 0 | 80 | 380 | |
| Bubba | 500 | 200 | 80 | 0 | 300 | |
| Bart | 200 | 500 | 380 | 300 | 0 | |
| Total | 1620 | 1220 | 1100 | 1080 | 1380 | |
The minimal total distance above is \(1080\). This is the case when everyone meets at Bubba’s home.
Finding a shortest distance is an algorithmic problem that occurs in many situations. In this setting, the circular structure means that from any home to another home, you can reasonably only try two direct routes, either going clockwise or going counterclockwise. In more complicated situations, there are a variety of algorithms one can try to determine the shortest path from one location to the next, arguably the most famous such algorithm being Dijkstra’s Algorithm.
Netherlands
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
Alice the beaver plays a game with shaped cards. She starts with a single card that is a square and uses the following set of replacement rules.
meaning each square card is replaced by two triangle cards, and
meaning each triangle card is replaced by one square card, one triangle and another square (in that order).The result of following these rules three times is shown below.
Boris the beaver plays a similar game. He starts with one of a square, triangle or circle and he plays with a different set of replacement rules. The result of following these rules three times is shown below.
Which of the following set of replacement rules might Boris have used?
(B)
Notice that
so Boris might have used the rules in (B). To be complete, we should rule out the other possibilities.
For answer (A), if Boris starts with a triangle or circle, he will never generate any square cards. So using these rules three times starting with a square, the result is
and the line of cards can only get longer using the rules more often. Alternatively, we can notice that he can never generate two circles beside each other.
For answer (C), we notice that Boris can never generate two squares beside each other.
For answer (D), we notice that Boris can never generate two circles beside each other.
The rules presented here describe a sequence of rewriting rules given by a context-free grammar. These grammar systems can describe
The question here is asking for a derivation or a parse of a given word using different rules. Parsing is one important step in translating a program from “human-readable” words to “computer-readable” binary numbers.
Canada
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
Information is given below about the friendships between a beaver, rabbit, hedgehog, squirrel and skunk on the social network Instachat. In the picture, the lines show which animals are friends with each other. The table records how many friends each animal has.
| Animal | Number of Friends |
|---|---|
| beaver | 4 |
| rabbit | 2 |
| hedgehog | 2 |
| squirrel | 1 |
| skunk | 1 |
Five different animals are on a different social network Snapgram and the same information is recorded in the same way.
Which of the following cannot be the table recording how many friends each animal has on Snapgram?
| Animal | Number of Friends |
|---|---|
| fox | 2 |
| groundhog | 2 |
| chipmunk | 2 |
| turtle | 2 |
| snake | 2 |
| Animal | Number of Friends |
|---|---|
| fox | 2 |
| groundhog | 3 |
| chipmunk | 4 |
| turtle | 3 |
| snake | 2 |
| Animal | Number of Friends |
|---|---|
| fox | 1 |
| groundhog | 4 |
| chipmunk | 3 |
| turtle | 4 |
| snake | 1 |
| Animal | Number of Friends |
|---|---|
| fox | 3 |
| groundhog | 3 |
| chipmunk | 4 |
| turtle | 3 |
| snake | 3 |
(C)
| Animal | Number of Friends |
|---|---|
| fox | 1 |
| groundhog | 4 |
| chipmunk | 3 |
| turtle | 4 |
| snake | 1 |
Each animal with a friend adds two to the total of the values in the table. For example, if the fox becomes friends with the snake, then the snake is also friends with the fox and so both entries to the right of the fox and snake get an additional one to their tally. Thus, the total of the values in the table must be an even number. The sums for the entries in the tables for A, B, C and D are 10, 14, 13 and 16. Therefore the table in C cannot be correct.
For completeness, let’s also show that tables A, B and D can be obtained. Table A is possible by imagining a picture of the friendships as where the lines form a pentagon between the five animals.
Table B is possible by taking the pentagon from table A and adding a friendship between the groundhog and the chipmunk and a friendship between the turtle and the chipmunk.
Lastly, table D is possible by first starting with the situation where each animal is friends with each other animal. Then, remove the friendship between the fox and the groundhog and the friendship between the turtle and the snake.
Social networks can be modelled by a graph. Graphs describe the connections between things. The animals are the vertices of the graph and the edges of the graph correspond to friendships represented by lines in the picture which is a drawing of the graph. In graph theory, the number of friends of an animal is called the degree of the corresponding vertex. The table of degrees is normally written as a degree sequence. A degree sequence is one of many graph properties that give us information about these connections.
Poland
Edward the beaver built a colourful lights display in the center of town. The lights can be made to flash in eight different pretty patterns by turning three switches on and off. Edward wants to test every pattern. To do so, he needs to try all eight different on/off combinations of the three switches. Unfortunately, the switches are each one kilometer apart and Edward has to walk to a switch to be able to change it.
If Edward can start at any one of the switches, what is the least number of kilometers he has to walk?
(B) 6 km
Edward can test the switches using these steps:
| Step | Switches |
|---|---|
| Start | off off off |
| Switch 1 ON | on off off |
| Switch 2 ON | on on off |
| Switch 1 OFF | off on off |
| Switch 3 ON | off on on |
| Switch 2 OFF | off off on |
| Switch 1 ON | on off on |
| Switch 2 ON | on on on |
The left column shows the changes he makes. The right column shows the settings of the switches after each change.
With this strategy, Edward must walk from switch 1 to switch 2 and then further to switches 1, 3, 2, 1 and 2 (in order). Therefore he travels a total distance of 6 km.
We need to show that this cannot be done in less than 6 km. By staying in place with the same switch, Edward can only test one new on/off combination. Hence, when walking only 5 km, he can only test at most six new on/off combinations, which together with the initial switch settings, is still one too few.
All eight combinations of three switches can be generated in just seven steps by flipping exactly one switch at each step. This can be generalized to 16 possible combinations of four switches, 32 possible combinations of 5 switches and so on. If we write 0 for “off" and 1 for “on", the subsequent on/off combinations can be written as a sequence of bit strings. The second column in the table in our solution corresponds to the following sequence: 000 100 110 010 011 001 101 111.
Such sequences are called Gray codes. Each term in a Gray code is unique, even though it differs in only one bit from the adjacent terms. Do you think it is possible to find another Gray code, which works as a closed loop, so that you can change one bit in its last term and get the first one again?
Gray codes have many applications in electronics and computer science. For example, they are used to minimize the number of actions needed during hardware and software testing.
Belgium
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
