2017 Beaver Computing Challenge
(Grade 7 & 8)

Questions, Answers, Explanations, and Connections

Answer

(B) 6

Explanation of Answer

The three dogs can end up in three consecutive positions by

• first swapping the first large dog twice towards the right, and then
• swapping the last large dog four times towards the left.

Every small dog must be involved in a swap because each small dog is positioned between two large dogs. Swapping two small dogs does not have any effect so each useful swap of a small dog must be with a large dog. Since there are six small dogs, this means there must be at least six swaps.

Notice that trying to move all of the three large dogs towards the left or all three large dogs towards the right, requires more than six swaps.

Connections to Computer Science

Data is stored in a computer’s memory. Data includes both internal memory (often referred to as RAM) and external memory (which might be a hard drive or USB flash drive, for example). Computers can access data in internal memory very quickly but external memory is more cost-effective than internal memory. This trade-off means that modern computers usually have a lot more external memory but computer scientists try to find ways to use the internal memory as much as possible.

For this problem, the only operation we are concerned about is a swap. If we think of the dogs as data stored in the memory of a computer, then a swap involves changing the location of two pieces of data. If this data is in external memory, then having as few swaps as possible is exactly what we need to do in order to perform the overall task as quickly as possible. Swap operations are also used in some sorting algorithms, where we have to arrange data in ascending or descending order, since we would like some information listed in some ranking or priority order. An example of a sorting algorithm is bubble sort: in each round of the algorithm we swap two consecutive data that are not in the correct order.

Country of Original Author

Canada

Answer

(B) 5

Explanation of Answer

At 09:00 and 10:00, 5 students need a computer – we can’t solve the problem with fewer than 5 computers. If we organize the information properly, as in the following table, 5 computers are enough.

When a students arrives, they sit on the first available computer. When they have finished their work, another student comes and sits at that computer.

Connections to Computer Science

In order to understand large quantities of data and the relationship between different types of data, it is often best to create a method of data representation, for example a table, chart or diagram. Depending on the information of interest, we can represent the same data differently, and different relationships may be revealed.

For the current task, another way to represent this data is:

Scheduling and optimizing resources are important problems in real life. For example, in a room reservation system for a hotel, it is very important for two reservations not to overlap.

Another way to represent this data is to create a graph. A graph is a set of nodes along with a set of edges connecting pairs of nodes. In this task, the nodes are intervals and there is an edge between two nodes if those two intervals intersect. This graph is called an interval graph. If we can assign the fewest number of colours to each node so that no adjacent nodes are the same colour, then that will be the optimal allocation.

Country of Original Author

Hungary

Answer

(C)

Explanation of Answer

There are seven skaters. After every seven minutes, the skater originally at the front of the line returns to the front of the line. Thus, after 7 minutes, the skaters will be in the same position as they started. After 14 minutes, again, the skaters will be in the same positions. So, to get to 16 minutes, we need two more minutes, and so V then U move to the back of the line, and thus T is in front.

Connections to Computer Science

The solution to this problem involved finding the quotient and remainder when dividing 60 by 7. Computing and working with remainders is called modular arithmetic. This mathematics is central to many areas of computer science. Modular arithmetic is related to how we represent integers in computer memory. It also plays a central role in cryptography which is the study of sending and receiving secret messages.

A third use of modular arithmetic arises when arranging and manipulating data similar to the skaters in this problem. We can abstractly view a line of data by what computer scientists call a queue. One way to store the data in a queue in memory, is to use a "circular" array-based queue. This data structure allows data to be efficiently removed from the front of the queue and added to the rear of the queue. Modular arithmetic is usually used in the details of the implementation.

Country of Original Author

Canada

Answer

(B) 2

Explanation of Answer

It is clear that the chameleon must change colour from red to blue, yellow or pink after its first move. So this means that the chameleon must have at least two colours.
The path below shows that it is possible to have only two colours.

Connections to Computer Science

One of the most important problems that is solved using computer algorithms is the problem of finding the optimal path in a network. In this task, the optimal (or best) path is the one which requires the least number of colours. In other situations, it may be the path that travels through the least number of toll roads, or takes the shortest time, or uses the least amount of fuel.

This task is small and simplified enough to be solvable with a few insights, but larger problems, like finding the shortest path to send a message through the internet, require more sophisticated algorithms that may not even know all of the possible paths, and yet can solve the problem efficiently. These algorithms fall under the category of networking algorithms.

Country of Original Author

Ukraine

Answer

(D) all computers in the world which are connected to the Internet and set up like Darren’s

Explanation of Answer

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.

Connections to Computer Science

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.

Country of Original Author

Estonia

Answer

(B) 4 seconds

Explanation of Answer

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

Connections to Computer Science

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.

Country of Original Author

Canada

Answer

(C) A baguette and a slice of toast

Explanation of Answer

The truth table expresses relationships between beavers and types of bread. Number the four bullet items from top to bottom, and then we can record facts from each bullet item.

Since Alice does not have a roll or croissant and she had two different type of bread, she must have a baguette and a slice of toast.

Connections to Computer Science

The core idea of this problem is on logic, which is the study of truth, implications and conclusions. More formally, this problem relies on boolean algebra. Algebra deals with solving equations to find an unknown value; for example, the equation \(x+9=14\) has a solution of \(x=5\). Boolean algebra does not give numeric values to variables, but instead gives boolean values of either true or false to each variable. In this problem, there would be 16 “variables”, one of each of the combinations of people and bread.

Computers use boolean logic in conditional evaluation, such as if-statements, as well as iteration, such as loops, which are two of the main programming concepts in many programming languages.

Country of Original Author

Japan

Answer

(B) 6

Explanation of Answer

In the diagram below, the six red nodes are the only nodes which would disconnect the pipe network if they were removed.

Connections to Computer Science

Many structures, from hardware chipset to city maps, can be modeled by graphs. A graph is a set of nodes with a set of edges which connect pairs of nodes. In most of these structures, it is crucial to keep all components connected to allow communication/transportation between all nodes. One method to check the connectedness of the structure is to find and limit the number of cut nodes in the graph. A cut node is any node whose removal increases the number of connected components. This problem deals with the analysis and identification of all cut nodes in the graph.

Country of Original Author

Iran

Answer

(C) 2

Explanation of Answer

Label the chairs from 1 to 7, clockwise, starting with 1 being the top-most chair with a large beaver in front of it. Consider the movement after three rounds, which multiplies the movement by 3.

Big beavers move 9 steps counterclockwise. Thus, one big beaver moves from chair 1 to 6, and the other big beaver moves from chair 6 to 4.

Medium beavers move 6 steps counterclockwise. Thus, one medium beaver moves from chair 4 to 5, and the other medium beaver moves from chair 3 to 4.

Small beavers move 3 steps clockwise. One small beaver moves from chair 2 to 5, another moves from chair 7 to 3, and third moves from chair 5 to 1.

So after 3 rounds, chairs 1, 3, 6 are occupied with 1 beaver each, while chairs 4 and 5 are occupied with 2 beavers each. The only unoccupied chairs are 2 and 7.

Connections to Computer Science

One way to solve this problem is remembering the state of each beaver, in terms of its position after each round. 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 7 states (one for each chair), and transitions for each type of beaver to its corresponding next state.

Country of Original Author

Malaysia