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.