Пункт а). Цве­тов не может быть боль­ше 42, иначе есть цвет, в ко­то­рый по­кра­шен толь­ко один дом, тогда домов этого этого цвета ни в каком от­рез­ке не может быть стро­го боль­ше, чем лю­бо­го дру­го­го. По­ка­жем при­мер на 42 цвета, то есть такую рас­крас­ку, что для каж­до­го цвета в него было по­кра­ше­но ровно два дома, при­том су­ще­ству­ет от­ре­зок из 20 домов, в ко­то­рый эта пара од­но­цвет­ных по­па­да­ет це­ли­ком, а любая дру­гая  — нет.

На­зо­вем 38-бло­ком сле­ду­ю­щую кон­струк­цию: под­ряд стоят 38 домов, пары домов на рас­сто­я­нии 19 (то есть такие, между ко­то­ры­ми ровно 18 дру­гих домов)по­кра­ше­ны в один цвет, и боль­ше этого цвета домов нет (не толь­ко в блоке но во­об­ще из участ­ву­ю­щих домов); 2-бло­ком на­зо­вем сто­я­щие под­ряд два дома, по­кра­шен­ные в уни­каль­ный цвет. 84 дома надо рас­кра­сить так: 2-блок, 38-блок, два 2-блока, 38-блок, 2-блок. Оста­лось до­ка­зать, что эта рас­крас­ка под­хо­дит, мы остав­ля­ем это чи­та­те­лю в ка­че­стве не­слож­но­го упраж­не­ния (но каж­дый участ­ник, ко­то­рый оста­вил это жюри в ка­че­стве не­слож­но­го упраж­не­ния, не­до­счи­тал­ся од­но­го балла).

Пункт б). Этот же при­мер поз­во­ля­ет ре­а­ли­зо­вать 42 цвета на 86 домах  — в конец до­ба­вим еще два дома, цвет ко­то­рых сов­па­да­ет с по­след­ним 2-бло­ком.

Оцен­ка. По­нят­но что каж­до­го цвета долж­но быть хотя бы два дома, зна­чит, ответ для не боль­ше 43. Если для ответ 43, то каж­до­го цвета ровно два дома. За­ну­ме­ру­ем цвета в по­ряд­ке их по­яв­ле­ния слева на­пра­во, и пусть дома i-го цвета имеют но­ме­ра и при­чем По опре­де­ле­нию До­ка­жем что Пред­по­ло­жим про­тив­ное, то есть для каких-то ока­за­лось Вспом­нив что и видим, что то есть любой от­ре­зок, со­дер­жа­щий a_i, b_i, также со­дер­жит a_i, b_i, то есть нет от­рез­ка, на ко­то­ром домов i-го цвета боль­ше всего  — при­ве­ли пред­по­ло­же­ние к про­ти­во­ре­чию.

До­ка­жем еще два по­лез­ных не­ра­вен­ства:   — иначе нет от­рез­ка из 20 домов, в ко­то­рый по­па­ли оба из a_i, b_i; и   — иначе каж­дый от­ре­зок, со­дер­жа­щий a_i, b_i, также со­дер­жит или или

Bce го­то­во для ре­ше­ния. Среди пер­вых 20 но­ме­ров ровно одна b-шка, это b₁: иначе, если там есть и b₂, среди домов от 1 до 20 есть два дома вто­ро­го цвета, тогда для пер­во­го цвета нет от­рез­ка, в ко­то­ром его боль­ше чем лю­бо­го дру­го­го (по­сколь­ку толь­ко от­ре­зок [1, 20] со­дер­жит два дома пер­во­го цвета, но он со­дер­жит и два дома вто­ро­го). Зна­чит, среди пер­вых 20 домов ровно 19a-шек. Зна­чит, из со­от­вет­ству­ю­щих им b-шек 18 лежат среди 19 но­ме­ров от 21 до 39, то есть там мак­си­мум одна a-шка, это может быть толь­ко Мы до­ка­за­ли, что По­вто­рив то же самое рас­суж­де­ние с дру­го­го конца, по­лу­чим, что Но это про­ти­во­ре­чит не­ра­вен­ству (част­ный слу­чай до­ка­зан­но­го выше для

Ответ: а)  42; б)  43.