2020 Beaver Computing Challenge

(Grade 9 & 10)

*Questions, Answers,
Explanations, and Connections*

A skyline consists of 14 towers as shown. The height of a tower is measured from the bottom of its base to its highest point, including any flagpoles or antennas.

If the towers are listed from shortest to tallest, which tower would be 10th in the list?

(A)

Notice that the skyline consists of one sequence of towers that gets taller from left to right followed by a second sequence of towers that gets taller from left to right. Also notice that the last two towers in each of these sequences make up the four tallest towers overall. (This did not have to be true. It could have been the case, for example, that the four tallest towers were all at the end of one of the two sequences.)

Since there are 14 towers in total, if we ignore the four tallest towers, the tallest remaining tower will be 10th in the list. The tallest remaining tower is the one in Option A.

In this task, you are asked to determine which tower would be the 10th in a list of towers if all the towers were ordered by height. Arranging items in order is called *sorting*.

There are many well-known sorting algorithms and this task is related to the *mergesort algorithm*. The key idea behind this technique is to separately sort the two halves of the items. Then you must *merge* these two sorted lists to produce one completely sorted list. If you chose to solve this problem by sorting all 14 towers, then you could have been merging the sorted towers in the left half with the sorted towers in the right half.

Canada

Beavertown Library has only a small pile of books. When a beaver wishes to borrow a book, they take the book that is on the top of the pile and record their name. When a beaver returns a book, they place their book on the top of the pile and record their name again.

At the beginning of the week the pile of books was arranged as shown:

The libraryâ€™s records at the end of the week show the following information:

Which book did Cato borrow?

- Charlotteâ€™s Web
- Curious George
- Go, Dog, Go!
- The Hobbit

(B) Curious George

At the beginning of the week, Alba borrowed a book and then Felix borrowed a book. Looking at how the books were arranged at the beginning, this tells us that Alba borrowed Charlotteâ€™s Web and Felix borrowed Curious George.

At the end of the week, Cato borrowed a book immediately after Felix returned a book. Since books are taken from the top of the pile and returned to the top of the pile, this means Cato borrowed the same book that Felix returned. Since Felix borrowed only one book that week, we know that he must have returned Curious George. Thus, Cato borrowed Curious George.

It is interesting to notice that we do not need to consider all of the books that were borrowed and returned. For example, it does not matter which book Marta borrowed.

In this problem, you are asked to keep track of which books are
available as they are borrowed and returned. The key property is that
the last book returned is the first book that must be borrowed the next
time someone borrows a book. We say that this follows the *last-in
first-out* or *LIFO* principle.

In computer science, a collection of items that follows this principle
is called a *stack*. It is one fundamental way that a collection
can be stored. In particular, a *computer program* will often be
broken into smaller pieces called *subroutines*. The order in
which these subroutines are executed is often determined using a stack.
Another example of a stack is a web browserâ€™s back button: the last page
visited is the first page revisited when the back button is pressed.

Canada

Five different chests are engraved with letters as shown:

Each chest has a key labelled with digits corresponding to the chestâ€™s engraved letters. Each digit always corresponds to the same letter.

The keys fell on the floor and one label was lost:

What is the lost label?

- 496
- 639
- 436
- 649

(A) 496

Chest BEB is the only one where the first and the third letter match. So, this chest matches key 636, which is the only key where the first and third digit match. So we know that the letter B corresponds to the digit 6 and the letter E to the digit 3.

Letter |
A | B | E | R |
---|---|---|---|---|

Digit |
Â | 6 | 3 | Â |

Chest AER is the only one that ends with a letter other than B. So, this chest matches key 934, which is the only key that ends with a digit other than 6. Thus, the letter A corresponds to the digit 9 and the letter R to the digit 4.

Letter |
A | B | E | R |
---|---|---|---|---|

Digit |
9 | 6 | 3 | 4 |

Now that we know all the letter-digit pairings, we can match the remaining chests to keys, and discover that chest RAB matches key 496, which is missing.

*Cryptography* is an area of study that lies at
the intersection of computer science and mathematics. The mapping
between digits and letters in this task is based on the
*monoalphabetic substitution cipher* example called
the *Vatsyayana cipher*. The idea came from an
Indian text from the 4th century AD. The Vatsyayana cipher creates
unique pairs for the alphabet letters â€“ a letter always matches another
letter and each letter can be used only in one pair. During
*encryption* of an original message one letter is
directly substituted by a paired letter. Interestingly, the exact same
process is used to *decrypt* the message. By
directly substituting a letter in the encrypted message with its paired
letter, the original message can be retrieved. This encryption method is
easy to crack as, once someone is sure about a letter pair(s), they can
decrypt all other pairs.

Modern cryptographic techniques, such as those that are used for banking transactions through the internet, use much more advanced computational methods that rely on the difficulty of hard mathematical problems, such as factoring a number which has two very large prime factors.

Cyprus

Dani is required to entirely fill as many empty water bottles as possible using a 50 litre tank.

Suppose she is given the following 10 empty bottles where each bottle is labelled with the number of litres it can hold.