2021 Beaver Computing Challenge
(Grade 7 & 8)

Questions, Answers, Explanations, and Connections

Answer

(A) 6

Explanation of Answer

We are told that the first photo has 64 butterflies in it. Since half the butterflies fly away after each photo is taken, we can record how many butterflies are in each photo.

We see that the photo with 2 butterflies in it is photo number 6. Therefore, the beaver took 6 photos.

Connections to Computer Science

In order to move from 64 butterflies to one butterfly, we need to cut the number in half 6 times. If we started with 128 butterflies, we would need to cut the number in half 7 times before reaching one butterfly, and if we started with 256 butterflies we would need to cut the number in half 8 times before reaching one butterfly.
This process of cutting by half each time decreases the problem size exponentially. There are many natural processes that either grow or shrink exponentially: how an invasive species spreads and how a radioactive element decreases its radioactivity are two examples. This idea is used by computer scientists to design algorithms which use the divide and conquer technique: each major step of the algorithm reduces the size of the problem by half. These sorts of algorithms are very efficient because they can take very large inputs and produce an answer very quickly. One famous example of this idea is binary search in a sorted list of elements.

Country of Original Author

Canada

Answer

(B)

Explanation of Answer

To determine the correct answer, we reverse the process.

Notice that the coin in the bottom-left corner is the only coin that has no other coins on top of it. This means it must have been placed on the table last and was therefore the sixth coin to be placed. Before this coin was placed, the coins on the table must have looked like this:

Now the only coin that has no other coins on top of it is the coin . This coin must have been placed second to last and was therefore the fifth coin to be placed. Before this coin was placed, the coins on the table must have looked like this:

Now the only coin that has no other coins on top of it is the coin . This coin must have been placed third to last and was therefore the fourth coin to be placed.

Continuing this process, we find that the coins were placed on the table in the following order:

1. 
2. 
3. 
4. 
5. 
6. 

Connections to Computer Science

The coins in the picture are laid in a sequence, and the order of the sequence matters.

There are many sequences where the order matters. For example, when getting dressed, putting on shoes should come after putting on pants.

Another example is describing to a computer how to draw a picture. Drawing a circle, then two dots, and then a curved line, will produce a smiley face, as shown in the picture below.

If the order was different, and the circle was drawn last, the two dots and curved line would have been hidden behind the circle.

Computers internally usually also work sequentially. Most computer programs are written so that first one action and then another action happens. So a computer program for drawing a smiley face could look like this:

• draw circle at (0,0) with radius 5
• draw dot at (-2,2)
• draw dot at (2,2)
• draw curved line from (-4,1) to (4,1)

Country of Original Author

Czech Republic

Answer

(A)

Explanation of Answer

Here is the state of the board after each swap:

If you compare the locations of the objects at the beginning, with the locations of the objects after the last swap, you can see that the star is now in the original location of the flower.

Another way to see this final result is to think about trading goods at a market. Suppose you bring a flower and you trade it for a tree. Then you trade your tree for a ladybug. Then you trade your ladybug for a star. The item you end up with is the same as if you traded your flower for a star directly.

Connections to Computer Science

This task focuses on the concept of swapping values between two variables. In computer programming, a variable is a memory location that can hold information. Swapping involves exchanging the values of two variables.

For example, suppose A is a variable that holds the value “18” and B is another variable that holds the value “42”. After a swap, variable A will hold “42” and variable and B will hold “18”.

In most programming languages, a temporary variable is needed to swap values between two variables. For example, if there was a temporary variable T, the following three steps would swap the values between A and B:

1. Give T the value of A.
2. Give A the value of B.
3. Give B the value of T.

One of the most common uses of swapping in computer science is in sorting, where a collection of data it put into either ascending or descending order.

Country of Original Author

India

Answer

(C) 3

Explanation of Answer

The first experiment is flagged because the number of times the target letter T appears in the sequence T T T T T T T is 7 which is between 2 and 8 (inclusive).

The second experiment is not flagged because the number of times the target letter C appears in the sequence A G C T A C T A C is 3 which is not between 1 and 2 (inclusive).

The third experiment is flagged because the number of times the target letter A appears in the sequence T C G C T G C is 0 which is between 0 and 2 (inclusive).

The fourth experiment is flagged because the number of times the target letter G appears in the sequence G A T G T A G C T is 3 which is between 1 and 3 (inclusive).

Three of the four experiments are flagged.

Connections to Computer Science

The concept of pattern recognition is a very important one in computer science. The key goal of pattern recognition is to determine if some input, perhaps text or an image, matches or contains a particular pattern. For example, given a large body of text, such a collection of textbooks or entire webpages, determine if a certain word or phrase appears.

DNA can be described as a very long sequence of the letters A, C, G, T. In humans, there are about 3 billion such letters describing DNA. A particular pattern would be a sequence of letters that is known to indicate a certain genetic condition, such as an increased likelihood of a specific disease.

One very common technique to describe patterns in text is the use of regular expressions. An example of a regular expression for Canadian Postal codes would be (A-Z)(0-9)(A-Z)(0-9)(A-Z)(0-9). This expression indicates that the first, third, and fifth characters must be uppercase letters, and the second, fourth, and sixth characters must be a single digit. Regular expressions like this are used in text editors for advanced “search and replace” functions.

Country of Original Author

Portugal

Answer

(D) Volcanoes 2 and 4

Explanation of Answer

Since Dino cannot climb up and over an erupting volcano, a road to or a road from an erupting volcano is not helpful (at least up to the point where it intersects another road).

In the following image all roads to and from volcanoes 2 and 4 have been removed. Notice that in this situation it is not possible for Dino to get to point \(Q\) from point \(P\).

Using the same approach we can see that a route from \(P\) to \(Q\) does exist for the other three options.