Занятие в математической смене пришкольного лагеря № 5 Комбинаторика. Подсчёт вариантов. Формула включений-исключений.

Занятие 5.

Остатки и делимость.

№ 1. Докажите, что если а + 1 делится на 13 и 11 - в делится на 13, то 2а - в делится на 13.

№ 2. Докажите, что если а + 10 делится на 13, то и 3а - 9 делится на 13.

№ 3. Может ли число, записанное 2010 единицами и несколькими нулями быть полным квадратом?

№ 4. Может ли число, оканчивающееся цифрами 30, быть полным квадратом?

№ 5. Докажите, что число 543212345432121 не является квадратом натурального числа.

Комбинаторика. Подсчёт вариантов.

№ 6. Сколькими способами можно зажечь свет в комнате, в которой 3 лампочки, у каждой - отдельный выключатель?

№ 7. Комбинация из трёх букв на автомобильном номере состоит только из тех русских букв, у которых есть похожие латинские, а именно А, В, Е, К, М, Н, О, Р, С, Т, У, Х. Сколько всего таких комбинаций?

№ 8. Сколькими способами можно поставить на шахматную доску белую и чёрную ладьи так, чтобы они не били друг друга.

№ 9. Сколько всего существует трёхзначных чисел? А пятизначных?

№ 10. а) У скольких двузначных чисел все цифры чётные? б) А у скольких трёхзначных?

№ 11. Сколько диагоналей в выпуклом 10-угольнике?

№12. а) У скольких двузначных чисел все цифры разные? б)А у скольких трёхзначных? в) А у скольких 11-тизначных?

№ 13. На окружности отмечены 5 красных и 7 синих точек. Рассмотрим все возможные отрезки (хорды) с концами в отмеченных точках. У скольких отрезков концы а) разного цвета, б) одинакового цвета?

Формула включений-исключений.

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

Пересечением двух множеств А и В будем называть множество А ∩В, состоящее из элементов, которые принадлежат одновременно этим двум множествам. Аналогично определяют пересечение большего числа множеств.

Объединением множеств А и В будем называть множество А U В, состоящее из элементов, которые принадлежат хотя бы одному из этих множеств.

Для конечного множества А количество его элементов будем обозначать │A│.

Формула включений-исключений. Если есть два конечных множества А и В, то число элементов в их объединении равно │ А U В│=│A│+│В│-│ А ∩В │.

№ 14. Сколько существует целых положительных чисел, не больших 100, которые:

а) делятся одновременно на 2 и на3,

б) делятся на 2, но не делятся на 3,

в) делятся на 3 , но не делятся на 2,

г) делятся на 3 или на 2,

д) не делятся ни на 2 ни на 3?

№ 15. Сколько целых положительных чисел, меньших 100, которые не делятся ни на 2, ни на 3, ни на 5?

Задачи для проверки.

№ 16. Докажите, что если а -4 делится на 5, то и 6а +1 делится на 5.

№ 17. Докажите, что число, составленное из семи двоек и семи единиц, расположенных в любом порядке, не является квадратом натурального числа.

№ 18. Сколько существует чётных четырёхзначных чисел? А нечётных?

№ 19. Сколько трёхзначных чисел, которые делятся и на 2 и на 5?

№ 20. Сколько диагоналей в выпуклом 101угольнике?

Домашнее задание.

№ 21. Может ли число, оканчивающееся цифрами 45, быть полным квадратом?

№ 22. Докажите, что если (3а +1) и (в - 5) делятся на 7, то (а + в) делится на 7.

№ 23. Сколько трёхзначных чисел, которые не делятся ни на 2, ни на 5?

№ 24. Сколько семизначных чисел с чередующейся чётностью цифр?

№ 25. Имеется 8 тетрадей и 5 книг. Сколькими способами можно выбрать набор из двух тетрадей и книги?

Решения и ответы к занятию 5.

№ 1. а + 1 ≡ 0 (mod 13), значит а ≡ 12 (mod 13); 11 - в ≡ 0 (mod 13), значит в ≡ 11 (mod 13), тогда

2а - в ≡ 2∙12 - 11 = 13 ≡0 (mod 13).

№ 2. аналогично № 1

№ 3. НЕТ. Квадрат любого числа содержит простые делители только в чётных степенях (то есть простой делитель содержится чётное количество раз). Сумма цифр этого числа равна 2010, значит число делится на 3, так как 2+0+1+0=3. Но это число не делится на 9, значит не может быть квадратом.

№ 4. НЕТ. Это число оканчивается на 30 и делится на 2, но не делится на 4.

№ 5. НЕТ. Данное число делится на 3 и не делится на 9, так как сумма его цифр равна 42

Комбинаторика. Подсчёт вариантов.

№ 6. Для каждой лампочки два варианта: включена или нет. Для каждого варианта первой лампочки есть два варианта второй, для каждого варианта первых двух лампочек есть два варианта для третьей. Тогда всего вариантов 2∙ 2∙2 =8. Из них нужно исключить один вариант, при котором все три лампочки выключены. 8-1=7 вариантов включить свет.

№ 7. Для первой буквы 12 вариантов, каждому из них соответствует 12 вариантов второй буквы и т.д. Всего 12∙12∙12= 1728 вариантов.

№ 8. Сначала поставим белую ладью, для неё 64 способа. Тогда вторую нельзя ставить на те клетки, которые бьёт первая, в том числе на ту, на которой стоит первая, то есть 15 клеток. Для каждого из 64 вариантов есть 64-15=49 вариантов поставить вторую ладью, значит всего 64∙49=3136 способов.

№ 9. Первая цифра - 9 вариантов (все цифры, кроме 0), для второй - 10, третьей - 10. Значит всего трёхзначных чисел 9х10х10=900, пятизначных 9х10х10х10х10=90000.

№ 10. Для первой чётной цифры 4 варианта: 2,4,6,8, а для остальных 5 вариантов:0,2,3,4,6,8. Тогда а) 4х5=20, б)4х5х5=100.

№ 11. Из каждой вершины 10-тиугольника выход 10-3=7 диагоналей, и каждая диагональ соединяет две вершины, значит всего 10х7: 2=35 диагоналей.

№ 12. Для первой цифры 9 вариантов (все кроме 0). Для второй - 9 (все кроме первой), для третьей -8 (все кроме первой и второй), и так далее. А)9х9=81, б) 9х9х8=648, в) 0 (всего 10 различных цифр, значит, у 11-тизначного числа все цифры не могут быть различными.

№ 13. а)5х7=35, б)5х4:2 + 7х6: 2 =10+21 =31.

Формула включений-исключений.

№ 14 а) Число делится на 2 и на 3, тогда и только тогда, когда оно делится на 6. На 6 делятся числа 6, 12, …, 96. Значит, их количество равно (96-6): 6 + 1 = 16. б) Всего существует (100-2):2 + 1=50 чисел не больших 100 и делящихся на 2. Из них вычитаем числа, которые делятся и на 2 и на 3 50-16 = 34, в) На 3 делятся числа 3, 6, 9, 12, ….99. Всего (99-3):3 +1 =33. Вычтем из этого количества числа, которые делятся и на 2 и на3: 33-16 = 17. г) Обозначим А - множество чисел, делящихся на 2, через В - множество чисел, делящихся на 3, тогда А ∩В - множество чисел, делящихся на 2 и на 3. │ А U В│=│A│+│В│-│ А ∩В│= 50 + 33 -16 = 67. д) Из 100 рассматриваемых чисел, вычтем те, которые делятся на 2 или на 3. Всего 100 - 67 =33 числа.

№ 15 Пусть А - множество чисел, делящихся на 2, В - множество чисел, делящихся на 3, С - множество чисел, делящихся на 5. Для трёх множеств формула включений-исключений примет вид:

│ А U В U С│=│A│+│В│+ │С│ -│ А ∩В│-│ А ∩С│- │С ∩В│+ │ А ∩ В ∩ С│

В задаче № 14 некоторые из данных слагаемых найдены, найдём │С│=(100-5):5+1=20,│ А ∩С│=(100-10):10+1=10 найдём │С ∩В│= (90-15):15+1=6, │ А ∩ В ∩ С│ = (90-30):30 +1 = 3. │А U В U С│=50+33+20-16-10-6+3=74. Чисел, которые делятся хотя бы на 2, на 3 или 5 всего 74, значит, чисел, не делящихся ни на одно из них

100 -74=26.

Задачи для проверки.

№16. а - 4 ≡ 0 (mod 5), значит а ≡ 4 (mod 5); тогда 6а + 1 ≡ 6∙4 +1 = 25 ≡0 (mod 5).

№ 17. Сумма цифр такого числа равна 21 и делится на 3, но не на 9.

№ 18. У чётного числа 5 вариантов для последней цифры. Всего: 9х10х10х5=4500 чисел, аналогично с нечётным

№ 19. Число делится и на 2 и на 5, когда оно делится на 10, всего таких трёхзначных чисел (990-100):10+1=90.

№ 20. (101 - 3):2 = 49.