2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Отношение делимости, комбинаторика
Сообщение23.07.2016, 14:05 


13/02/16
129
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$; остальные числа несравнимы...

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 14:28 
Заслуженный участник


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

-- 23.07.2016, 15:36 --

NL0 в сообщении #1139634 писал(а):
остальные числа несравнимы...

ну и славно!
Вопрос тем самым состоит в том, сколько способов установить наши числа "в очередь", чтобы 5 было впереди 10, а 6 - впереди 12....
Кстати, в чем была ошибка при решении первой задачи?
NL0 в сообщении #1139634 писал(а):
делящихся на три будет в три раза меньше

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

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 14:50 


13/02/16
129
Спасибо. Про признак делимости на $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 --

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

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 14:58 
Заслуженный участник


10/01/16
2315
NL0
Дык я ж написал....

-- 23.07.2016, 15:59 --

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

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 15:00 


13/02/16
129
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!$ четных десятизначных чисел с различными цифрами, верно?

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 15:06 
Заслуженный участник


10/01/16
2315
NL0 в сообщении #1139648 писал(а):
прямо соседними должны быть?

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

-- 23.07.2016, 16:07 --

NL0 в сообщении #1139648 писал(а):
Всего $41\cdot 8!$ четных десятизначных чисел с различными цифрами, верно?

!!! :D

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 15:12 


13/02/16
129
DeBill в сообщении #1139651 писал(а):
NL0 в сообщении #1139648 писал(а):
прямо соседними должны быть?

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

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

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 15:17 
Заслуженный участник


10/01/16
2315
NL0
И?

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 16:36 


13/02/16
129
У нас всего перестановок $9!$

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

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

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

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение23.07.2016, 19:56 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение24.07.2016, 05:28 


13/02/16
129
Спасибо! У семизначных чисел наибольшая сумма $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$ можно аналогично провернуть. Верно?

 Профиль  
                  
 
 Re: Отношение делимости, комбинаторика
Сообщение24.07.2016, 07:35 
Заслуженный участник


10/01/16
2315
NL0 в сообщении #1139797 писал(а):
У семизначных чисел наибольшая сумма $9+8+7+6+5+4+3=43$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group