Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

Mady has an infinite number of balls and empty boxes available to her. The empty boxes, each capable of holding four balls, are arranged in a row from left to right. At the first step, she places a ball in the first box (the leftmost box) of the row. At each subsequent step, she places a ball in the first box of the row that still has room for a ball and empties any boxes to its left. How many balls in total are in the boxes as a result of Mady's th step?
Solution
After trying the first few steps, we notice that the boxes resemble the set of positive integers in quinary (base ). In particular, the first box corresponds to the units digit, the second corresponds to the fives digit, and so forth. An empty box corresponds to the digit and a box with balls, corresponds to the digit .

We need to verify that this is true. On the first step, the boxes represent the number . For the th step, suppose that the units digit of in quinary is not equal to , so that the first box is not full. The operation of adding in quinary simply increments the units digit of by . Indeed, Mady performs the corresponding operation by adding a ball to the first box. Otherwise, if the units digit of in quinary is equal to , suppose that the rightmost consecutive quinary digits of are equal to . Then, adding to entails carrying over multiple times, so that the th digit will be incremented once and the other digits will become zero. Mady does the same: she places a ball in the first available box (the th), and empties all of the previous boxes.

It follows that the number of filled boxes on the th step is just the sum of the digits in the quinary expression for . Converting this to quinary, the largest power of less than is , and that . Then, . Repeating this step, we find that so the desired answer is .
Final answer
6