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 RecursionThis 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,... .
|
Your connection to recursion offers an interesting way to extend this puzzle beyond simply finding the weights. I wonder if students could first discover the relationship between consecutive weights through exploration and then develop the recursive formula themselves. This could make the formula more meaningful than introducing it directly.
ReplyDelete