2021 Beaver Computing Challenge

(Grade 5 & 6)

*Questions, Answers,
Explanations, and Connections*

## Part A

### Strawberry

#### Story

Anja makes a design on the ground using the following four types of
objects.

She then places sticks in her design according to her very important
rule:

*Sticks cannot be placed between objects that are the same
type.*

Here is Anjaâ€™s completed design:

Suddenly a bird swoops in and eats the ! Anja would like to avoid
having this happen again.

#### Question

If possible, Anja would like to replace the with a different type of
object, and without moving any sticks. Without breaking her very
important rule, which object can Anja replace the with?

- It is not possible. Only a could go there.

#### Answer

(D) It is not possible. Only a could go there.

#### Explanation of Answer

Unfortunately, Anja is not going to be able to replace the strawberry
with a different type of object, without breaking her very important
rule.

In Anjaâ€™s original design, the strawberry had sticks between it and every other
type of object. Changing the strawberry to anything other than another
strawberry would force a stick to exist between two objects of the same
type.

#### Connections to Computer
Science

Anjaâ€™s design is an example of a *graph*. The objects are the
*vertices* of the graph and the sticks are the
*edges* of the graph. Two objects that have a stick
between them, which is equivalent to two vertices that have an edge
between them, are called *neighbours*.

The problem that is being asked here is related to *graph
colouring*. That is, we try to determine how many colours are
needed so that every vertex is coloured a different colour than all of
its neighbours. The problem of how to colour a graph using the minimum
possible number of colours has many applications, such as scheduling
sports competitions, designing a seating plan, and even solving a Sudoku
puzzle.

#### Country of Original Author

Switzerland

### Overlapping Coins

#### Story

Emil has six different coins.

Emil placed the six coins on a table, one at a time. Some coins were
placed on top of other coins so that they overlap as shown.

#### Question

Which coin was the fourth coin that Emil placed on the table?

#### 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: