Find all the pairs of integers $ (a,b)$ satisfying $ ab(a - b)\not = 0$ such that there exists a subset $ Z_{0}$ of set of integers $ Z,$ for any integer $ n$, exactly one among three integers $ n,n + a,n + b$ belongs to $ Z_{0}$.
Problem
Source: Chinese TST 2009 2nd quiz P2
Tags: modular arithmetic, algebra, polynomial, number theory, combinatorics proposed, combinatorics, Additive combinatorics
26.03.2009 08:18
It's my first time here, so sorry for any glaring deficiencies in my proof (most notably, how I cannot express how m and n are relatively prime). If anyone could correct them or give tips, that would be helpful. Label $ x$ as the middle integer of $ n$, $ n + a$, $ n + b$. $ x - m$ will be the smallest integer and $ x + o$ will be the greatest. If $ m = o$, clearly the condition will be satisfied with $ Z_0$ containing all integers $ 3km$, where k is an integer. So from now on we will work with $ m \neq o$. If $ m$ and $ o$ are not relatively prime, $ Z$ will be split into $ (m, o)$ sets? fields? rings? groups? whatever But each of these "bunches" of integers will only affect integers inside it, and shifting and dividing by $ (m, o)$ will result in our original problem with $ (m, o) = 1$. So assume m and n are relatively prime WLOG, as every non-relatively prime pair will only work if their relatively prime cousins work. There must be at least one integer in $ Z_0$. Call it $ f$. Take $ x = f$. $ f + o$ cannot be in $ Z_0$. Take $ x = f + m$. $ f + m$ and $ f + m + o$ cannot be in $ Z_0$. Take $ x = f + m + o$. $ f + m + 2o$ must be in $ Z_0$. Going left instead of right, we get that $ f - 2m - o$ must also be in $ Z_0$. If $ f$ is in $ Z_0$, so is $ f + m + 2o - 2m - o = f + o - m$, and therefore $ f + k (o - m)$ is in $ Z_0$, where k is an integer. $ (o - m, m + 2o) = (o - m, -2m - o) = (m - o, 3o) = (m - o, 3m) = (3o, 3m) = 3$ Assume one of $ m$, $ o$ is divisible by 3. (make it o because it does not matter) $ (o - m, 3o) = 3$. Thus, $ m$ must be divisible by three. However, this gives us $ (o, m) = 3$. Contradiction! Assume $ m + o = 0 \pmod{3}$. $ (m - o, 3o) = (m + 2o, 3o) = 3$, so that means m + 2o must be a multiple of 3. However, our assumption gives us that $ o$ is a multiple of 3, which by the lemma above cannot satisfy the given condition. Contradiction! So we have that neither $ m$, $ o$, nor $ m + o$ is divisible by 3. These are the three distances between the three integers $ x$, $ x - m$, $ x + n$, so none of them can have the same residue mod 3. We put every third integer into $ Z_0$, and as $ x - m$, $ x$, and $ x + n$ are $ 0$, $ 1$, and $ 2 \pmod{3}$, not necessarily in that order, this set will satisfy all m and n outlined above. This means that all integers $ a$, $ b$ such that neither $ a$, $ b$, nor $ a - b$ (the three distances) is a multiple of 3 work. To undo the relatively prime restriction, we multiply a and b by k, where k can be a multiple of three. Then $ Z_0$ can contain $ 3kc, 3kc + 1, 3kc + 2, \cdots 3kc + k - 1$. Thus, our answer is all integers $ a = ky$, $ b = kz$, where neither $ y$, $ z$, nor $ y - z$ is a multiple of 3.
26.03.2009 13:24
I'm sorry! it should be Chinese TST 2009 2nd quiz P2!
22.09.2011 06:34
Let $f(n)=1$ if $n\in Z_0$ and $0$ otherwise, so $f(n)+f(n+a)+f(n+b)=1$ for all $n\in\mathbb{Z}$. Then $f(n+b+1)-f(n+b)+f(n+a+1)-f(n+a)+f(n+1)-f(n)=0$ for all integers $n$, so by the Skolem-Mahler-Lech theorem the set of zeroes of $f$ is eventually periodic for sufficiently large $n>N$ and consequently purely periodic with period $\ell>0$ (easily seen by "reversing" the recurrence). Hence \[P(x)=\sum_{k=0}^{\ell-1}f(k)x^k\implies P(x)(1+x^{-a}+x^{-b}) \equiv 1+x+\cdots+x^{\ell-1} \pmod{x^\ell-1}.\]Modulo $x-1$ forces $3P(1)=\ell$, whence $\ell=3^r s$ for some $r\ge1$ and $\gcd(s,3)=1$. If $\gcd(x^{3^r}-1,1+x^{-a}+x^{-b})=1$, then \[\frac{x^{3^r}-1}{x-1} \bigg{|} P(x)\implies 3^r|P(1)=\frac{\ell}{3}=3^{r-1}s,\]a contradiction, so there exists some $1\le t\le r$ such that $\Phi_{3^t}(x) = 1+x^{3^{t-1}}+x^{2\cdot3^{t-1}} | 1+x^{-a}+x^{-b}$ (since cyclotomic polynomials are irreducible in $\mathbb{Q}[x]$). Now working in $\mathbb{Q}(\omega)[x]$ for $\omega=e^{2\pi i/3}$, we have $x^{3^{t-1}}-\omega | 1+x^{-a}+x^{-b}$, so if $-a=3^{t-1}a_1+a_2$ and $-b=3^{t-1}b_1+b_2$ for $0\le a_2,b_2<3^{t-1}$, then it's easy to see that $a_2=b_2=0$ and $\{a_1,b_1\}\equiv\{1,2\}\pmod{3}$. For the construction, taking $\ell=3^t$ and $P(x)=1+x+\cdots+x^{3^{t-1}-1}$ works. Also note that in general, if $X\subseteq\mathbb{Z}$ and $X+a = \{x+a | x \in X\}$, then assuming integers $a_i$ exist such that $X+a_1, \ldots , X+a_n$ partition $\mathbb{Z}$, there must also exist an integer $N$ such that $X = X+N$. I think this allows us to generalize the original problem to $f(n+a_1)+f(n+a_2)+\cdots+f(n+a_p)=1$ if $p$ is prime.
26.07.2013 06:24
Note that 2012 China TST Day 2 #3 actually reduces to a specific case of this problem (you are also given exactly one of $n$, $n-a$, and $n-b$ is in the set).
24.05.2020 18:58
Awesome solution of math154 to the problem! I wish to remark here math154 wrote: Then $f(n+b+1)-f(n+b)+f(n+a+1)-f(n+a)+f(n+1)-f(n)=0$ for all integers $n$, so by the Skolem-Mahler-Lech theorem the set of zeroes of $f$ is eventually periodic for sufficiently large $n>N$ and consequently purely periodic with period $\ell>0$ (easily seen by "reversing" the recurrence). as $f$ is given by a recurrence relation and takes values in a finite set, it’s automatically eventually periodic (the recurrence relation even doesn’t need to be linear), so we don’t need Skolem-Mahler-Lech. math154 wrote: I think this allows us to generalize the original problem to $f(n+a_1)+f(n+a_2)+\cdots+f(n+a_p)=1$ if $p$ is prime. Also let me put down a small step needed to run math154’s arguments for $p$, namely the fact that if $p$ powers of a $p^n$-th root of unity add up to $0$, then they divide the unit circle evenly. WLOG we may assume arguments of these powers are between $0$ and $2(p-1)\pi/p$, then since the minimal polynomial of a primitive $p^n$-th root of unity over $\mathbb{Q}$, i.e. the $p^n$-th cyclotomic polynomial has degree $p^{n-1}(p-1)$, these powers must correspond to terms of the cyclotomic polynomial and equal the $p$-th roots of unity.
05.08.2020 09:37
It's easy to check that if $n$ appears in the set, all integers congruent to $n$ (mod $a+b$) will be in set too. Suppose $S$ is the set of remainders mod $a+b$ wich appeared in the set; then the sets $S+a$ and $S+b$ and $S$ are disjoint and covering all remainders mod $a+b$. Thus $a+b$ is divisable by 3 and the rest is easy by claiming that if (a,b) is an answer, (a/3,b/3) is an answer too.
16.08.2020 19:54
This problem is very similar to IMO ShortList 1999, C6. One may see #8 there for a solution, using the Discrete Fourier Transform (DFT). The same approach can be applied here and it's even easier in my opinion. I decided to write something on DFT in my blog, and as an illustration to see how it works on both problems.