# Covering the integers by two kinds of three-element sets (IMO Shortlist 2001 problem C4): extensions and generalizations?

As a straightforward generalization of IMO Shortlist 2001 problem C4, we can show the following fact:

Let $u$ and $v$ be two positive integers. A set of three integers $\left\lbrace x,y,z\right\rbrace$ with $x < y < z$ is called historic if $\left\lbrace z-y,y-x\right\rbrace =\left\lbrace u,v\right\rbrace$. Then, the set of all nonnegative integers can be written as a union of pairwise disjoint historic sets.

This is considered a medium-difficulty exercise, and the solutions avaliable online are basically one solution in different writeups (ok, 3 and 4 aren't even different).

As far as I understand, this solution doesn't answer any of the following

Questions:

(1) Is there a periodic way to write the set of all nonnegative integers as a union of pairwise disjoint historic sets? Equivalently, is there a function $f:\left\lbrace 0,1,2,...\right\rbrace \rightarrow\mathbb{N}$ such that $\left\lbrace x\in\left\lbrace 0,1,2,...\right\rbrace \mid f\left( x\right) =d\right\rbrace$ is a historic set for every $d\in\mathbb{N}$, and such that $f\left(x+u\right)=f\left(x\right)+v$ for some fixed positive integers $u$ and $v$ and all sufficiently large $x$ ? Actually, I believe that the answer is yes here, as can be deduced from the above problem using an additional argument.

(2) Is there a purely periodic way to do this? Equivalently, is there a function $f:\left\lbrace 0,1,2,...\right\rbrace \rightarrow\mathbb{N}$ such that $\left\lbrace x\in\left\lbrace 0,1,2,...\right\rbrace \mid f\left( x\right) =d\right\rbrace$ is a historic set for every $d\in\mathbb{N}$, and such that $f\left(x+u\right)=f\left(x\right)+v$ for some fixed positive integers $u$ and $v$ and all $x$?

(3) Is there a positive integer $n$ such that the set $\left\lbrace 0,1,2,...,n\right\rbrace$ is a union of pairwise disjoint historic sets?

(4) What happens if we start with three positive integers $u$, $v$, $w$, and call a set of four integers $\left\lbrace x,y,z,t\right\rbrace$ with $x < y < z < t$ historic if $\left\lbrace t-z,z-y,y-x\right\rbrace =\left\lbrace u,v,w\right\rbrace$ ?

I would not be surprised to see very easy counterexamples to some of these questions, yet I have not been able to find one myself. The same holds for proofs (no progress since 2008).

• Am I misunderstanding? A historic set has exactly 3 elements. If the set of $x$ such that $f(x)=d$ is historic, then $f$ takes on the value $d$ exactly 3 times. So how can $f$ be periodic? Also, in (4), I think you are overloading $w$. – Gerry Myerson Jul 17 '11 at 2:39
• As the author of the original problem I can add a spot of historical data. I believe the problem arises out of a result mentioned in Golomb's book on Polyominos (which regrettably I don't have access to just at the moment to check). I think the answer to (1) is definitely yes using a finite state automaton argument. Obviously yes to (3) implies yes to (2) (if I'm reading it correctly), and I also believe the answer to (3) is yes, but have never quite managed to convince myself of that. – Michael Albert Jul 19 '11 at 3:55
• Further to my previous comment concerning (3). I just did a long overdue experiment and can report that for 0 <= u, v <= 30, gcd(u,v) = 1 (obviously the only case we need to worry about) and u + v <= 30, the answer to (3) is yes. Moreover, the method of the standard solution (greedily use tiles of one type so long as you can, and whenever necessary use one of the other type) seems to produce such a tiling. The worst case in this range was u = 9, v = 20, which required 1638 tiles before tiling an interval. – Michael Albert Jul 20 '11 at 2:38
• Here at the IMO, I have spoken with Ilya Bogdanov about the problem, and he told me that the tiling constructed with the greedy algorithm can be "reconstructed" again from the right to the left with the same greedy algorithm "the other way round". This apparently yields (2) and (3). I am far from understanding this, however. Thanks Michael for the checking! – darij grinberg Jul 21 '11 at 10:01
• Excellent, this means I don't have to construct that argument myself. The basic idea must be this -- we have a 'state' which consists of the first empty square plus the next u+v (plus or minus one) squares. The greedy tiling gives a transition between states. If this is invertible, i.e. we can read the old state from the new one, then the first repeated state must be the initial state (of all empty squares), and hence we will have covered an initial segment. – Michael Albert Jul 21 '11 at 22:28