Let's say we have a nice representation of the positive integer $ n$ if we write it as a sum of powers of 2 in such a way that there are at most two equal powers in the sum (representations differing only in the order of their summands are considered to be the same). a) Write down the 5 nice representations of 10. b) Find all positive integers with an even number of nice representations.
Problem
Source: Central American Olympiad 2000, problem 6
Tags: induction, strong induction
basketball9
18.02.2010 20:27
$ 2^0+2^0+2^3$
$ 2^2+2^1+2^1+2^0+2^0$
$ 2^2+2^2+2^1$
$ 2^-1+2^-1+2^2+2^2+2^0$
$ 2^-1+2^-1+2^2+2^2+2^0$
Arrange your tan
18.02.2010 21:12
basketball9 wrote:
$ 2^0 + 2^0 + 2^3$
$ 2^2 + 2^1 + 2^1 + 2^0 + 2^0$
$ 2^2 + 2^2 + 2^1$
$ 2^ - 1 + 2^ - 1 + 2^2 + 2^2 + 2^0$
$ 2^ - 1 + 2^ - 1 + 2^2 + 2^2 + 2^0$
EDIT: No, your last two are repeated. I got five representations (between us) when the exponent on a $ 2$ is limited to being nonnegative. Use braces around the negative ones in the exponents. You are missing:
$ 2^1 + 2^3$
$ 2^0 + 2^0 + 2^2 + 2^2$
After looking at it further, I see no limit to the number of "nice" representations for $ 10$ when the exponents can be negative.
$ 2^{ - 2} + 2^{ - 2} + 2^{ - 1} + 2^0 + 2^3$
$ 2^{ - 3} + 2^{ - 3} + 2^{ - 2} + 2^{ - 1} + 2^0 + 2^3$
And so on.
Keep splitting up the lead value of $ 1$ into sums of fractions
where the $ 2$ is raised to certain negative exponents.
NuncChaos
28.12.2010 02:48
So far for part B I got all odd powers of $2$ and all integers $n=2^{2k}-1$ for nonnegative integer $k$. But I realizie there's a lot more...
JaMoS
24.03.2011 20:01
I am going to take the question as meaning nonnegative powers, since otherwise part a makes no sense. Part a has been done, here is part b: Let $k(n)$ denote the number of ways that n can be made permitted by the question, and let $f(n)$ be $k(n)$ reduced modulo 2. I will work only with $f$, although it is the same to use $k$. Now, $f(1) = 1$, $f(2) = 0$. I will now generate two recurrences for $f$. Suppose $n = 2m + 1$ is odd. Then there must be exactly one $2^0$ occurrence, by parity. Then, we have the rest being a representation of $2m$ using no $2^0$s. By dividing through by 2, we can see this is exactly equal to the number of representations of $m$. Therefore, $f(2m+1) = f(m)$. Suppose $n = 2m$ is even. If there are no $2^0$ occurrences in a representation, then we have $f(m)$ ways as before. If there are two $2^0$ occurrences, subtract two, and we have the number of representations of $2m - 2$ using none of $2^0$, or rather we have $f(m-1)$ ways like this. Therefore, $f(2m) \equiv f(m) + f(m-1) 2$ mod 2. Finally, I will show by strong induction that $f(n)$ is zero for $n \equiv 2$ mod 3. Note that $2m+1 \equiv 2$ iff $m \equiv 2$ mod 3, and $2m \equiv 2$ iff $m \equiv 1$ iff $f(m) = f(m-1)$. Therefore, it is obvious by strong induction. QED.