Two nonnegative integers $a$ and $b$ are tuanis if the decimal expression of $a+b$ contains only $0$ and $1$ as digits. Let $A$ and $B$ be two infinite sets of non negative integers such that $B$ is the set of all the tuanis numbers to elements of the set $A$ and $A$ the set of all the tuanis numbers to elements of the set $B$. Show that in at least one of the sets $A$ and $B$ there is an infinite number of pairs $(x,y)$ such that $x-y=1$.
Problem
Source: Spanish Communities
Tags: modular arithmetic, number theory proposed, number theory
20.09.2007 14:49
I believe the problem was originally stated so that the translated version may be misinterpreted. The original problem stated that $ A$ and $ B$ are such that $ B$ is the set of numbers, such that each of them is tuani to all numbers in $ A$, and $ A$ is the set of numbers such that each of them is tuani to all numbers in $ B$...
05.08.2009 00:44
daniel73's is right. This was not the original problem. Here is my solution to the original problem: Suppose that $ A$ contains two numbers $ a$ and $ a'$ such that $ a\not\equiv a' \pmod {10}$. Being $ b$ an element of $ B$ we have wlog that $ b+a\equiv 0 \pmod{10}$ and $ b+a'\equiv 1 \pmod{10}$ because these numbers only contain $ 0$ and $ 1$ in their decimal expression. Consequently $ a'\equiv a+1 \pmod{10}$. If there is an element $ b'$ of $ B$ such that $ b\not\equiv b' \pmod{10}$ then $ b'+a\equiv 1 \pmod{10}$ (because $ b'+a\equiv 0 \pmod {10}\Rightarrow b'\equiv b\pmod{10}$) and $ b'+a'\equiv 0 \pmod{10}$ and so $ a\equiv a'+1\pmod{10}$. Contradiction! We then conclude that if not all numbers in $ A$ have the same residue modulo $ 10$ then all elements in $ B$ have the same residue modulo $ 10$. Suppose now wlog that all numbers in $ B$ have the same residue modulo $ 10$. Choosing one number $ a$ in $ A$ we know that $ a$ is tuanis with all numbers in $ B$ and so, since these all have the same residue modulo $ 10$ we obtain that $ a+b$ always has $ 0$ as unit digit or always has $ 1$ as unit digit $ \forall \; b\in B$. If $ a+b\equiv 0 \pmod{10}\; \forall \; b\in B$ then $ a+1\in A$ because $ a+b+1$ only contains $ 0$ and $ 1$ in its decimal expression since $ a+b$ only contains $ 0$ and $ 1$ in its decimal expression and $ a+b$ has $ 0$ as unit digit $ \forall \; b\in B$. Analogously if $ a+b\equiv 1 \pmod{10}\; \forall \; b\in B$ then $ a-1\in A$. So we proved that if $ a\in A$ then $ a-1\in A \vee a+1 \in A$. As $ |A|=\infty$ we conclude that $ A$ contains an infinite of pairs $ (x,y)$ such that $ x-y=1$.