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

[prrrr]

Здравствуйте!
Покритикуйте пожалуйста рассуждения и подскажите, куда двигаться дальше в решении.

Задача:
Человек читает журнал и попутно отмечает четырехзначные числа, в записи которых все цифры различны. Всего он отметил ровно $100$ таких чисел. Возможно ли найти две разные цифры, которые одновременно присутствуют в записи не менее чем $14$ отмеченных чисел?

Пока мои рассуждения такие:
Общее количество возможных четырехзначных чисел, в записи которых все цифры различны, определяется следующим образом:
Первая цифра может принимать значения от $1$ до $9$ (с $0$ число начинаться не может), всего $9$ возможных вариантов.
Вторая цифра может принимать значения от $0$ до $9$, всего $10$ возможных вариантов, но за вычетом одной возможной цифры, уже использованной в качестве первой, получается $9$ возможных вариантов.
Третья цифра может принимать значения от $0$ до $9$, всего $10$ вариантов, но за вычетом двух вариантов цифр, уже использованных в качестве первой и второй получается $8$ вариантов.
Четвертая цифра аналогично третьей, но мы уже заняли три цифры для записи числа, поэтому получается, что возможных вариантов четвертой цифры – $7$.
Всего получается: $9\cdot9\cdot8\cdot7=4536$ возможных четырехзначных чисел, в записи которых все цифры различны.
По-другому это можно посчитать как $9 \cdot A_4^2 = 9\cdot(\frac{9!}{6!})=4536$

Количество возможных взаимных размещений каких-то двух цифр равно $12$. Или $A_4^2=\frac{4!}{2!}=12$.
$\frac{4536}{12}=378$. Поэтому можно сказать, что для каждого числа можно найти $377$ других чисел, в которых одновременно будут встречаться хотя бы две цифры из этого числа, стоящие на одних и тех же или разных местах в числе.

Дальше застрял.. Понимаю, что в частном случае, ответ: да, возможно, получается, что может быть и во всех $100$ числах встречаться две одинаковые цифры, но как обосновать ответ для общего случая пока не понимаю.
Пробовал рассуждать через $\frac{100}{14}=7,14$, т.е. числа с двумя одинаковыми цифрами должны встречаться среди отмеченных не реже, чем в $1$ числе из $7$, но это, на мой взгляд какое-то не строгое рассуждение, т.к. отмеченные числа могут быть любыми из $4536$ возможных и не обязательно подчиняются какой-то закономерности.
Возможно я вообще не в ту сторону пошел в решении. Подскажите пожалуйста.

Большое спасибо!

[mihaild]

А какое минимальное число раз может встречаться самая популярная цифра? Например, может ли оказаться, что каждая цифра встречается не более чем в 10 числах?

[prrrr]

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

А какое минимальное число раз может встречаться самая популярная цифра? Например, может ли оказаться, что каждая цифра встречается не более чем в 10 числах?

У меня получается, что из $4536$ возможных чисел, составленных из неповторяющихся цифр, в $1512$ встречается цифра $0$ (это самая популярная цифра), и цифры $1-9$ встречаются по $1848$ раз каждое..

[mihaild]

prrrr, это ответ на какой-то другой вопрос. Вот есть 100 четырехзначных чисел (даже не обязательно различых), в каждом все цифры различны. Каждая цифра встречается в каком-то количестве этих чисел (может и ни разу не встречаться). Может ли оказаться, что никакая цифра не встречается больше чем в 10 числах?

[prrrr]

mihaild
Такого быть не может, т.к. если мы зафиксируем первую цифру четырехзначного числа (разряд тысяч), то у нас останется $9$ возможных вариантов цифр для использования в качестве второй цифры (разряд сотен). Сотен до следующей $1000$ всего $10$, поэтому уже на этом этапе понятно (по принципу Дирихле), что какая-то цифра точно встречается больше $10$ раз.

[mihaild]

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

поэтому уже на этом этапе понятно (по принципу Дирихле), что какая-то цифра точно встречается больше $10$ раз

Непонятно. К чему тут применяется принцип Дирихле?

[prrrr]

mihaild
Если у нас зафиксирована первая цифра, то возможных вариантов для второй цифры - $9$. Если использовать каждую цифру по $10$ раз, то получится $90$ чисел, а нам нужно $100$, поэтому, по принципу Дирихле, как минимум одна цифра будет использована в разряде сотен более $10$ раз.

[mihaild]

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

Если у нас зафиксирована первая цифра, то возможных вариантов для второй цифры - $9$.

Так она же не зафиксирована.

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

как минимум одна цифра будет использована в разряде сотен более $10$ раз

Это неправда. Пусть у нас 10 раз число $1023$, 10 раз число $2130$, 10 раз число $1230$ и т.д. - получится, что каждая цифра в разряде сотен по 10 раз.

[prrrr]

mihaild
Еще, как вариант:
Пусть первая цифра в числе может быть записана $9$ вариантами, пусть вторая так же может быть записана $9$ варинтами и третья $8$ вариантами, тогда последняя цифра в записи числа может быть записана $7$ вариантами. Т.к. всего отмеченных чисел $100$, то какая-то из цифр, стоящая последней в числе, встретится не менее чем в $14$ числах.

-- 15.03.2021, 18:10 --

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

Это неправда. Пусть у нас 10 раз число $1023$, 10 раз число $2130$, 10 раз число $1230$ и т.д. - получится, что каждая цифра в разряде сотен по 10 раз.

Так у нас же все отмеченные числа различны и состоят из попарно различных цифр?

[mihaild]

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

Т.к. всего отмеченных чисел $100$, то какая-то из цифр, стоящая последней в числе, встретится не менее чем в $14$ числах.

Не следует из предыдущего.

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

Так у нас же все отмеченные числа различны и состоят из попарно различных цифр?

Можно подобрать аналогичный пример и с попарно различными числами, но в вопросе выше я рассматривал вариант, когда они не обязательно различны.

Пишите рассуждения более подробно, а не просто "понятно по принципу Дирихле" - станет легче увидеть, где ошибка.

[prrrr]

А что если попробовать так:
Первая цифра может принимать значения от $1$ до $9$ (с $0$ число начинаться не может), всего $9$ возможных вариантов.
Вторая цифра может принимать значения от $0$ до $9$, всего $10$ возможных вариантов, но за вычетом одной возможной цифры, уже использованной в качестве первой, получается $9$ возможных вариантов.
Третья цифра может принимать значения от $0$ до $9$, всего $10$ вариантов, но за вычетом двух вариантов цифр, уже использованных в качестве первой и второй получается $8$ вариантов.
Четвертая цифра аналогично третьей, но мы уже заняли три цифры для записи числа, поэтому получается, что возможных вариантов четвертой цифры – $7$.

Дальше рассмотрим $100$ отмеченных чисел:
Все числа четырехзначные, поэтому можно определить, что каждой позиции цифры в числе соответствует определенный разряд: тысяч, сотен, десятков и единиц.
Так же все числа различные.

Для записи тысяч будет использовано не менее $1$ цифры, т.к. $1000$ больше $100$.
Для записи сотен не менее двух раз будет использовано не менее $2$ различных цифр, т.к. в $1000$ $10$ сотен, а чисел, которые мы можем использовать для записи сотен - $9$.
Для записи десятков в каждой сотне не менее двух раз будет использовано не менее $3$ цифр, т.к. в $100$ $10$ десятков, а чисел, которые мы можем использовать для записи десятков - $8$.
Для записи единиц в каждом десятке не менее двух раз будет использовано не менее $4$ цифр, т.к. в $10$ $10$ единиц, а чисел, которые мы можем использовать для записи десятков - $7$.

Второй варинт такой:
С помощью двух последних цифр (единиц и десятков) можно получить $56$ различных чисел ($7\cdot8$).
Значит для записи $100$ различных чисел третья с конца цифра (сотни) должна быть записана с помощью не менее чем двух различных цифр.

Что-то я запутался.. Понял, что задача на принцип Дирихле, но ме могу понять с какой стороны его применить..

[mihaild]

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

Для записи сотен не менее двух раз будет использовано не менее $2$ различных цифр, т.к. в $1000$ $10$ сотен, а чисел, которые мы можем использовать для записи сотен - $9$.

Это неправда, ведь для разных чисел допустимые 9 цифр могут быть разные.

Попробуем так: пусть у нас просто одно число из 1000 разрядов. Какое минимальное число раз может в него входить самая популярная цифра? И как этот вопрос связан с предыдущим?

[prrrr]

mihaild
Подскажите пожалуйста, я немного не понимаю, что значит самая популярная цифра?
Если я правильно понимаю, то пока мы число не увидим и не посчитаем для конкретного числа сколько точно раз встречается та или иная цифра, любая цифра, кроме 0 может встречаться от 1 до 1000 раз, 0 может встречаться от 1 до 999 раз (т.к. не можетбыть первым в числе).

[mihaild]

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

что значит самая популярная цифра?

Цифра, которая в записи данного числа встречается больше всего раз.

[prrrr]

mihaild
Тогда получается, что если число четырехзначное, то самая популярная цифра должна встречаться не меньше двух раз. Если в числе 1000 разрядов, то самая популярная цифра должна встречаться не меньше 501 раза.
Тогда если самая популярная цифра одна, то она встречается не меньше двух раз и число возможных положений в четырехзначном числе - 6.