Отношение делимости, комбинаторика

[NL0]

1) Каких чисел в десятичной системе больше - $9$-значных состоящих из различных цифр и делящихся на $3$ или $10$ значных чисел, состоящих из различных цифр и делящихся на $2$?

Девятизначных чисел с различными цифрами будет $9\cdot 9\cdot 8\cdot ...\cdot 3\cdot 2=9!\cdot 9$

Девятизначных чисел с различными цифрами, делящихся на три будет в три раза меньше $9!\cdot 3$

Десятизначных, из различных цифр будет $9\cdot 9\cdot 8\cdot ...\cdot 3\cdot 2\cdot 1=9!\cdot 9$

Десятизначных четных чисел, из различных цифр будет $\dfrac{9!\cdot 9}{2}$

Очевидно, что $\dfrac{9!\cdot 9}{2}>9!\cdot 3$. Правильно ли это?


2) Сколькими способами отношение делимости на множестве натуральных чисел от $5$ до $13$ можно достроить до отношения полного порядка?

Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение.

Но как тут достраивать? Нужно расширять множество (дополнять элементами)? Операцию деления буду обозначать $R$

$10R5$; $12R6$; остальные числа несравнимы...

[DeBill]

NL0
1. Ответ правильный, но оба количества сосчитаны неверно.
Для а) : используйте признак делимости на 3.
Для б) : составляйте число так: сначала - первую цифру, затем - последнюю, а уж потом - остальные.
И помните - в обоих случаях - о специфике цифры 0.....

-- 23.07.2016, 15:36 --

NL0 в сообщении #1139634 писал(а):

остальные числа несравнимы...

ну и славно!
Вопрос тем самым состоит в том, сколько способов установить наши числа "в очередь", чтобы 5 было впереди 10, а 6 - впереди 12....
Кстати, в чем была ошибка при решении первой задачи?

NL0 в сообщении #1139634 писал(а):

делящихся на три будет в три раза меньше

Почему? (и то же - для четных). Так можно рассуждать, если их (четных-нечетных, напр.) - поровну. А в первой задаче это не так. Но вот зато во второй......

[NL0]

Спасибо. Про признак делимости на $3$ понял. Сумма цифр девятизначного числа должна делиться на $3$.
Так как у нас число девятизначное, а цифр всего десять, то одна цифра не используется.
Чтобы сумма цифр делилась на три, должны не использоваться либо $0,3,6,9$.

Когда не используется ноль $9!$ таких чисел. Когда не используется $3$ вариантов чисел меньше, а именно $9!-8!=8\cdot 8!$. С шестеркой и девяткой аналогично.

Потому девятизначных чисел, которые делятся на $3$ будет $9!+3\cdot 8\cdot 8!$. Правильно?

-- 23.07.2016, 15:52 --

А как быть с Десятизначными четными числами, из различных цифр ?

[DeBill]

NL0
Дык я ж написал....

-- 23.07.2016, 15:59 --

А с9-значными - правильно.

[NL0]

DeBill в сообщении #1139639 писал(а):

Вопрос тем самым состоит в том, сколько способов установить наши числа "в очередь", чтобы 5 было впереди 10, а 6 - впереди 12....

Они прямо соседними должны быть? А почему именно так стоит вопрос?

У нас всего 9 мест. Если стоит 10 на последнем месте, то для $5$ будет $8$ мест, если на предпоследнем, то 7. Если на втором, то 1 место. Всего тогда вариантов $8+7+..+1=\dfrac{8\cdot 9}{2}=36$.

Для 6 и 12 аналогично 36 мест. Но эти места пересекаются!!! То есть всего у нас будет менее 36 вариантов. Можно в лоб выписать 36 вариантов для $5$ и $10$, среди них выбрать варианты, где 6 спереди 12. Но есть ли иные способы, верно ли это?

-- 23.07.2016, 16:06 --

А как быть с Десятизначными четными числами, из различных цифр ?

Попробую сделать.

Пусть первая цифра нечетная, тогда вариантов у нас будет $5\cdot 5\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=25\cdot 8!$

Пусть первая цифра четная, тогда вариантов у нас будет $4\cdot 4\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=16\cdot 8!$

Всего $41\cdot 8!$ четных десятизначных чисел с различными цифрами, верно?

[DeBill]

NL0 в сообщении #1139648 писал(а):

прямо соседними должны быть?

нет, то то и оно!.
А попробуйте по простому: расставьте числа от балды, и посмотрите на все случаи: когда обе пары - в нужном порядке; когда обе - в неправильном, когда - одна так, одна не так... Каких случаев - больше?

-- 23.07.2016, 16:07 --

NL0 в сообщении #1139648 писал(а):

Всего $41\cdot 8!$ четных десятизначных чисел с различными цифрами, верно?

!!!

[NL0]

DeBill в сообщении #1139651 писал(а):

NL0 в сообщении #1139648 писал(а):

прямо соседними должны быть?

нет, то то и оно!.
А попробуйте по простому: расставьте числа от балды, и посмотрите на все случаи: когда обе пары - в нужном порядке; когда обе - в неправильном, когда - одна так, одна не так... Каких случаев - больше?

Одинаково, насколько я понимаю!

[DeBill]

NL0
И?

[NL0]

У нас всего перестановок $9!$

Ясно, что перестановок, когда в $5,10$ пятерка слева $\dfrac{9!}{2}$

Среди этих $\dfrac{9!}{2}$ ровно половина таких, что 6 левее 12.

Тогда, пять левее десяти и шесть левее 12 в $\dfrac{9!}{4}$ случаев. Верно?

[DeBill]

NL0
Да, очень хорошо.
Т.е., сейчас мы отработали замечательный метод решения комбинаторных задач - метод "деления" - когда все пространство разбивается на одинаковые кучки. Или - когда строится взаимно-однозначное (или не совсем ) соответствие. Вот Вам пара примеров такого типа:
1. Каких (и на сколько ) семизначных чисел больше: с суммой цифр 30, или 33?
2. На окр-ти отметили 20 синих точек и одну красную. Каких мн-ков с вершинами в этих точках больше (и на скоко): чисто синих, или с красным?

[NL0]

Спасибо! У семизначных чисел наибольшая сумма $9+8+7+6+5+4+3=43$.
Чтобы сделать сумму $33$ -- нужно убрать оттуда $10$. Заменим $9$ на $1$. Сумма станет $35$, еще поменяем $4$ на $2$.
Получаем число $1235678$. Чисел с такими цифрами $7!$. Оставшиеся цифры $0,4,9$.
1) Мы можем заменить $1+3$ на $0+4$.
2) Можно заменить $4+9$ на $8+5$ или $7+6$.
3) Можно заменить $0+9$ на $4+5$ или $6+3$ или $8+1$.
Итого возможных замен $6$. Значит семизначных чисел с суммой $33$ будет $6\cdot 7!$. C $30$ можно аналогично провернуть. Верно?

[DeBill]

NL0 в сообщении #1139797 писал(а):

У семизначных чисел наибольшая сумма $9+8+7+6+5+4+3=43$

Не: ведь нет условия, что все цифры различны. И наибольшая сумма равна $7\cdot9 = 63$.
А идея: $63 = 30+33$