University of Waterloo Logo and CEMC Banner

2018 Beaver Computing Challenge
(Grade 7 & 8)

Questions, Answers, Explanations, and Connections

Part A

Roped Trees

Story

Joni Beaver uses rope to mark groups of trees. The rope forms a very tight loop so that each tree either touches the rope or is entirely inside the loop. Below is an example where the rope touches exactly 5 trees when viewed from above.

Question

How many trees will the rope touch if the trees are arranged as follows (when viewed from above)?

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

Answer

(C) 6

Explanation of Answer

We can count the trees touching the rope in the picture below.

Connections to Computer Science

This problem is known as finding the convex hull of a set of points. One way to define this is the polygon with the smallest area which contains all the points in the set. The word convex means extending outward or curving out, and any two points within a convex shape, when drawn on paper, can be connected with a straight line which is inside of the shape. The word hull here is used to describe the “shell" or “encasement", as in the hull of a ship or the hull of a seed, such as corn.

Finding the convex hull of a set of points is very useful:

Country of Original Author

Canada

Rotation Game

Story

Beavers play a simple game. The game always begins with this starting position:

In a 2 by 2 grid, the top left square is red, the top right square is green, the bottom left square is blue, and the bottom right square is yellow.

From this starting position, rotation instructions are followed. All the rotations are clockwise and one quarter of a complete turn. The possible instructions are:

For example, if the first instruction is 2R, the top-left square will be Yellow as shown below.

In a 2 by 2 grid, the top left square is yellow, the top right square is blue, the bottom left square is green, the bottom right square is red.

Question

From the starting position, what colours will the top-left square be after each of the instructions 1R, 2R, 2R, and 3R are followed in order?

  1. Red Green Blue Green Yellow
  2. Red Blue Green Blue Red
  3. Red Blue Yellow Red Green
  4. Red Red Yellow Red Blue

Answer

(B) Red Blue Green Blue Red

Explanation of Answer

The top-left square is Red for the starting position and the results after each rotation are shown below.

The top left square is blue, the top right square is red, the bottom left square is yellow, and the bottom right square is green. The squares row by row from left to right are coloured green, yellow, red, and blue. The squares row by row from left to right are coloured blue, red, yellow, and green. The squares row by row from left to right are coloured red, green, blue, and yellow.

Connections to Computer Science

This problem involves following a series of steps and keeping track of the current state. The state could be what the current orientation looks like, or only what is in the top-left corner (which can be used to determine the position of the other three colours). The ordered sequence of instructions is an algorithm. The ability to execute algorithms and remember state is the defining property of a computer.

This problem also involves simplifying and applying reasoning, since a rotation by two 2R rotations, or 1R plus 3R rotations (for a total of 4R rotations) will yield the game in the same orientation as it started.

Country of Original Author

Canada

Beaver Graffiti

Story

Beaver graffiti consists of three different symbols: fish, flower, and leaf.

Sequences of symbols are built using two steps:

  1. One of the symbols is drawn once or twice.
  2. One of the symbols is is drawn once to the left of the current sequence and once to the right of the current sequence.

Step 1 happens first and exactly one time. Step 2 may happen any number of times. Here are five examples:

Question

Which of the following is not an example of beaver graffiti?

  1. fish fish fish
  2. flower leaf fish leaf flower
  3. leaf flower fish leaf leaf fish flower leaf
  4. leaf leaf leaf leaf fish leaf leaf leaf