Разделы 
Дополнительно
Задача по математике - 3766
2019-06-16 
Имеется тысяча билетов с номерами $000, 001, \cdots, 999$ и сто ящиков с номерами $00, 01, \cdots, 99$. Билет разрешается опускать в ящик, если номер ящика можно получить из номера этого билета вычеркиванием одной из цифр. Докажите, что:
а) можно разложить все билеты в 50 ящиков;
б) нельзя разложить все билеты менее чем в 40 ящиков;
в) нельзя разложить все билеты менее чем в 50 ящиков;
г) Пусть билеты имеют четырехзначные номера (от 0000 до 0001) и билет разрешается опускать в ящик, номер которого можно получить из номера билета вычеркиванием каких-либо двух цифр. Докажите, что все четырехзначные билеты можно разложить в 34 ящика.
д) Какой минимальный набор ящиков потребуется для $k$-значных билетов ($k = 4, 5, 6, \cdots$)?
Решение:
а) Разобьем десять цифр $0, 1, 2, \cdots, 9$ на две группы по 5 цифр в каждой (например, от 0 до 4 - одна группа, от 5 до 9 - другая). Достаточно использовать ящики, у которых обе цифры берутся из одной группы, поскольку такие две цифры есть в любом трехзначном номере.
б) Кроме 10 ящиков $00, 11, \cdots, 99$, которые непременно будут заняты, потребуется не менее 30 ящиков, чтобы разместить билеты с тремя разными цифрами: таких билетов всего $10 \cdot 9 \cdot 8 = 720$, а в каждый ящик о номером $\bar {pq} (р \neq q)$ помещается не более $3 \cdot 8 = 24$ из них ($\overline{zpq}, \overline{pzq}$ и $\overline{pqz}$, где $z$ - любая цифра, отличная от $p$ и $q$).
в) Пусть $x$ - наименьшее количество номеров занятых ящиков, начинающихся с одной какой-либо цифры ($x \geq 1$); поскольку все цифры равноправны, мы можем считать, что меньше всего номеров начинается с 9 и эти номера - $\overline{99}, \overline{98}, \cdots, \overline{9y}$ где $у = 10 - x$. Тогда любой билет $\overline{9pq}$, где $p < у, q < у$, не может помещаться в ящиках $\overline{9p}$ и $ {9q}$, т. е. должен быть занят ящик $\overline{pq}$. Таким образом, заняты по крайней мере все у ящиков с номерами, у которых обе цифры - от 0 до $у - 1$, и еще по крайней мере $х$ ящиков, начинающихся с одной из цифр от $у$ до 9 (не менее чем по $x$ для каждой из этих $x$ цифр), т. е. всего занято не менее
$у^2 + x^2 = (10 - x)^2 + x^2 \geq 50$ ящиков.
г), д) Для данных натуральных чисел $k$ и $s, k < s$, обозначим через $F(k, s)$ наименьшее из чисел $x_1^2 + x_2^2 + \cdots + x_k^2$, где $x_1, x_2, \cdots, x_k$ - натуральные числа, в сумме дающие $s$; величину $F(k,s)$ можно выразить через $k$ и $s$ - наименьшее значение суммы квадратов достигается, когда числа $x_j$ «почти равны»; точнее, если $s = kq + r, 0 \leq r < k$, то $k - r$ из них равны $q$ и $r$ остальных $q + 1$, так что
$F (k, s) = (k - r) q^2 + r (q + l)^2 = kq^2 + r (2q + 1)$.
Удобно рассматривать сразу более общую задачу - для $k$-значных «билетов» с $s$ «цифрами» от 0 до $s - 1$ (в нашей задаче $s = 10$). Докажем, что наименьшее число $M(k, s)$ ящиков с номерами $\bar {pq}$ ($0 \leq p < s, 0 \leq q < s$), в которые можно поместить билеты, вычеркнув $k - 2$ цифры, равно $F(k-1, s)$.
В частности, в задаче г)
$M (4, 10) = F (3, 10) = 3^2 + 3^2 + 4^2 = 34$,
а ответ к задаче д) дается таблицей
Неравенство $M(k,s) \geq F(k-1, s)$ можно доказать индукцией по $k + s$, рассуждая так же, как в пункте в):
$М (k, s) \geq min_{x = 1, 2, \cdots, s} (M(k - 1, s - x)+ x^2)$.
Для размещения билетов пo $F(k-1, s) = x_1^2 + x_2^2 + \cdots + x_{k-1}^2$ ящикам достаточно, как в пункте а), разбить $s$ цифр на $k - 1$ группу (по $x_1, x_2, \cdots, x_{k-1}$ цифр) и оставить ящики, у которых обе цифры из одной группы.
Имеется тысяча билетов с номерами $000, 001, \cdots, 999$ и сто ящиков с номерами $00, 01, \cdots, 99$. Билет разрешается опускать в ящик, если номер ящика можно получить из номера этого билета вычеркиванием одной из цифр. Докажите, что:
а) можно разложить все билеты в 50 ящиков;
б) нельзя разложить все билеты менее чем в 40 ящиков;
в) нельзя разложить все билеты менее чем в 50 ящиков;
г) Пусть билеты имеют четырехзначные номера (от 0000 до 0001) и билет разрешается опускать в ящик, номер которого можно получить из номера билета вычеркиванием каких-либо двух цифр. Докажите, что все четырехзначные билеты можно разложить в 34 ящика.
д) Какой минимальный набор ящиков потребуется для $k$-значных билетов ($k = 4, 5, 6, \cdots$)?
Решение:
а) Разобьем десять цифр $0, 1, 2, \cdots, 9$ на две группы по 5 цифр в каждой (например, от 0 до 4 - одна группа, от 5 до 9 - другая). Достаточно использовать ящики, у которых обе цифры берутся из одной группы, поскольку такие две цифры есть в любом трехзначном номере.
б) Кроме 10 ящиков $00, 11, \cdots, 99$, которые непременно будут заняты, потребуется не менее 30 ящиков, чтобы разместить билеты с тремя разными цифрами: таких билетов всего $10 \cdot 9 \cdot 8 = 720$, а в каждый ящик о номером $\bar {pq} (р \neq q)$ помещается не более $3 \cdot 8 = 24$ из них ($\overline{zpq}, \overline{pzq}$ и $\overline{pqz}$, где $z$ - любая цифра, отличная от $p$ и $q$).
в) Пусть $x$ - наименьшее количество номеров занятых ящиков, начинающихся с одной какой-либо цифры ($x \geq 1$); поскольку все цифры равноправны, мы можем считать, что меньше всего номеров начинается с 9 и эти номера - $\overline{99}, \overline{98}, \cdots, \overline{9y}$ где $у = 10 - x$. Тогда любой билет $\overline{9pq}$, где $p < у, q < у$, не может помещаться в ящиках $\overline{9p}$ и $ {9q}$, т. е. должен быть занят ящик $\overline{pq}$. Таким образом, заняты по крайней мере все у ящиков с номерами, у которых обе цифры - от 0 до $у - 1$, и еще по крайней мере $х$ ящиков, начинающихся с одной из цифр от $у$ до 9 (не менее чем по $x$ для каждой из этих $x$ цифр), т. е. всего занято не менее
$у^2 + x^2 = (10 - x)^2 + x^2 \geq 50$ ящиков.
г), д) Для данных натуральных чисел $k$ и $s, k < s$, обозначим через $F(k, s)$ наименьшее из чисел $x_1^2 + x_2^2 + \cdots + x_k^2$, где $x_1, x_2, \cdots, x_k$ - натуральные числа, в сумме дающие $s$; величину $F(k,s)$ можно выразить через $k$ и $s$ - наименьшее значение суммы квадратов достигается, когда числа $x_j$ «почти равны»; точнее, если $s = kq + r, 0 \leq r < k$, то $k - r$ из них равны $q$ и $r$ остальных $q + 1$, так что
$F (k, s) = (k - r) q^2 + r (q + l)^2 = kq^2 + r (2q + 1)$.
Удобно рассматривать сразу более общую задачу - для $k$-значных «билетов» с $s$ «цифрами» от 0 до $s - 1$ (в нашей задаче $s = 10$). Докажем, что наименьшее число $M(k, s)$ ящиков с номерами $\bar {pq}$ ($0 \leq p < s, 0 \leq q < s$), в которые можно поместить билеты, вычеркнув $k - 2$ цифры, равно $F(k-1, s)$.
В частности, в задаче г)
$M (4, 10) = F (3, 10) = 3^2 + 3^2 + 4^2 = 34$,
а ответ к задаче д) дается таблицей
Неравенство $M(k,s) \geq F(k-1, s)$ можно доказать индукцией по $k + s$, рассуждая так же, как в пункте в):
$М (k, s) \geq min_{x = 1, 2, \cdots, s} (M(k - 1, s - x)+ x^2)$.
Для размещения билетов пo $F(k-1, s) = x_1^2 + x_2^2 + \cdots + x_{k-1}^2$ ящикам достаточно, как в пункте а), разбить $s$ цифр на $k - 1$ группу (по $x_1, x_2, \cdots, x_{k-1}$ цифр) и оставить ящики, у которых обе цифры из одной группы.
