Задача по комбинаторике

[Tiberium]

Цитата:

В стране ограничений очень любят ограничения. И автомобили. Автомобильные номера в этой стране состоят из пяти цифр, но есть еще одно ограничение — в номере может быть максимум одна пара одинаковых цифр, идущих подряд. Например, номер $22343$ имеет право на существование, а номера $78855$, $12333$ и $11111$ — нет. Сколько различных автомобильных номеров есть в стране ограничений? Автомобильные номера могут начинаться с нуля.

Я рассуждаю так: нас устраивают все комбинации, в которых все цифры разные — $10 \cdot9\cdot8\cdot7\cdot6$. С другой стороны, нас устраивают все варианты, где есть одна пара — $10\cdot10\cdot9\cdot8$.

Итого получаем: $10 \cdot9\cdot8\cdot7\cdot6+10\cdot10\cdot9\cdot8 = 52440$

Есть ощущение, что я не все варианты учитываю или, наоборот, эти множества случаев что-то покрывают дважды.

[kotenok gav]

А почему у вас парой цифр могут быть только первые две цифры? Домножьте второе слагаемое на $10$.

[Someone]

Как я понимаю, $32433$ — тоже допустимый номер.

[Yadryara]

Tiberium в сообщении #1332920 писал(а):

Есть ощущение, что я не все варианты учитываю

Очень, очень многие не учитываете. Проще из $10^5$ вычесть все незаконные номера. Их ведь совсем мало...

Наверное, я здесь не имею права оглашать полученный результат.

[wrest]

Yadryara в сообщении #1332973 писал(а):

Их ведь совсем мало...

Ну как мало... хватило бы примерно на каждый палец на руках всех федеральных депутатов РФ...

[arseniiv]

Да «аддитивный синтез» тут тоже простой. Сначала (правильно) считаем все номера, где нет пар. Потом считаем номера, где ровно одна пара, что не сильно сложнее предыдущего. Всё.

[Tiberium]

Yadryara в сообщении #1332973 писал(а):

Очень, очень многие не учитываете. Проще из $10^5$ вычесть все незаконные номера. Их ведь совсем мало...

Наверное, я здесь не имею права оглашать полученный результат.

А если рассуждать так: первый элемент можно выбрать десятью способами. Второй тоже. Даже третий ещё можно выбрать десятью способами. Но тогда четвертый уже можно выбрать максимум восемью способами, а пятый — семью. Итого может быть $56000$ случаев, где есть одна пара.

Тогда получаем $30240+56000 = 86240$.

Если это неверно, тогда прошу намекнуть на то, как тут лучше рассуждать.

[Yadryara]

Ответ неверен, разумеется. wrest неплохо намекнул.

Tiberium в сообщении #1332986 писал(а):

где есть одна пара

Терминология в таких задачах очень важна. Есть ровно одна пара или есть хотя бы одна пара?

[Tiberium]

Я умудрился сам задачу неправильно прочитать. Действительно тут проще посчитать количество неподходящих вариантов. Но у меня получается, что таких $3970$, что идет вразрез с подсказкой wrest

[Yadryara]

Ну что тут скажешь. Ищите ошибку. Подсчитайте отдельно количество незаконных номеров, и отдельно количество допустимых. Сложите их. У Вас получилось ровно $100\;000$ ? Если нет, значит ошибка именно у Вас.

Не получается её найти? Тогда стандартный совет — идти от простого к сложному, то есть уменьшить количество цифр в номере и/или основание позиционной системы счисления. Упрощать задачу вплоть до того, что все варианты можно будет просто-напросто быстро переписать и сложить. Так легче будет заметить ошибку или её отсутствие. Затем, постепенно или сразу, вернуться к исходной задаче.

[TOTAL]

Пятизначные номера, у которых за каждой цифрой следует отличная плюс учетверенные четырехзначные номера, у которых за каждой цифрой следует отличная.

(я так понял условие)

[Tiberium]

TOTAL в сообщении #1333015 писал(а):

Пятизначные номера, у которых за каждой цифрой следует отличная плюс учетверенные четырехзначные номера, у которых за каждой цифрой следует отличная.

TOTAL в сообщении #1333015 писал(а):

Последний раз редактировалось TOTAL
17.08.2018, 09:12, всего редактировалось 1 раз.


Пятизначные номера, у которых за каждой цифрой следует отличная плюс учетверенные четырехзначные номера, у которых за каждой цифрой следует отличная.

Там ведь ещё подходят варианты, когда две пары, но не подряд. Получается, действительно удобнее посчитать "неподходящие" варианты и вычесть их из 100000.

Тогда получается нам не подходят варианты вида:

XXXXX

XXXXY
YXXXX

XXXYZ
YZXXX
YXXXZ

XXXYY
YYXXX

XXYYZ
ZXXYY

Только вот 4500 вариантов у меня все равно не получается.

[TOTAL]

Tiberium в сообщении #1333022 писал(а):

TOTAL в сообщении #1333015 писал(а):

Пятизначные номера, у которых за каждой цифрой следует отличная плюс учетверенные четырехзначные номера, у которых за каждой цифрой следует отличная.

Там ведь ещё подходят варианты, когда две пары, но не подряд.

Где там, какие варианты, Вы про что?
Приведите вариант, который не охватывается моим рецептом или противоречит ему.

[EUgeneUS]

Tiberium
1. Не посчитаны варианты $XXZYY$ и $XXZXX$

2. Варианты $XXXYZ$ и $YZXXX$. В первом $Y$ не равен $X$, а $Z$ может быть равно $X$. Во втором - наоборот. Хороший повод для ошибки

3. Варианты с тремя и более одинаковыми цифрами подряд удобно считать так:

$XXX**$
$YXXX*$
$*YXXX$

Где $X$ - любая цифра, $Y$ - любая цифра не равная $X$, $*$ - любая цифра, может быть равна X или не равна.

4. Итого:

$XXX**$
$YXXX*$
$*YXXX$

$XXYYZ$
$XXYYX$
$ZXXYY$
$YXXYY$

$XXZYY$

$Z$, $X$, $Y$ - попарно различные.

[Tiberium]

TOTAL в сообщении #1333015 писал(а):

Пятизначные номера, у которых за каждой цифрой следует отличная плюс учетверенные четырехзначные номера, у которых за каждой цифрой следует отличная.

Прошу прощения, я сначала неверно Вас понял. Действительно, можно считать, что нам нужно посчитать четырехзначные номера, у которых одинаковые цифры не идут подряд. Но тогда получается, что количество вариантов - $10\cdot9\cdot10\cdot8\cdot4$.