Комбинаторика, запись числа

[mihaild]

prrrr в сообщении #1509562 писал(а):

если число четырехзначное, то самая популярная цифра должна встречаться не меньше двух раз

Разве? Вот число $1234$ - в нём сколько раз встречается самая популярная цифра? А в числе "100 единиц, 100 нулей, 100 двоек, ..., 100 девяток"?

[prrrr]

mihaild в сообщении #1509566 писал(а):

Разве? Вот число $1234$ - в нём сколько раз встречается самая популярная цифра? А в числе "100 единиц, 100 нулей, 100 двоек, ..., 100 девяток"?

Тогда получается, что в числе $1234$ самой популярной цифры нет, все цифры равнопопулярны.

[mihaild]

prrrr в сообщении #1509572 писал(а):

Тогда получается, что в числе $1234$ самой популярной цифры нет, все цифры равнопопулярны.

Нет, в нём 4 самых популярных цифры - 1, 2, 3 и 4.

Переформулируем иначе: может ли оказаться, что в 1000-значном числе нет ни одной цифры, которая встречается больше 14 раз?

[prrrr]

mihaild в сообщении #1509574 писал(а):

может ли оказаться, что в 1000-значном числе нет ни одной цифры, которая встречается больше 14 раз?

Если я правильно понимаю, то нет. Потому что, если каждая цифра от 0 до 9 встречается хотя бы 14 раз, то получится 140-значное число, а у нас 1000 значное, поэтому всегда будет хотя бы одна цифра, которая встречается больше 14 раз.

[mihaild]

prrrr в сообщении #1509577 писал(а):

Потому что, если каждая цифра от 0 до 9 встречается хотя бы 14 раз, то получится 140-значное число

Почти правильно, только не "хотя бы" а "не более чем", и не "140-значное" а "не более чем 140-значное".
Хорошо, теперь возвращаемся к предыдущему вопросу. У нас есть 100 4-значных чисел. Может ли оказаться так, что никакая цифра не встречается в них более 14 раз?

[prrrr]

mihaild в сообщении #1509578 писал(а):

У нас есть 100 4-значных чисел. Может ли оказаться так, что никакая цифра не встречается в них более 14 раз?

Если я правильно понял логику, то 100 4-значных чисел можно представить как 400-значное число? Тогда аналогично получается, что если каждая цифра от 0 до 9 встречается не более чем 14 раз, то опять таки получим не более чем 140-значное число, поэтому всегда будет хотя бы 1 цифра, которая встречается более 14 раз.

[svv]

prrrr в сообщении #1509582 писал(а):

Если я правильно понял логику, то 100 4-значных чисел можно представить как 400-значное число?

Не обязательно так представлять. Важно лишь, что в сотне 4-значных чисел всего цифр 400, а различных цифр только 10.

Хорошо, а не более 17 раз каждая цифра может встречаться?
Сформулируйте сами наиболее сильное утверждение, какое тут возможно.

[prrrr]

svv в сообщении #1509585 писал(а):

Хорошо, а не более 17 раз каждая цифра может встречаться?
Сформулируйте сами наиболее сильное утверждение, какое тут возможно.

Получается, что самое сильное утверждение такое: в 100 различных 4-значных числе каждая цифра может встречаться не более 40 раз.

[mihaild]

prrrr в сообщении #1509587 писал(а):

Получается, что самое сильное утверждение такое: в 100 различных 4-значных числе каждая цифра может встречаться не более 40 раз.

Нет, можно легко найти сотню 4-значных чисел, у которых всех в первом разряде стоит 1.

[prrrr]

mihaild
Точно, поторопился, не правильно сформулировал..
Будет хотя бы одна цифра, которая встретится не меньше 40 раз.

[mihaild]

Правильно. В итоге тут принцип Дирихле применяется так: всего у нас 10 различных цифр и 400 позиций, где они должны стоять. Значит, хотя бы одно число стоит в хотя бы $\frac{400}{10} = 40$ позициях.
Попробуйте теперь провести то же рассуждение, но для пар цифр.

[prrrr]

mihaild
Спасибо! Попробую применить к паре различных чисел:
Всего может быть $C_9^2=\frac{9!}{7!\cdot2!}=36$ различных пар цифр. В каждом 4-значном числе пары цифр могут быть образованы $C_4^2=\frac{4!}{2!\cdot2!}=6$ способами. Получается, что всего возможных способов образовать пары цифр в $100$ 4-значных числах может быть $6\cdot100=600$.
Тогда хотя бы одна пара цифр встречается $\frac{600}{36}=16,7$, т.е. не менее чем $16$ раз.

[mihaild]

prrrr в сообщении #1509634 писал(а):

Всего может быть $C_9^2=\frac{9!}{7!\cdot2!}=36$ различных пар цифр

Уверены?

[prrrr]

mihaild
Я считал $C_9^2$ потому что у нас же максимальное возможное количество вариантов цифр для первого и второго разрядов (если читать справа налево) - $7$ и $8$, а для третьего и четвертого разрядов - $9$, т.е. максимальное количество возможных вариантов цифр - $9$.
Но так рассуждать наверное не совсем корректно, потому что мы можем при формировании пар начинать с любого разряда, при этом первая цифра в паре всегда будет выбираться из $10$ вариантов, а вторая из $9$ вариантов. Тогда общее количество возможных пар цифр (с учетом того, что по условиям задачи пары вида $1-5$ и $5-1$ считаются за одну пару) равно $C_{10}^2=\frac{10!}{8!\cdot2!}=45$.

И получаем, что $\frac{600}{45}=13,3$. Это значит, что хотя бы одна пара встречается не менее $14$ раз.