The positive integers are colored with black and white such that: - There exists a bijection from the black numbers to the white numbers, - The sum of three black numbers is a black number, and - The sum of three white numbers is a white number. Find the number of possible colorings that satisfies the above conditions.
Problem
Source: 2012 Indonesia Round 2.5 TST 2 Problem 2
Tags: combinatorics proposed, combinatorics
22.05.2012 08:38
Assuming that the sum of three not necessarily distinct black numbers is black and similar for white: Well, if $a$ is black, $a+a+a=3a$ is black. Also $3a+a+a=5a$ is black, $5a+a+a=7a$ is black, and so on. If $a$ is black, $ax$ where $x$ is odd is black, and similar for white. Consequentially, if a number is black, the highest power of $2$ dividing it must be black, as if it were white, the number would be white. Then it only matters what color the powers of $2$ are. Now, if $2^a$ and $2^{a+1}$ are the same color (WLOG black), then $2^a+2^a+2^{a+1}$ is black, and all the bigger powers of $2$ are black by induction. In order to not have something like that for values less than $2^a$, $2^{a-1}$ must be white, $2^{a-2}$ black, etc. Then $2^{a-3}+3*2^{a-3}+2^{a-1}$ will be white, but it's black, contradiction, so $a=2$, $a=1$, or $a=0$. If $a=0$, we have the all-black coloring. Similarly, we derive the all-white coloring and get two possibilities. If $a=2$, the only things that are white are those divisible by $2$, but not by $4$. This satisfies the conditions. The other case with the whites and blacks switched gives 2 possibilities. If $a=1$, the only things that are white are those that are odd. This satisfies the conditions. Once again, 2 possibilities using symmetry. In all, we have 6 possible colorings.
22.05.2012 16:25
yugrey wrote: If $a=0$, we have the all-black coloring. Similarly, we derive the all-white coloring and get two possibilities. But there doesn't exist a bijection from black numbers to white numbers. yugrey wrote: If $a=2$, the only things that are white are those divisible by $2$, but not by $4$. This satisfies the conditions. The other case with the whites and blacks switched gives 2 possibilities. But then $1+1+4$ should be black, but $6$ is white according to your coloring. My solution: WLOG $1$ is black. Hence inducting, we get $1+1+k = k+2$ black for all odd $k$. Hence all odd numbers are black. Suppose there exists a black even number; by well-ordering principle there exists a minimum black even number $m$. Hence inducting again, we get $1+1+k = k+2$ black for all even $k \ge m$. Since we assumed $m$ is the minimum black even number, then all even numbers below $m$ must be white. Hence there are $\dfrac{m-2}{2}$, a finite quantity of white numbers. But there are infinitely many odd numbers, and hence infinitely many black numbers. Hence a bijection cannot exist from black numbers to white numbers. Hence the assumption that there exists a black even number is false, and hence all even numbers are white. If we let $1$ to be white instead, we get the exact opposite coloring: white odd numbers and black even numbers. Hence in total there are $\boxed{2}$ possible colorings.