а)  Рас­по­ло­жим дву­знач­ные числа в клет­ках пря­мо­уголь­ни­ка вы­со­ты 9 и ши­ри­ны 10 (по го­ри­зон­та­ли от­кла­ды­ва­ем еди­ни­цы, по вер­ти­ка­ли  — де­сят­ки). Каж­дой по­пыт­ке Гриши со­от­вет­ству­ет кре­стик из пяти кле­ток: в цен­тре на­зван­ное им число, а по бокам че­ты­ре числа, от­ли­ча­ю­щи­е­ся в одной цифре на еди­ни­цу (если на­зван­ное число со­дер­жит цифру 0 или 9, не­ко­то­рые клет­ки кре­сти­ка вы­хо­дят за края пря­мо­уголь­ни­ка; таким клет­кам ни­ка­кие числа не со­от­вет­ству­ют). За­да­ча Гриши  — по­крыть пря­мо­уголь­ник 9 × 10 та­ки­ми кре­сти­ка­ми. Убе­дим­ся, что 18 кре­сти­ков ему не хва­тит. Сум­мар­ная пло­щадь кре­сти­ков равна 18 × 5  =  90, т. е. равна пло­ща­ди пря­мо­уголь­ни­ка. Но, по­кры­вая уг­ло­вую клет­ку, мы не­из­беж­но вый­дем за пре­де­лы пря­мо­уголь­ни­ка, и эта по­те­ря по­ме­ша­ет по­крыть весь пря­мо­уголь­ник.

б, в)  Решим сразу пункт в)  — убе­дим­ся, что 22 по­пы­ток хва­тит. По­кры­тие из 22 кре­сти­ков легко найти, если за­ме­тить, что кре­сти­ка­ми можно вы­ло­жить плос­кость без пе­ре­кры­тий (прав­да, придётся ещё до­ба­вить не­сколь­ко кре­сти­ков по краям пря­мо­уголь­ни­ка). На­при­мер, Гриша может на­звать числа 11, 13, 17, 25, 29, 30, 32, 37, 44, 49, 51, 56, 63, 68, 70, 75, 82, 87, 89, 90, 94, 97.

При­ме­ча­ние Алек­сандра Ива­но­ва.

Да­вай­те рас­смот­рим пред­ло­жен­ную кар­тин­ку. Пря­мо­уголь­ник за­мо­щен фи­гу­ра­ми раз­ной формы: крест (5 кле­ток), Т-⁠об­раз­ный (4 клет­ки), трех­кле­точ­ные (уг­ло­вые и пря­мые), двух­кле­точ­ные фи­гу­ры и две оди­ноч­ные клет­ки.

Услы­шав «хо­лод­но», мы (Гриша) сразу от­бра­сы­ва­ем все клет­ки на­зван­ной фи­гу­ры, услы­шав «тепло»,  — на­чи­на­ем про­ве­рять. Для про­вер­ки раз­ных фигур тре­бу­ет­ся раз­ное мак­си­маль­ное ко­ли­че­ство до­пол­ни­тель­ных ходов: для кре­ста  — 3 хода, для Т-⁠об­раз­но­го и трех­кле­точ­ных фигур  — 2 хода, для двух­кле­точ­ных  — 1 ход.

Стра­те­гия со­сто­ит в сле­ду­ю­щем.

Сна­ча­ла на­зы­ва­ем числа, со­от­вет­ству­ю­щие кре­стам, по­сколь­ку для них тре­бу­ет­ся боль­ше про­ве­роч­ных ходов: 25, 32, 37, 44, 51, 56, 63, 68, 75, 82, 87 (всего 11 чисел). Если мы услы­ша­ли «тепло», то для уга­ды­ва­ния числа нам по­тре­бо­ва­лось мак­си­мум 11 + 3  =  14 ходов, если же всё время мы слы­ша­ли «хо­лод­но», то мы по­тра­ти­ли 11 ходов и ис­клю­чи­ли 55 чисел.

Далее на­зы­ва­ем числа, со­от­вет­ству­ю­щие Т-⁠об­раз­ным и трех­кле­точ­ным: 11, 13, 17, 29, 30, 49, 70, 89, 94 (таких чисел 9). Если мы те­перь услы­ша­ли «тепло», то для уга­ды­ва­ния числа нам по­тре­бо­ва­лось мак­си­мум 11 + 9 + 2  =  22 хода (Ура!!!), если же всё время мы и те­перь слы­ша­ли «хо­лод­но», то мы по­тра­ти­ли 11 + 9  =  20 ходов и ис­клю­чи­ли 55 + 31  =  86 чисел.

Далее на­зы­ва­ем число 90, это был два­дцать пер­вый ход. Если слы­шим «тепло», то про­ве­ря­ем одним ходом и от­га­ды­ва­ем число за 21 + 1  =  22 хода (Ура!!!), а если слы­шим «хо­лод­но», то вы­чер­ки­ва­ем еще 2 числа. Итого вы­черк­ну­то 86 + 2  =  88 чисел, за 21 ход. Оста­лось два не­вы­черк­ну­тых числа.

ФИНАЛ (по­след­ний, 22-⁠й ход): на­зы­ва­ем число 96. Если «тепло», то за­га­да­но число 96, если «хо­лод­но», то за­га­да­но число  98. УРА!!!

Таким об­ра­зом, Гриша (с нашей по­мо­щью), при пра­виль­ной стра­те­гии мак­си­мум за 22 хода обя­за­тель­но от­га­да­ет за­ду­ман­ное Лёшей дву­знач­ное число.