Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
    
Thanks Gerry! Fixed these now. –  darij grinberg Jul 17 '11 at 8:45
1  
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
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.