Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Silk Road Mathematics Competition

Given a positive integer nn. Let us call by a word any sequence of nn letters of an alphabet. Define the distance ρ(A,B)\rho(A, B) between the words A=a1a2...anA = a_1a_2...a_n and B=b1b2...bnB = b_1b_2...b_n as the number of positions in which they differ (i.e. the number of indices ii for which aibia_i \ne b_i). We say that the word CC lies in between the words AA and BB if ρ(A,B)=ρ(A,C)+ρ(C,B)\rho(A, B) = \rho(A, C) + \rho(C, B). What is the largest number of words can be chosen so that among every three of them there is a word that lies in between the other two?

Solution

Answer: n+1n+1 for n2n \ne 2 and 44 for n=2n = 2.
For n2n \ne 2, take all words consisting only of letters aa and bb, in which each letter aa to the left of each letter bb, and for n=2n = 2 the words aa,ab,ba,bbaa, ab, ba, bb.

Let us prove that more words can not be chosen. Consider two selected words AA and BB, located at the largest distance mm. Suppose that the selected word CC is from AA at a distance k>0k > 0. Then ρ(B,C)\rho(B, C) is equal to the sum or difference of ρ(A,B)=m\rho(A, B) = m and ρ(A,C)=k\rho(A, C) = k and does not exceed mm, hence ρ(B,C)=mk\rho(B, C) = m - k. Now, if some selected word CCC' \ne C is also from AA at distance kk, we can assume without loss of generality km/2k \ge m/2 (otherwise, we can swap AA and BB). The distance between CC and CC' can not be equal to kk=0k - k = 0, therefore, it is equal to k+kmk + k \ge m, and hence k=m/2k = m/2.

So, we have that for each kk, 0km0 \le k \le m, except, perhaps, for k=m/2k = m/2, among the selected words no more than one, located from AA at distance kk. The selected words, which are at a distance of m/2m/2 from AA, are no more than 2 (we showed that the distance between any two such words is mm, therefore none of the three words lies between the two others).

It remains to check that if m>2m > 2 and two words are chosen at a distance k=m/2k = m/2 from AA, then there are at most 4 words. Indeed, let ρ(A,C)=ρ(A,C)=k=m/2\rho(A, C) = \rho(A, C') = k = m/2, and we have chosen some other word DD. As in the previous argument, we can assume without loss of generality that ρ(A,D)=s<k\rho(A, D) = s < k. Then ρ(B,D)=2ks\rho(B, D) = 2k - s and ρ(D,C)=ρ(D,C)=ks\rho(D, C) = \rho(D, C') = k - s (the distance between DD and CC can not be equal to the sum ρ(B,D)+ρ(B,C)=2ks+k>2k\rho(B, D) + \rho(B, C) = 2k - s + k > 2k, so it is equal to

the difference ρ(B,D)ρ(B,C)\rho(B, D) - \rho(B, C)). It turns out that among the three distances ks,ks,2kk-s, k-s, 2k, the words D,C,CD, C, C' are not equal to the sum of the other two, a contradiction.
This proves the estimate: if m>2m > 2, then for each knk \le n there is at most one selected word at a distance of kk from AA, and there are no more than n+1n+1 words in total, and if m=1m = 1 or 22, then there are no more than 4 words.

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 and solution reproduced as published; topic and difficulty added by this site.