Wednesday, 24 November 2010

A short nice maths question

Today is the sports day and I managed to deal with a Putnam 2005 paper.

Putnam 2005 A1:
Show that every positive integer is a sum of one or more numbers of the form 2^r(3^s) where r and s are nonnegative integers and no summand divides another. e.g., 23=9+8+6.

1)What if "no summand divides another" is not nessary?
Then the answer is obvious: express them in binary form. e.g. 31 = 11111_2 = 16+8+4+2+1

2)Then?
Then the answer is not unique.

3)So any approach to attain "no summand divides another"?
Draw a square table, the horizontal row represents power of 3 and vertical row represents powers of 2.
e.g. A23 = 3^2 * 2^3 = 72

4)What's its significance?
If we say a=2^i 3^j and b=2^k 3^l is "one divdes another" (a>b), then i>= k and j >=l. Then in the table drawn, if the elements Amn is chosen then  all elements in the left-top and right-bottom quartile can't be chosen. Then we can eliminate our choice once a number is chosen.

5)What's your alogarithm?
-If it's odd, subtract it with the biggest possible powers of 3.
-If it's even, divide by 2.
-If it's power of 2, subtract by itself.
Repeat the above two step until it's zero.
e.g.
21 - 9 => 12
12/2 => 6
6/2 => 3
3-3 => 0
Then we have 21=9+2(2(3)) = 9+12
e.g.2
77 - 27 = 50
50/2 = 25
25 - 9 = 16
16-16=0
77 = 27 + 2(9+16) = 27+18+32

6)Why this works?
Refer to the table, when it's multiplied by 2 and less power of three, it's the left-bottom quartile choice, so it is possible.
We see this alogarthim does not have any limitation on numbers, so we're done.

7)Any simplified representation like binary representation?
We don't see any simplified and possible representation since the sum is not ordered (by this alogarithm)
e.g. 77 = 27+18+32, it has decreasing powers of 3, but in the same power of 3 there may be more than one powers of 2.
e.g. 77 = 27 + 18+32, 61 = 27+18+16.

8) Is this unique?
No, 95 = 27+36+32 = 81 + 8 + 6.

Foods for thought:
If it isn't 2^r 3^s but other base, like 3^r 5^s, can it represents all numbers?

No comments:

Post a comment