Занятие в математической смене пришкольного лагеря № 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.