Let $S=\{1,2,3,\ldots,2012\}.$ We want to partition $S$ into two disjoint sets such that both sets do not contain two different numbers whose sum is a power of $2.$ Find the number of such partitions.
Problem
Source: Turkey JBMO Team Selection Test Problem 2
Tags: induction, floor function, logarithms, combinatorics proposed, combinatorics
30.05.2012 11:48
Denote $S = A \cup B$, $A \cap B = \emptyset $. First we can prove the lemma by induction. Lemma: If we determine the position of ${2^0},{2^1},{2^2},...,{2^{n - 1}}$, so does $1,2,3,...,{2^n} - 1$. Hence if we determine the position of ${{2^0},{2^1},{2^2},...,{2^{10}}}$, then we determine the partition. So if $1 \in A$, there are $2^{10}$ such partitions.
02.02.2013 12:14
Another approach: Lemma:If 1 is in set A and 3 is in set B then set A contain all integer in form of $4k+1$ and set B contain all integer in form of $4k+3$. We prove this by induction. Assume this lemma is true for every $i \leq t$, if this is not true for $t+1$, for example $4(t+1)+1$ is in set B, then exists a number in set B such that it has the form $2^m - 4(t+1)-1$, contradiction! Hence the lemma is proved. Using this lemma, we can also prove that each set contain all numbers either in form of $2^{p+2}k+2^p$ or $2^{p+2}k-2^p$ but not both. Since $2012<2^{11}=2048$, then any number in the set can divisible by at most $2^{10}=1024$, so we have $2^{11}$ such partitions.
10.11.2013 03:31
03.05.2021 11:15
Claim: There is a unique way to partition the odd numbers. Proof: Trivial by induction.$\blacksquare$ Let $f(n)$ be the answer for the set $\{1,2,\dots , n\}$. We claim that $f(n) = 2^{\lfloor \log_2 n \rfloor}$. We will prove it by induction. It is easy to verify the base cases. Let it be true for $n$, we will prove it for $n+1$. Case 1: $n+1$ is odd. In that case, by our claim we have to have $f(n+1) = f(n)$ so this case is done. Case 2: $n+1$ is even but not a power of $2$. In that case, there is only one number that is less than $n+1$ such that when you add $n+1$ with it, you get a power of $2$. So there is a unique way to put $n+1$ in the sets. So we have $f(n+1) = f(n)$ in this case too. Case 3: $n+1$ is a power of $2$. In that case, there is no number that is less than $n+1$ such that when you add $n+1$ with it, you get a power $2$. So we have $f(n+1) = 2f(n)$ in this case. And thus, the claim is proven and the answer is $2^{10} = 1024$ for our case.$\square$
28.12.2024 19:57
Trying smaller cases like $1,2…10$ gives us the intuition that the answer for fixed $n$ is $2^{\lfloor log_2(n)\rfloor}$.Let’s prove it::: Assume it is true for $n$ there are $3$ cases::: 1)$n$ is even::: When we add $n+1$ which is odd,nothing changes and the function remains still.So $a_{n+1}=a_n$ in this case. 2)$n+1$ is even and has at least one odd prime divisor::: Notice that there is only one $k\in \{1,2…n\}$ s.t $k+n=2^a-1$.It is not hard to prove.So $a_{n+1}=a_n$ 3)$n+1$ is a power of $2$ It’s actually the opposite of the case two because we can not find such $k$ such that they sum up to $2^a$ so we can add it to all subsets in that case $a_{n+1}=a_n *2=2a_n$ Solving this reccurence relation isn’t that hard since the relation is related to the powers of 2 one can prove that $a_n= 2^{\lfloor log_2(n)\rfloor}$ $\lambda $