title: "IMO 1989 SL 11" description: "Define sequence an by " date: "2026-05-29T15:05:12+07:00" tags: ["imo", "shortlist", "mathematics", "olympiad"] categories: ["mathematics"] year: 1989 type: "shortlist" number: 11 origin: "HUN" weight: 198900011 draft: false

IMO 1989 SL 11

Origin: HUN

Problem

Define sequence an by  d|n ad = 2n. Show that n|an.

Solution

Call a binary sequence S of length n repeating if for some d | n, d > 1, S can be split into d identical blocks. Let xn be the number of nonrepeating binary sequences of length n. The total number of binary sequences of length n is obviously 2n. Any sequence of length n can be produced by repeating its unique longest nonrepeating initial block according to need. Hence, we obtain the recursion relation  d|n xd = 2n. This, along with x1 = 2, gives us an = xn for all n. We now have that the sequences counted by xn can be grouped into groups of n, the sequences in the same group being cyclic shifts of each other. Hence, n | xn = an.