2023 Beaver Computing Challenge
(Grade 5 & 6)
Questions, Answers, Explanations, and Connections
2023 Beaver Computing Challenge
(Grade 5 & 6)
Questions, Answers, Explanations, and Connections
Five hats are hanging as shown.
In what order should the hats be rehung so that they get taller as you move left to right?
(A) \(R,P,S,T,Q\)
If we order the hats so that they get taller as you move left to right, the result is as shown below.
In computer science, arranging elements into an ordered sequence is called sorting. Sorting is one of the most fundamental problems in computer science. There are many uses of sorting: when clothes are arranged by size and colour in a store, or when the sports standings are shown in descending order. Having data in sorted order helps us make important observations about the data more quickly, such as finding the biggest value, or smallest value, or the top three values, or the middle value, etc.
There are many algorithms to sort elements. An algorithm is a process to accomplish some task. Many sorting algorithms rely on two basic principles: comparing the relative size of two values, and swapping (or exchanging the positions of) those elements. For the original order of the hats, try to think of a process to compare and swap the hats to put them into sorted order.
Lithuania
Beaver Bai has a garden with 9 fence posts around the edge, as shown.
He uses yellow ropes to divide the garden into smaller sections, according to the following rules:
Each section must be in the shape of a triangle.
One rope cannot cross another rope.
Each end of a rope must be attached to a fence post.
Which of the following gardens below could Bai have made?
(D)
In Option A, one of the sections is a quadrilateral. This breaks the rule that each section must be in the shape of a triangle.
In Option B, two of the ropes cross. This breaks the rule that one rope cannot cross another rope.
In Option C, two of the ropes attach to another rope. This breaks the rule that each end of a rope must be attached to a fence post.
Option D follows all three rules, so is the only garden that Bai could have made among these four options.
This task demonstrates the concept of triangulation: taking a polygon and decomposing it into triangles. Triangulation is a major area of computational geometry, which studies how to solve geometry problems using computer algorithms. A few of the main problems in computational geometry include computer graphics, which is concerned with generating and manipulating visual images on a computer; geographical information systems (GIS), which are systems designed to capture, store, and display data related to the surface of the Earth; and 3D modeling which represents a three-dimensional model as a two-dimensional image.
Indonesia
Karla has three maps that all show exactly the same region. One map shows the forests 
, one shows the rivers 
, and one shows the houses 
. Karla's house is in the forest, touches the bank of the river, and is House A, B, C, or D.
Which house is Karla’s house?
(A) House A
To identify Karla’s house, the information from all three maps must be considered together. This can be done by overlaying the 3 maps:
Since Karla’s house is in the forest and touches the bank of the river, it must be House A. Houses B and C are not in the forest, and House D does not touch the bank of the river.
If the information about the forests, the rivers, and the houses were shown on a single map, then it would be easy to identify the house you are looking for.
In a geographic information system (GIS), a wide variety of spatial information about the surface of the Earth is captured, stored and displayed on a computer. In particular, each different type of information, such as vegetation, buildings, water systems, or roadways is stored independently, but can be integrated in various combinations in order to more easily visualize and analyze patterns and relationships. Some applications of a GIS are emergency management when a natural disaster occurs, car navigation systems, and mapping water systems to preserve wetland habitats.
The principle of multiple layers with different image information is also used in many computer graphics programs, primarily to place visual objects in front of or behind other objects. An important question is always which layer or which objects are displayed in the foreground. In this task with three layers of images, Karla’s map of the houses should be the top layer in order for the houses to not be hidden by the forest areas.
Germany
This is a view of Andrew’s umbrella from above. The umbrella has 10 sections, each with a different design.
Which of the following images shows a possible side view of Andrew’s umbrella?
(C)
First we give each design on Andrew’s umbrella a number, increasing as we move counter clockwise around the umbrella. Then we can check the potential side views to see if the designs are in the correct place.
In this Bebras task, we have only partial information about the umbrella patterns shown in the answer options. Nevertheless, we can determine which image shows Andrew’s umbrella: we can look at the four pattern sequences and notice that only one also occurs in Andrew’s umbrella.
This use of visual pattern matching is also used in machine vision, to detect the location and position of objects based on characteristics of those objects. One example of visual pattern matching is in the design of robots to locate and move physical objects in a factory. Another application is to assist medical doctors in the detection of tumours from CT scans of patients. Both of these applications use partial information to make inferences about the most likely location/orientation/size of objects in visual images.
Switzerland
Masahiro made a hamburger for a customer, but the customer changed their mind several times while giving their order.
Masahiro built the hamburger in the order shown from left to right, always putting new items on top. The 
symbol means that the customer changed their mind about the most recently added item, so Masahiro removed the item on top.
Which of the following hamburgers did Masahiro make?
(B)
The table below shows the steps Masahiro followed when making the hamburger. The top row of the table shows the sequence of actions he performed, and the bottom row shows how the hamburger looks after each action in the top row.
| |
|
|
|
|
|
|
|
|
|
|
|
|---|---|---|---|---|---|---|---|---|---|---|---|
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
Therefore the correct answer is Option B.
In this task, a hamburger is made using two operations: adding an item on top, and removing the top-most item. The hamburger can be thought of as a simple data structure used in computer science, called a stack. A stack follows the last in, first out or LIFO rule: the item that is placed last is the first to be removed. Stacks are used frequently in computer science. One such usage is keeping track of operations that can be "undone", such as edits to a document, browsing history in a browser, or searching through a maze by way of backtracking if a dead end is reached.
Japan
Tiles that show blue areas of water and green areas of land are placed together to create landscapes. Tiles must be placed so that when tiles share an edge, land always touches land and water always touches water. For example, two tiles may be placed as shown on the left, but not as shown on the right:
If the following two tiles have been placed as shown, which tiles can be placed in the grey areas?
(D)
After overlaying the possible tile options with the tiles that have already been placed, we can look at each shared edge in order to verify whether or not land always touches land and water always touches water.
This task focusses on the problem of edge detection in computer science. Edge detection is a main tool in image processing and computer vision, especially with feature detection and feature extraction.
To solve this task, our human eyes can easily find the edge where the land and water meet due to the change in colour. Computer vision would rely on similar changes in colour, brightness, or depth to determine the edges of given features. One application of feature detection is to locate the eyes, nose, or mouth in a given image of a face.
Germany
Evren is trying to learn what a Ricca looks like. Evren studies photos of the following five Riccas and makes some notes that accurately describe what she sees.
Evren is then shown this sixth photo of a Ricca and realizes one of her notes is definitely wrong:
Which one of Evren’s notes about Riccas is definitely wrong?
(D) Riccas have the same number of arms as legs.
The answer is Option D. It is not true that a Ricca always has the same number of arms as legs. The sixth photo shows a Ricca with two arms and five legs.
The note in Option A may still be true. All six photos show Riccas with teeth.
The note in Option B is definitely true. The second photo shows a Ricca with wings.
The note in Option C may still be true. Photos one, two, five, and six show Riccas with horns and “only" two eyes. The remaining photos (three and four) show Riccas with three eyes and no horns.
Evren is learning to identify a Ricca by studying photos of Riccas and looking for similar characteristics. Computers can also be taught to do this, using a process called machine learning. As part of machine learning, a computer is presented with a collection of data, and then it searches for patterns within this data to draw conclusions. Just like with Evren, it is possible for a computer to arrive at the incorrect conclusion. By providing the computer with more data, and data that is more representative and inclusive, the computer can correct its mistakes and update its learning.
Detecting recurring patterns in given data is an important skill in computer science, generally referred to as pattern recognition. For example, in image recognition, pattern recognition techniques assist in identifying objects in images, classifying them into different categories, and even recognizing faces. In natural language processing, pattern recognition enables computers to understand the structure of sentences, identify topics, and even generate human-like text.
If care is not taken in the selection of data for machine learning, bias may be introduced into the pattern recognition algorithm. For example, what impact would a speech recognition system have on society if it were trained only on data from male native English speakers?
Canada
Jacinta’s new helicopter has a control panel with four levers that each control a different system.
The labels on the levers are missing, and Jacinta was told that the system was wired in a confusing way so she doesn’t know which lever controls which system. All she knows is that putting a lever up turns one system and its indicator light on, and putting a lever down turns one system and its indicator light off.
The image shows which indicator lights are on for three different configurations of the levers.
Which of the following correctly matches each lever to the system that it controls?
(C)
We will refer to the systems as heat 
, ventilation 
, lights 
, and humidity 
.
First we will number the levers 1, 2, 3, and 4, starting from the left. In the first image, levers 2 and 4 are up, and the heat and ventilation are on. Thus, levers 2 and 4 must control the heat and ventilation, in some order.
In the second image, levers 1, 2, and 4 are up, and the heat, ventilation, and humidity are on. Since we already know that levers 2 and 4 control the heat and ventilation, we can conclude that lever 1 controls the humidity.
In the third image, levers 1, 3, and 4 are up, and the ventilation, light, and humidity are on. Since we already know that levers 2 and 4 control the heat and ventilation, we can conclude that lever 4 must control the ventilation. It follows that lever 2 must control the heat. We also know that lever 1 controls the humidity, so we can conclude that lever 3 must control the lights.
This problem focusses on keeping track of the arrangement of four levers and the systems they control. Since a system is either on or off, we can keep track of each system using a binary number. A binary number is either the number 0 or 1, which we can think of as "off" or "on", which in this task is indicated by a lever being either "down" or "up".
We can then think about the state of all systems as being a list of four binary numbers. For example, if we list the systems in the order (heat, lights, ventilation, humidity), then the state (0, 1, 0, 1) would indicate that heat and ventilation are off, and that lights and humidity are on. In total, there would be \(2^{4} = 16\) different states for these systems.
This problem then involves determining the state of the systems based on the arrangement of the levers. This operation of updating a state is one of the fundamental operations of the central processing unit (CPU): given the current state and some input, what new state should the computer be in? Every mouse click or key press changes the state of a computer, and the state is stored on the computer as a sequence of binary numbers.
Perú
A beaver has a special technique to shrink images.
First, they cut the original image into 10 equally-sized vertical strips. Then, they remove the even-numbered strips and assemble the odd-numbered strips to create a new image.
Next, they cut the new image into 10 equally-sized horizontal strips. Then, they remove the even-numbered strips and assemble the odd-numbered strips to create a complete shrunken image. Here is an example:
If the beaver uses this technique to shrink the image below, what is the complete shrunken image?
(D)
The steps the beaver uses are illustrated below.
Alternatively, you can solve this multiple-choice question by considering the four options. Since the dark "eye" of the snail is in an even-numbered horizontal strip, it will be removed. This eliminates Options A and B. Similarly, the bottom horizontal strip (numbered 10) is the only one with more than four green cells. Since it is an even-numbered strip, it will be removed. This eliminates Option C because it contains five green cells in its bottom row. Therefore, of the options, Option D must be correct.
This task is focussed on image compression, which is the process of reducing the size of an image file by eliminating or minimizing some of the information in the image while still maintaining sufficient image quality for use. Reducing the size of an image can save both storage space and improve the time needed to transfer the image between devices, such as between two phones.
In this task, the total amount of information stored is only 25% of the original amount of information. However, some of the details of the image are removed. This type of compression is an example of a lossy compression method that works well for certain types of images that don’t have much variation.
There are also lossless compression methods, which allow the original information to be stored in a smaller size completely, without any loss of information. Two well-known examples of lossless compression are ZIP files and PNG files.
Vietnam
Freight trains consist of an engine followed by wagons, each holding a numbered box. The boxes must be unloaded in increasing order, starting from box 1. To unload a box, its wagon must be positioned directly below the crane.
The crane is in a fixed position and trains can only move forward on a loop. Usually, this means that several rounds are needed to unload all the boxes. Each round begins with the engine directly under the crane.
In the example shown, the boxes have to be unloaded in the order 1, 2, 3, 4 and three rounds are needed to do this. In the first round of unloading, the train moves forward to skip box 4, unload box 1, skip box 3, and unload box 2. The train then goes around the track until the engine is under the crane again. In the second round of unloading, the train moves forward to skip box 4, skip the empty wagon, and unload box 3. The train then has to come back for a third round in order to unload box 4.
How many rounds will be needed to unload all the boxes from the following train?
(C) 7
We can simulate the unloading of the boxes in the required order 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 in as few rounds as possible. This just means that a box is unloaded if it is directly below the crane and all lower-numbered boxes have already been unloaded. Carefully following this procedure, we can determine that boxes are unloaded as shown in the following table.
| Round | Boxes Unloaded |
|---|---|
| 1 | 1,2 |
| 2 | 3,4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7,8 |
| 6 | 9 |
| 7 | 10 |
Alternatively, one might discover a general rule that determines exactly how many extra rounds (rounds after the first round) are needed. For each number in the sequence 1, 2,..., 10, if the next number in the sequence comes to the left of it on the train, an extra round is needed. For instance, if 3 appears to the left of 2, then 3 will be skipped to unload 2 and so an extra round is needed to bring 3 under the crane. For this question, there are six such pairs that are out of order on the train: (2,3), (4,5), (5,6), (6,7), (8,9), and (9, 10). Therefore, six extra rounds are needed, for a total of seven rounds.
This task has the concept of counting inversions as the key idea. Generally, an inversion in a list of numbers is where a number, say 6, has the next largest number, 7, written earlier in the list. In the context of this task, an inversion is where box \(K\) has box \(K+1\) somewhere to the left of it on the train. For each such inversion, an extra round is needed. If we count the number of inversions, we get the answer.
Counting inversions with respect to a desired sequence has many applications in computer science. For some sorting algorithms, such as insertion sort, the number of inversions tells us how many swaps we need to sort a given sequence. Consider another example from online shopping, where two customers rank the same set of items in order of preference. Then, the number of inversions in their rankings tells us how aligned their tastes are, and this information can be used by online retailers to identify "similar" customers to make product recommendations.
India
Ángel has the decorated mat shown below on the left and the pattern shown below on the right.
They determine that the pattern appears twice on the mat. Note that they may rotate the pattern but they may not turn it over.
Then Ángel looks at the new mat shown below on the left for the new pattern shown below on the right.
How many times does this new pattern appear on the new mat if Ángel may rotate the pattern but not turn it over?
(B) 4
The four appearances of the pattern on the larger mat are illustrated below.
One way to find these appearances, is to find each red circle on the larger mat. For each of these red circles, we can align it with the red circle on the pattern. Then, to find appearances of the pattern with these red circles aligned, we can rotate the pattern to see if its four possible orientations match the larger mat.
Detecting recurring patterns in given data is an important skill in computer science, generally referred to as pattern recognition. For example, in image recognition, pattern recognition techniques assist in identifying objects in images, classifying them into different categories, and even recognizing faces. In natural language processing, pattern recognition enables computers to understand the structure of sentences, identify topics, and even generate human-like text.
We can use pattern recognition with less abstract, real-life examples such as images. This task requires spatial orientation, which is important in robotics and computer graphics. Spatial orientation involves understanding and interpreting visual information, such as images, diagrams, or other graphical representations, and the ability to manipulate these representations in order to solve problems or create new solutions. In computer graphics, spatial orientation is used to create realistic animations and renderings, as it helps artists and programmers understand and manipulate complex 3D models.
Switzerland
Plots of land on Qi’s farm are arranged in an 8-by-8 grid. The 64 plots contain four types of plants as shown.
Ali wants to install sprinklers so that each plot is watered by exactly one sprinkler. All the plots watered by a single sprinkler must be the same type of plant. There are three types of sprinklers:
small sprinklers that water the one plot in a 1-by-1 region,
medium sprinklers that water the four plots in a 2-by-2 region, and
large sprinklers that water the sixteen plots in a 4-by-4 region.
What is the minimum number of sprinklers that Qi needs?
(D) 25
The diagram below shows how Qi’s farm can be divided into one 4-by-4 region, eight 2-by-2 regions and sixteen 1-by-1 regions. Since \(1+8+16=25\), this means it is possible for Qi to use 25 sprinklers.
We need to convince ourselves that there isn’t a way for Ali to use fewer than 25 sprinklers.
An important observation is that Ali should use as many large sprinklers as possible, and then as many medium sprinklers as possible. Finally, she can use one small sprinkler for each remaining 1-by-1 region. This approach works because of the specific shape and size of regions watered by each type of sprinkler. Try to convince yourself that it is true.
Using this idea, we see that there are only two 4-by-4 regions containing the same type of plant (corn). One is the location shown above and a large sprinkler should be installed there because the alternative is one row directly below this location. This alternative does not leave any unwatered 2-by-2 regions of corn and would require a total of 8 sprinklers to water the corn which is more than the 5 sprinklers used in our answer above.
Now we need to install as many medium sprinklers as possible. Exactly one of these sprinklers can water each of the corn and the apples. There are only two 2-by-2 regions of grapes and a medium sprinkler can water each of these regions. The pumpkins can be divided into 2-by-2 regions in several ways, but only into at most four 2-by-2 regions. In total, this means Ali should use \(1+1+2+4=8\) medium sprinklers.
We have determined how to water \(1\times16+8\times4=48\) of the 1-by-1 regions on Ali’s farm. Therefore, an additional \(64-48=16\) small sprinklers are needed for a total of \(1+8+16=25\) sprinklers.
This task is an example of an optimization problem: problems which have the goal of maximizing or minimizing a target value given a set of restrictions or constraints. Several optimization problems can be solved by following the strategy of always selecting the best choice at each step, which is called the local optimum and hoping that doing so will lead to the best result overall, which is called the global optimum. This problem-solving strategy is known as a greedy approach. A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. The greedy approach of picking the largest possible sprinkler at any point does yield the global optimum in this task. In many problems, however, a greedy strategy does not produce an optimal solution, but can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
This task also highlights the computer science concept of a quadtree. A quadtree is a way to represent an image by dividing it into four equal square regions. A region can further be divided into four regions until each region contains exactly one colour, which is similar to how the solution divides the farm into regions until each region encloses exactly one plant. Quadtrees store images as a collection of regions rather than individual pixels, resulting in smaller storage requirements and faster operations. This idea of quadtrees is applied to areas such as image processing, game development, and navigation systems.
Philippines
