4
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ Jul 17, 2011 at 2:39
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 19, 2011 at 3:55
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 20, 2011 at 2:38
  • $\begingroup$ 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! $\endgroup$ Jul 21, 2011 at 10:01
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 21, 2011 at 22:28

1 Answer 1

2
$\begingroup$

(4) This appears to be an open question! A partial solution just was posted on the arXiv:

Ilkyoo Choi, Junehyuk Jung, Minki Kim, On tiling the integers with 4-sets of the same gap sequence, arXiv:1605.03322v1.

This preprint also gives non-contest references for the original problem. One of these references is Chapter 8, Section 3 of Ross Honsberger's Mathematical gems. II.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.