Здравствуйте. Дан отрезок чисел от a до b. Допустим, от 233 до 1566. Найти кол-во чисел на этом отрезке, которые не делятся ни на 2, ни на 3, ни на 7, ни на 9, ни на 12.

задан 14 Янв '14 15:24

изменен 14 Янв '14 18:27

Deleted's gravatar image


126

10|600 символов нужно символов осталось
1

В таких случаях применяется формула включений и исключений. Можно ввести обозначения для множеств чисел (из указанного отрезка), делящихся на 2, делящихся на 3, на 7 и так далее. Число элементов каждого такого множества легко подсчитывается. Далее надо посмотреть на попарные пересечения. Для чисел 2 и 3 получится множество чисел, кратных 6. Сколько их имеется в отрезке, также легко выясняется. Таким же образом исследуются тройные пересечения, и так далее. Везде надо брать наименьшее общее кратное в том смысле, что пересечением множеств, относящихся к числам 4 и 6, будет множество чисел, кратных 12.

После применения формулы (она есть в книжках по комбинаторике) получается подсчёт тех чисел, которые на что-то из указанного делятся, а нам нужно то, что осталось. Поэтому в конце надо взять общее количество (равное 1566-232) и вычесть из него то, что нашли по формуле.

В Вашем примере про 9 и 12 можно не говорить, так как если число не делится ни на 2, ни на 3, то оно не будет кратно ни 9, ни 12.

ссылка

отвечен 14 Янв '14 15:57

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

(14 Янв '14 16:06) ivan145

@ivan145: тот способ, который я назвал -- самый прямой, естественный и лёгкий. Такие задачи являются "типовыми", и решаются именно этим способом. Там можно разве что вывести прямые формулы с участием целых частей вида $%[n/2]$%, $%[n/3]$%, $%[n/6]$% с суммами и разностями. Но основой всё равно будет идея формулы включений и исключений.

Можно, конечно, для отрезка длиной 42 всё сосчитать вручную, а потом поделить числа на секции по 42 числа в каждой и умножить на число секций, а потом так же подсчитать количество чисел в неполной секции, но это как бы не проще.

(14 Янв '14 16:12) falcao

Можно, конечно, для отрезка длиной 42 всё сосчитать вручную, а потом поделить числа на секции по 42 числа в каждой и умножить на число секций, а потом так же подсчитать количество чисел в неполной секции, но это как бы не проще Можно про вот этот вариант поподробнее

(14 Янв '14 19:51) ivan145

Для чисел от 0 до 41 все считается просто. Их можно выписать, а потом вычеркнуть все чётные, все делящиеся на 3, все делящееся на 7. Подсчитать то, что осталось. Столько же чисел будет в каждой полной секции длиной 42. То есть среди Ваших чисел первая полная секция начинается числом 252, кратным 42, а последняя полная оканчивается числом 1553. Полных секций там помещается вроде бы 31, и про них всё известно. А небольшие участки слева и справа (от начала до 251 и от 1554 до конца) "прочёсываются" вручную.

(14 Янв '14 22:49) falcao

Далее надо посмотреть на попарные пересечения. Для чисел 2 и 3 получится множество чисел, кратных 6.Не совсем понял как искать пересечения,можно этот процесс поподробнее

(14 Янв '14 23:53) ivan145

@ivan145: речь здесь идёт об очевидном факте. Если число делится и на 2, и на 3, то оно делится на 6. То есть само пересечение двух множеств этим уже найдено. Количество же его элементов, то есть чисел списка, делящихся на 6, находится по такому же принципу, как и количество чисел, делящихся на 2 и прочие числа.

(14 Янв '14 23:59) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,448

задан
14 Янв '14 15:24

показан
3340 раз

обновлен
14 Янв '14 23:59

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru