45
Вероятно, многие из вас играли в лото или хотя бы слышали об этой игре. Предлагаем вам некоторое ее видимение. Как и в обычном варианте, главным предметом у нас является мешок с «бочонками», на которых написаны числа от 0 до 99. Правила игры таковы. Вам разрешается написать любое количество чисел от 0 до 99, каждое число не более одного раза. После этого из мешка вынимается один «бочонок». Если у какого-то из написанных вам чисел первая (или вторая) цифра совпадает с первой (соответствующего второй) цифрой вынутого числа, то ваше число получает 250 очков. Число, совпавшее с вынутом, получает 500 очков. Например, если вынуто число 95, то само оно получает 500 очков, числа 45 и 91 получают по 250 очков, а числа 59 и 04 не получают ничего (однозначные числа — 0, 1, 2, … — записьюются как двухначные — 00, 01, 02, …).
Чтобы лучше разобраться в правилах, давайте сыграм. У вас — листок бумаги и ручка, у меня — мешок с «бочонками». Например, на пиществе пару чисел. Я вынимаю 66. Сколько очков вы набрали? А сколько модели набрать? Видимо, не более 750. А какое наиболее количество чисел нужно написать, чтобы наверняка число-писью не нибудь набрать?
Не спешите, подумайте. Сколько у вас получилось? 10? Правильно. Например, можно написать числа 00, 01, 02, 03, …, 09, и тогда, какое бы число из мешка ни вынули, его вторая цифра совпадает со второй цифрой-одного из ваших чисел, а, значит, по крайней мере 250 очков вы получите. А меньшим количеством чисел не обойтись. Ведь если вы написете меньше десяти чисел, то найдет такая цифра a, которая не будет средней цифр ваших чисел, и такая цифра b, которая не будет средней цифр ваших чисел. А тогда если из мешка вынут «бочонок» с числом ab, вы не выиграете ничего.
Задача 1. Какое число было вынуто из мешка, если набор 07, 29, 45, 68, 84, 71, 32, 16, 53 ничего не получил?
А теперь вопрос потруднее.
Какое наиболее количество чисел нужно написать, чтобы наверняка число-писью не нибудь набрать?
Отвлечемся на минуту от лото и вспомним про шахматную доску и ладью, которая будет все поля, находящемся на одной горизонтали или одной вертикали с тем полем, на которой она стоит. Скажите, какое наиболее число ладей можно рассматривать на шахматной доске так, чтобы они не были другие другие?
46
Каждый, кто хоть немного знаком с шахматами, сразу ответит: конечно, восемь, например, как на рисунке 1.
Тогда еще один вопрос: пусть на доске расставлены 8 не быющих друг друга ладей. Сколько раз бется какое поле доски?
Если ладьи не быот друг друга, то они стоит на разных вертикальных и разных горизонтальных, а тогда на каждой вертикали и каждой горизонтали найдется по одной ладье. Любое поле, не занятое ладей, бется поэтому двумя ладями (одной — по вертикали, другой — по горизонтали).
Что же общего между лото и шахматами? А вот смотрите. Давайте выпишем все числа от 00 до 99 в квадратную таблицу 10×10:
| 00 | 01 | 02 | 09 |
| :— | :— | :— | :— |
| 10 | 11 | 12 | 19 |
| :— | :— | :— | :— |
| 90 | 91 | 92 | 99 |
Будем говорить, что число будет число , если получает очки, когда из мешка вынимают , то есть если или . Посмотрим на нашу таблицу. Каждый быет числа, которые стоит с ним лADO на одной горизонтали, либо на одной вертикали. Мы уже знаем, что если 10 чисел не быот друг друга (например, 00, 11, 22, …, 99), то любое число от 0 до 99 будет либо совпадать с одним из этих 10 чисел, либо будет быться двумя выбранными. В обонх
Рис. 1.
случаях наш набор получает 500 очков. А меняше чем десять чисlam и 250 очков можно не набрать. Вот мы и ответили на вопрос о лото. Осталясь только одна неясность.
Задача 2. Обязательно ли быть 10 чисел не былоими друг друга, чтобы такой набор всегда получилось 500 очков?
Этот вопрос очень важно. Поэтому прежде чем читать дальше, проверьте свой ответ на с. 60.
А теперь мы уже можем решить и более сложную задачу — найти, сколько всего есть набор из 10 чисел, наверняка получающих 500 очков.
Мы уже знаем, что набор из 10 чисел has a certain number of squares, and each square has a certain number of points. We can use a simple algorithm to find the number of squares in the given table.
Мы уже знаем, что набор из 10 чисел has a certain number of squares, and each square has a certain number of points. We can use a simple algorithm to find the number of squares in the given table.
Эта задача хорошо известна математикам и даже имеет свое название: ее называют задачей о перестановках. Для ее решения заметим, что к цифре 0 можно приписать любую из 10 различных цифр. Приписать цифры к паре 0 и 1 можно так: сначала приписываем какую-нибудь из 10 цифр к паре 0 и 1. Таким образом, мы получаем 10·9 = 90 пар чисел, начиная их с 0 и 1, и так далее. Ответом на вопрос задачи является 10! (читается «10 факторials»).
Задача 3 (kontrolная). Сколько способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы они не были друг друга?
Предположим теперь, что мы хотим расставить не былоих друг друга ладей на врашающей шахматной доске. Сколько рассмотренок мы увидим в этом случае?
47
Рис. 2.
Хитрость этой задачи состоит в том, что когда дока врашается, мы не можем отличить данную расстановку от центрально-симметричной ей расстановки.
Задача 4 (kontrolная и с «изюминкой»). Может ли мы различит на врашающее шахматной доке те расстановки, которые на неподвижной доке получаются друг из друга поворотом на 90° относительно центра доки?
Обозначим число центрально-симметричных расстановок через . Тогда общее число расстановок ладей на врашающее доке можно выразить формулой , и нам остается только найти .
В верхнюю горизонталь у нас, как и обычно, есть 8 способов поставить ладью. Но если мы поставили ладью в верхнюю горизонталь, то придется поставить и симметрично ей ладью в нижнюю горизонталь. Позатем для ладьи во второй сверху горизонтали остается только 6 возможностей, в третьей — 4, в четвертой — 2, после чего расстановка определенена. Таким образом, имеется симметричных расстановок, а общее число расстановок равно .
Задача 5 (kontrolная). Сколько расстановок восмини не былох друг друга ладей можно увидеть на нераскрашенной врашаюшей доке?
Пусть теперь на нашей шахматной доке выписаны подряд все числа от 1 до 64 (в верхней горизонтали слева направо числа от 1 до 8, в следующей — от 9 до 16 и так далее). Какие значения может принимать сумма чисел, написанных на тех полях, где стоям ладьи («ладейная сумма»)?
В начале этой статьи шахматная дока помогла нам решить задачу про ладо. Тепер наоборот: лодо поможет вам решить трудную задачу на доке. Пусть перед началом игры в лото каждой игрок получает некоторое число очков, и за возможность написать какое-то число нужно отдать столько очков, каково это число.
Задача 6 (kontrolная). Какой из 10! наборов не былох друг друга чисел выгоднее и каково требуемое число очков?
Решив эту задачу, вы фактически вычислите «ладейную сумму» на доке , здесь будет удобна десятичная запись чисел.
На доке больше выгодной будет запись, связанная с числом 8. А именно, доку с числами можно представить в виде «суммы» двух досок (рис. 2), причем на каждой «слагаемом» ладейная сумма не зависит от расстановки ладей и равна
на первом слагаемом и
на втором слагаемом. Значит, при любой расстановке восмини не былох друг друга ладей ладейная сумма равна 260.
Вернемся к лото.
Задача 7. У вас хватило очков, чтобы написать все числа от 00 до 99. Из мешка вынули один бочонок. Увеличится выше числа очков (по сравнению с исходным) или уменьшится?
Задача 8. Дан набор из 10 не былох друг друга чисел. Всегда ли можно разить остальные 90 чисел на 9 наборов по 10 не былох друг друга чисел?
И наконец, две задачи на доке. Будем говорить, что числа от 1 до 64 выписаны на шахматной доке «правильным образом», если для всех расстановок восмини не былох друг друга ладей «ладейная сумма» одинакова.
Задача 9. Доказать, что существует по крайней мере способа выписать числа от 1 до 64 на доке «правильным образом».
Задача 10. Какие значения может принимать «ладейная сумма», если числа от 1 до 64 выписаны «правильным образом»?