Market Vendor Puzzle for Sep 28

 

A more organized summary. Reading the comments as you work down the columns
is helpful!

So the set of number is {1,3,9, 27}. Powers of 3. Curious.

Solving it for the first time

Minimal set of number to sum to each of {1,..,31}?

A moments thought shows that we certainly need 1, 2 and 4. Then we can get up to 7, so we need 8.

Using the set {1,2,4,8} we can get up to 15, which means we need 16. Thus, selecting from {1,2,4,8,16} we can sum to every number in the set {1,2,...,30,31}.  Now powers of 2... strange.

A useful way to approach the problem:

Thinking of this problem recursively is best. Suppose we can sum to all the number less than say n. If we add n to the collection, we get up to 2n-1. 

Extending... Why powers of 3? Why powers of 2?

The first thing to know is that in ternary, 40 is written as 1111=1000+100+10+1, which represent individual weights. In binary 31 is written as 11111 = 10 000 + 1000 + 100 + 10 + 1, which also represent individual weights. In a high school math class, this would be a great way to introduce working in different bases, and what it really means, instead of just providing a key to convert between the two.

Teaching Recursion

This is also an opportunity to teach an intro to recursion. Let's derive the sequence of numbers for the original problem:

Let tn be the sequence of weights needed. In our sequence: starting with 1,3, we get the next number with the following logic: 2(1+3) +1 = 9. Let Sn represent the sum of the previous numbers in the sequence. Then we have

t_{n} = 2S_{n-1} +1

t_{n+1} = 2(t_n + S_{n-1})+1

Solving the system by taking t_{n+1}-t_n gives t_{n+1}=3t_n.

This is the recurrence relation for t(n) = 3^n for n=0,1,2,... .