Competition problem — Combinatorics

Library / /113 of 196

Combinatorics Difficulty 5.3 AIME, harder Prove it Soviet Union

Problem:
A finite sequence of 0s and 1s has the following properties: (1) for any $i < j$ , the sequences of length 5 beginning at position $i$ and position $j$ are different; (2) if you add an additional digit at either the start or end of the sequence, then (1) no longer holds. Prove that the first 4 digits of the sequence are the same as the last 4 digits.

Solution

Solution:
Let the last 4 digits be $a b c d$ . Then the 5 digit sequences $a b c d 0$ and $a b c d 1$ must occur somewhere. If neither of them are at the beginning then there are three 5 digit sequences $x a b c d$ , two of which must therefore be the same, contradicting (1). Hence $a b c d$ are the first 4 digits.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.