2017 Beaver Computing Challenge
(Grade 9 & 10)
Questions, Answers, Explanations, and Connections
2017 Beaver Computing Challenge
(Grade 9 & 10)
Questions, Answers, Explanations, and Connections
There are 12 spaces for cars in a parking lot. The pictures below show which spaces were used on Monday and which spaces were used on Tuesday.
How many parking spaces were empty on both Monday and Tuesday?
(B) 4
We can see which spaces were used by placing the cars from both days on the parking lot at the same time.
Then we can simply count empty spaces to determine that four spaces were empty on both Monday and Tuesday.
All data can be thought of as a sequence of zeros and ones. Each zero or one is called a bit and the sequence is called a binary code, binary representation, or binary number.
In this task, we can model an empty space as 0 and a space with a car as 1; each parking space corresponds to a bit. We get a sequence of bits by viewing the parking spaces in order. For example, we can read the top row from left to right and and then the bottom row from left to right to get 101001001010 from the parking lot on Monday and 100100000111 from the parking lot on Tuesday. This task asks to determine which of the twelve positions contain a 1 in either of these binary numbers. This is a logical operation named OR. Notice how we can compute the correct answer by seeing that
| Monday | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tuesday | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| Monday OR Tuesday | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
This resulting binary number has four zeros in it.
Canada
Seven people are skating in a line on a very long, frozen canal. They begin as shown below.
After every minute the person at the front of the line moves to the end of the line. For example, after one minute, U will be in front of the line, since V will move behind P.
Which skater will be at the front of the line after 9 minutes?
(C)
We can simply trace out the positions after each minute:
Thus, after 9 minutes, T is in front.
This task is focussed on tracing an algorithm and remembering the state or configuration of all information. Specifically, we start in a given configuration, follow a sequence of (nine, in this task) steps, and we must determine the final configuration. This process of tracing is used by computer scientists to ensure that that computer programs perform the intended process, and if they do not, to find the location or step where the program is not correct.
Canada
Darren’s computer is connected to the Internet but does not have any antivirus or firewall software. None of the accounts on his computer are protected by a password.
Which computers are at risk because of this?
(D) all computers in the world which are connected to the Internet and set up like Darren’s
Due to Darren’s reckless behaviour, his own computer may get infected by malicious software. However, infected computers are often used as a platform for attacking other computers. This means that all computers connected to the Internet without proper protection, such as firewalls and antivirus software are at risk because of Darren’s actions.
Owners of other computers can reduce some of the risks by following good practices. For example, installing security updates and running antivirus software reduces the risk of malware spreading to other computers. Unfortunately, this does not eliminate all risks. Malware, which is software designed to do malicious things, if it is on Darren’s computer, may be used to send spam or overload network connections (these are called DDoS attacks), and there is very little other computer users can do to protect themselves against these larger scale attacks.
Cybersecurity (or Information Technology security) helps protect computer systems from theft or damage to the hardware, software or the information on them, as well as from disruption or misdirection of the services they provide.
Estonia
The lines in the diagram show exactly which pairs of students in a class are friends. A popular artist releases a new song on Monday and there is a musical note beside each student that buys the song that day.
Every day after that, if a student has not bought the song yet but at least half of their friends did buy the song before this day, he or she will also buy the song. Otherwise they do not buy the song yet.
What is the earliest day when all students in the class own the song?
(B) Thursday
Tom, Ted and Kim buy the song on Tuesday:
Anna and Jane buy the song on Wednesday:
Finally Joe will buy the song on Thursday.
This task models a social network of friends by way of a graph. Each person is a vertex in the graph, and two friends are connected by an edge. The task is based on determining the spread of influence through a social network. This spread of influence can be modelled by defining a threshold of diffusion: that is, every person changes his/her mind if a certain ratio of his/her neighbours have a different idea.
Social media companies and marketing companies extract information about connections between individuals and purchasing preferences in order to attempt to market new products or ideas to individuals, based on the proportion of friends who have purchased those products or agree with the particular idea.
Iran
Four friends each buy one drink. How happy each person will be for each type of drink is shown in the table below. The more hearts indicated, the happier a person will be. Unfortunately, only one of each of the four types of drinks is available.
Four hearts |
Three hearts |
Two hearts |
One heart |
|
|---|---|---|---|---|
| Anna |  |
 |
 |
 |
| Bernard | |
|
|
|
| Christine | |
|
|
|
| Daniel | |
|
|
|
For example, Anna prefers with happiness , with happiness , and so on.
When measured by the total number of hearts, what is the happiest the friends can be?
(B) 14
Since three people want , the maximum total number of hearts the group could get
is 4+4+3+3 = 14. This is obtainable via the following matching:
Another way to see this, since Daniel has as his favourite drink and all others rank this beverage
last, Daniel must pick to maximize the group’s happiness.
Now, the first three people have the same first preference however the
Anna has as the next favourite and the other
two people have this as the third favourite. Thus Anna should pick . The other two people can pick and in whichever order.
Optimization is a very important part of computer science. In this situation, we are trying to maximize the happiness of the group. Optimization problems are ubiquitous in computer science.
This problem is a specific instance of an optimal matching problem. In this task, friends are trying to get matched to the best possible drink to make the group as happy as possible. These types of problems are extremely important in the real world. As an example, patients who are waiting for an organ transplant are place on a huge list. However, not all organs can be used on a person – organ donors must, for example, match their blood types in order to have a chance at a successful operation. These constraints make it harder to find a successful matching.
Canada
Numbered balls roll down a ramp as shown below. When a ball comes to a hole, if there is enough space, the ball falls in. Otherwise, the ball rolls past the hole. A pin at the bottom of each hole can be pulled which ejects the balls.
Note the final ordering of the balls in the example above is 45321.
In the diagram below, ten balls roll down the ramp. Three holes, with pins labelled A, B, and C, have space for 3, 2 and 1 balls, respectively. After all ten balls stop moving, pin A is pulled. Then, after all the balls released from A stop moving, pin B is pulled. Finally, after all the balls released from B stop moving, pin C is pulled.
Which of the following is the final ordering of the balls?
(D)
Hole A has space for three balls, so balls 4 to 10 roll past it in order. Hole B has space for two balls, so balls 6 to 10 roll past it in order. Hole C has space for one ball, so balls 7 to 10 roll past it in order. Then the pin in hole A is pulled and balls are ejected in the order 3,2,1 and roll to the bottom. At this point, the balls are at the bottom in the order 7,8,9,10,3,2,1. Then the pin in hole B is pulled and balls are ejected in the order 5,4. At this point, the balls are at the bottom in the order 7,8,9,10,3,2,1,5,4. Finally, the pin is pulled in hole C and ball 6 rolls to the bottom giving the correct answer.
The holes act like a stack which is a data structure. A data structure is a way of organizing data to make certain operations, like insert, delete, or retrieve, more efficient. A stack is based on the last-in first-out principle (LIFO). For example, the first ball to fall into a hole, is the last ball ejected from the hole. Despite being a very simple idea, it is useful in many different situations.
As an example, a stack can be used to check that the brackets in a mathematical expression like \(((1+2)*3)\) are balanced but the brackets in \(((4+5)*(6-7)\) are not balanced. The way to perform this check is that all opening brackets should be put on a stack (this operation is called a push) and when its matching closing bracket is found, the opening bracket is removed from the top of the stack (this operation is called a pop).
Serbia
Four fish are placed on a tray as shown below.
Every time a fish is turned clockwise, the fish diagonal to it also turns the same amount but in a counter-clockwise direction. For example, if the fish in the upper right turns 90\(\degree\) clockwise, then the fish in the lower left turns 90\(\degree\) counter-clockwise.
Aimi makes the following four turns in order.
What does the tray look like after Aimi is done?
(C)
A student who tries to follow this in their head is likely to get confused. A simpler way of solving this task reliably is required. One way is to produce a quick and simple notation to keep track of the changes. The system shown below is clear and easy to produce if arrows are used instead of fish.
| Step | start | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Arrows |  |
 |
 |
 |
 |
Alternatively this task can be quickly solved by reading all the operations and noticing that only step number 2 affects toys on the lower-left and upper-right. Therefore a student can simply look at the answer options and choose the only one with lower-left and upper-right fish in the correct position.
One way to solve this problem is remembering the state of each fish, in terms of its position after each turn. To determine the correctness of a program, typically we need to determine the state of all variables at each step of the program. This process of debugging or tracing of a program is an important part of designing and reasoning about the correctness of computer programs.
Computers, in particular the central processing unit or CPU, can be modelled as a finite state machine which keeps track of its current state and will change its state based on input. This problem can be simulated with a finite state machine with 4 states (one for each corner of the digram), and transitions for each possible rotation of each fish to its corresponding next state.
Japan
At the Beaver Apple Orchard, apples are either sold individually, or in bags of 8 apples (called Family Packs), or in boxes of 8 Family Packs. Therefore, apples are packed according to the following rules:
How many boxes, loose bags and loose apples are used to pack 275 apples?
(B)
Each box contains a total of 64 apples (8 bags \(\times\) 8 apples per bag). The beavers picked 275 apples which filled four boxes (\(275\div 64=4.296875\)). These four boxes contains a total of \(64 \times 4 = 256\) apples. Since each bag holds 8 apples, the remaining \(275-256=19\) apples filled 2 loose bags (\(19\div 8=2.375\)). These two loose bags contain 16 apples leaving 3 loose apples left.
As a check:
Choice A has a total of \(3\times 64 + 7\times 8 + 7 = 255\) apples
Choice B has \(4\times 64 + 2\times 8 + 3 = 275\) apples
Choice C has \(3\times 64 + 5\times 8 + 1 = 233\) apples
Choice D has \(4\times 64 + 1\times 8 + 6 = 270\) apples
The binary number system is the simplest form of computer code or information. The binary number system uses binary numbers, namely a sequence of zeros and ones, to represent all information.
The octal system, on the other hand, uses eight different symbols, values from 0 to 7. If any value larger than 7 is needed, extra columns are added to the left. Each value in one column is 8 times greater than the value in the column to its immediate right. The octal system allows the same information to be represented using only a third of the digits as each octal digit represents three binary digits. This was ideal for some old computer systems as they could concisely display certain machine code.
In the question, the boxes represent the number of \(8^2=64\) apples, the loose bags represent the number of \(8^1=8\) apples, and the loose apples represent the number of \(8^0=1\) (units). Thus, the decimal (base-10) number 275 is expressed as 423 in the octal (base-8) system.
Taiwan
In Roundabout City, navigation software gives instructions as a sequence of numbers, representing which exit number to take at each roundabout. For example, the instructions “4 1 2” mean to take the 4th exit at the first roundabout, the 1st exit at the next roundabout, and the 2nd exit at the next roundabout. The diagram shows this route highlighted in green, beginning at A.
If we start from A and follow the sequence “3 1 3 2 3" where will we end up?
(B) Point B
This is the route you would take:
This task introduces one important element of many computer programming languages: the instructions in a computer program are performed sequential, one after another in order. Additionally, each individual instruction should be performed exactly as specified.
The sequence of instructions given in the task, which is the exit number at each roundabout, can be thought of as a program in a very simple programming language. In order to achieve the desired goal or output, each instruction must be followed exactly (e.g., the sequence “4 1 2” is different than “3 1 2”) and in the order specified (e.g., the sequence “4 1 2” is not the same as the sequence “2 4 1”).
Slovenia
Peter and Henrietta are playing a video game. They move a beaver at a constant speed from the start of a course to the finish. The course consists of platforms on two levels. At the end of each platform before the finish, the beaver jumps instantaneously up or down to the next platform. The amount of time to move over each platform of the game is shown below each platform.
Here is an example course:
Peter and Henrietta start playing the following two different courses at exactly the same time.
For how long are both beavers moving along the top level at the same time?
(B) 4 seconds
We can see this answer by writing down "being at the bottom level for one second" as a 0, and "being at the top level for one second" as 1. Then, Peter’s game can be described as: \[0001111001111000\] and Henrietta’s game can be described as: \[0011001100110011\] To find the times that they are both on the upper level, we need to find the times when both games have a 1 value simultaneously. This can be done by applying the boolean logic function AND between these two sequences to get:
| Peter's game | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Henrietta's game | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| Peter's AND Henrietta's games | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
One of the main philosophies in computer science is how to represent information. In this task, we can abstract (or hide) away some of the details of the game to focus on what matters, which in this case is when a player is on the upper level. Then, once the information is represented in a precise way, we can transform or combine the information into new and meaningful ways. Specifically, for this problem, we treat the information as sequences of binary numbers and perform a bit-wise AND operation to find where both sequences have a 1 value simultaneously.
Canada
In the Bebras Museum of Post-Modern Wood Art, there is an intelligent security system that detects intruders. An intruder is a person who has entered the museum, but not via the entrance. The entrance of the museum is in Room 1.
Each and every time a person enters or leaves a room, the system detects exactly how many people are in each room and records this in a table. The system always correctly allocates each person in the museum to a single room. It may happen that several people enter or leave a room at the same time.
The table shows the records of the intelligent security system and the image shows the layout of the rooms in the museum.
| Time | Room 1 | Room 2 | Room 3 | Room 4 |
|---|---|---|---|---|
| 10:00 | 2 | 0 | 0 | 0 |
| 10:07 | 3 | 0 | 0 | 0 |
| 10:08 | 2 | 1 | 0 | 0 |
| 10:12 | 4 | 1 | 1 | 0 |
| 10:13 | 2 | 2 | 3 | 0 |
| 10:17 | 5 | 2 | 2 | 1 |
| 10:20 | 4 | 1 | 2 | 2 |
At what time did the system detect an intruder?
(C) 10:13
At 10:13 two people entered room 3, but in the attached rooms there was only one person before (in room 2). Thus someone entered room 3 from outside the museum not using the entrance.
Security systems keeping track of the number of people is critical in places such as airports, train stations or government buildings. Computer programs can evaluate and extract information from images, including the ability to detect people and thus count them. These programs use artificial intelligence, for example, to recognize humans, but also use simple logical rules like those outlined in this task (i.e., the number of people in a room cannot be more than the sum of all people in the room before plus the number of people in adjoining rooms) in order to detect security breaches.
Germany
A super hero watches over Beaver City from a straight path across a river. From every point along the path, the super hero needs to be able to see the point in the city directly across the river. Unfortunately, 16 walls of varying lengths stand between the river and the city as shown.
Fortunately, the super hero has X-ray vision and can see through a wall.
Unfortunately, the super hero can only see through one wall at a time.
Fortunately, the super hero is strong enough to destroy walls, and when he destroys a wall, he destroys it completely.
Unfortunately, destroying a wall makes the super hero very tired.
What is the fewest number of walls that the super hero needs to destroy?
(A) 9
Instead of determining the fewest number of walls that the super hero needs to destroy, we consider the largest number of walls that the super hero can keep (not destroy). This is equivalent.
We will show that the largest number of walls that the super hero can keep is seven. Since there are at total of 16 walls, this means the super hero needs to destroy \(16-7=9\) walls.
Consider the seven grey walls in the picture below.
No two of these seven walls “overlap". That is, from every point along the path, at most one of these walls will be between the super hero and the point in the city directly across the river. Thus we know that the super hero can keep at least seven walls. We must show that the super hero cannot keep more than seven walls.
There are walls of four lengths. Let’s name these lengths 1, 2, 3 and 4 (which happen to be proportional to the actual lengths in the picture).
Interestingly, instead of the leftmost wall “A" of length 3 in our solution, the super hero could keep either of the two leftmost walls of length 2, “B" or “C". So there is an alternative set of seven walls of lengths 2, 1, 2, 1, 1, 2 and 1 that the super hero could keep. The super hero cannot do better than this because there are only five walls of length 1 and two of them “overlap".
Why did we choose a wall of length 3 in our solution? We did this because it comes from a way to solve this problem for any set and placement of walls, not just those in this particular task. More generally, we can find the walls to keep by starting from the left and always selecting the next (non-overlapping) wall that ends closest to the left. (Can you see why this always works?)
Another way to observe that we can’t destroy less than 9 walls is to notice that there are disjoint sets of overlapping walls of sizes 4, 3, 4, and 2 when reading from left to right. This means that at least \(3+2+3+1=9\) walls must be destroyed.
The general solution to this problem is a greedy algorithm. That is, it is a sequence that solves a problem by always making a choice at each step that seems best “locally" or “at the moment". It does not take into account the “big picture" or full set of information.
This particular problem is a model of a scheduling problem for which computer scientists are interested in solving with efficient algorithms. To see this, think of time moving forward as you move towards from left to right and think of the walls as tasks that need to be completed with a fixed start and end time. The restriction that the super hero can only see through one wall corresponds to the fact that only one task can be completed at any one time. In our problem, the super hero is trying to solve as many tasks as possible!
Canada
All of the litter in the park shown below needs to be picked up. The park is a \(16\times 16\) grid.
Lucy must divide the entire park into square regions of sizes \(1\times 1\), \(2\times 2\), \(4\times 4\) and \(8\times 8\).
Each of the square regions must contain at most one piece of litter.
What is the fewest possible number of regions that Lucy can divide the park into?
(B) 13
The solution is shown below, where the red lines indicate where we divide the park into regions:
Notice that we must use at least 8 square regions, since there are 8 pieces of litter. To get the minimum number of squares, we want to maximum the size of each square region around each piece of litter. For the solution shown, there is no larger square of the given sizes that can surround each piece of litter without overlapping another piece of litter.
This representation of two-dimensional information is called a quad-tree. A quad-tree splits a two-dimensional region into four equal parts (quad meaning four in Latin), where each part may be further subdivided into four equal parts, until there is only one item in each part. The use of quad-trees as a data structure allows graphical information (such as the positions of windows on a computer screen) to be stored and searched efficiently, in particular, allowing range queries of the form “how many objects are in this part of a picture?" to be performed in a very efficient manner.
Canada
The Beaver family has built a lodge with 4 rooms and 5 tunnels connecting rooms as shown. There are also 7 doorways to the outside.
The Beaver children have noticed that it is possible to start in one of the rooms and run along a path passing through all of the tunnels and all of the doorways without walking through any doorway or tunnel twice.
In which room did the Beaver children start running along such a path?
(C) Room C
Turn each room into a node with an additional node for the outside. The nodes are connected if and only if there is a tunnel between the rooms presented by them or a doorway if one of the nodes represents the outside.
The described path is possible if there are no more than two nodes with an odd number of edges. Such nodes will be the first and last node on a path.
In our case the starting node with an odd number of edges (3 tunnels + 2 doorways) has to be C.
We can transform this task into a graph theory problem, where each location (room or outside) is represented as a node and each tunnel or doorway is represented as one edge. The path which this task asks to find is called an Eulerian path: that is, a path in a graph which visits every node exactly once. In order for there to be an Eulerian path in a graph, it is necessary that either zero or two nodes have an odd degree, where the degree of a node is the number of edges connected to that node. To see why that condition is necessary, notice that a continuous path will leave each node exactly as often as enters it, except for nodes which are at the start and at the finish.
Many problems are modelled using graphs, and computers algorithms for shortest paths, cycle finding, connectivity, and strongly connected components are some examples of well-known and well-studied algorithms that have been developed to solve real-world problems involving graphs.
Lithuania
On a digital clock, each digit can be formed by lighting up some of the seven segments.
Below, each of the digits from 0–9 are shown by lighting up some of those seven segments.
Suppose that some of the seven segments are not working but each of the ten digits can still be determined unambiguously.
What is the largest possible number of segments that are not working?
(C) 2
Consider the following labelling of the 7 segments of one digit, with the letters a through g:
Segment a must work to distinguish between digits 1 and 7.
Segment b must work to distinguish between digits 6 and 8.
Segment e must work to distinguish between digits 5 and 6.
Segment f must work to distinguish between digits 3 and 9.
Segment g must work to distinguish between digits 0 and 8.
If both segments c and d were not working, we would have the following 10 digits, each of which is uniquely determined:
Pattern recognition algorithms are algorithms with take in complex information, such as a picture or sound, and try to categorize it. For example, pattern recognition algorithms are used to detect facial features, such as eyes, mouth, and nose, for security and social media applications. These algorithms look for identifying information and attempt to provide a “most likely” answer, using statistical models.
Pattern recognition is a branch of a larger area of computer science called machine learning, that focuses on the recognition of patterns and regularities in data. One of the approaches to recognition is to extract specific features, that allow uniquely identify objects. This task focuses on identifying these key features to distinguish between each digit.
Russia