18-ші «Жібек жолы» математикалық олимпиадасы, 2018 жыл

Натурал $n$ саны берілген. Сөз деп қандай да бір алфавиттің әріптерінен құралған, ұзындығы $n$ болатын әріптер тізбегін айтамыз. Екі $A=a_1a_2 \ldots a_n$ және $B=b_1b_2 \ldots b_n$ сөздерінің $\rho(A, B)$ ара-қашықтығы деп, олардың сәйкес разрядтарындағы айырмашылықтар санын айтамыз (яғни $a_i\ne b_i$ шартын орындайтын $i$-дің жалпы саны). Егер $\rho (A,B)=\rho(A,C)+\rho(C,B)$ шарты орындалса, онда $C$ сөзі $A$ мен $B$ сөздерінің арасында жатыр дейміз. Кез келген үш сөздің қандай да біреуі қалған екеуінің арасында жататындай ең көп дегенде қанша сөз таңдауға болады? ( А. Голованов )