2021 Beaver Computing Challenge

(Grade 7 & 8)

*Questions, Answers,
Explanations, and Connections*

## Part A

### Butterflies

#### Story

A beaver is photographing butterflies, but after each photo is taken,
half the butterflies fly away.

The first photo has 64 butterflies in it and the last photo has 2
butterflies in it.

#### Question

How many photos did the beaver take?

- 6
- 63
- 4
- 32

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

1 |
64 |

2 |
32 |

3 |
16 |

4 |
8 |

5 |
4 |

6 |
2 |

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

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