Тема:
Все темы
>>
Комбинаторика
>>
Классическая комбинаторика
>>
Классическая комбинаторика (прочее)
Фильтр
Задачи
Задача 30604 |
|
|
Решение
Остатки от деления 2n на 7 повторяются с периодом 3: 2, 4, 1. Остатки от деления n² на 7 повторяются с периодом 7: 1, 4, 2, 2, 4, 1, 0. Поэтому делимость на 7 зависит только от остатка при делении n на 21. Рассмотрим все случаи (в первой строке таблицы – остатки от деления на 21, в следующих двух – остатки от деления на 7).Ответ
2858 чисел.
|
|
Задача 32040 |
|
|
Автобусные билеты имеют номера от 000000 до 999999. Билет называется счастливым, если сумма первых трёх цифр его номера равна сумме последних трёх его цифр. Докажите, что:
а) число всех счастливых билетов чётно;
б) сумма номеров всех счастливых билетов делится на 999.
Решение
а) Укажем два способа разбиения счастливых билетов на пары.
Первый способ. Переставим в номере билета первые три цифры с последними тремя цифрами. Полученный билет и поставим в пару исходному (например, билету 239671 парой будет 671239). Так мы разбили на пары все билеты кроме тех, которые являются парными сами к себе. Это билеты, для которых первые три цифры номера совпадают с последними тремя цифрами; таких билетов ровно 1000. Значит, общее число счастливых билетов чётно.
Второй способ. Каждому счастливому билету поставим в соответствие билет, номер которого состоит из цифр, дополняющих cоответствующие цифры номера исходного билета до девятки. Например, билет 239601 получит в пару билет 760398. Очевидно парой к каждому счастливому билету является также счастливый билет. При этом никакой билет не получает в пару себя (цифра не может дополнять до девятки самое себя, поскольку 9 – нечётное число). Таким образом, мы получили разбиение всех счастливых билетов на пары.
б) Рассмотрим второй способ разбиения билетов на пары. Сумма номеров билетов в каждой паре равна 999999, значит, она делится на 999. Сложив эти попарные суммы, получим число, кратное 999.
|
|
|
Задача 60438 |
|
|
Сколько существует целых чисел от 1 до 16500, которые
а) не делятся на 5;
б) не делятся ни на 5, ни на 3;
в) не делятся ни на 5, ни на 3, ни на 11?
Решение
а) Разобьём все числа на 16500 : 5 = 3300 пятерок последовательно идущих чисел. В каждой пятерке одно число делится на 5, а 4 – не делятся. Поэтому всего 4·3300 = 13200 чисел не делятся на 5.б) 3300 чисел делятся на 5. Аналогично 16500 : 3 = 5500 чисел делятся на 3. Из них 16500 : 15 = 1100 делятся на 15, то есть и на 5, и на 3. Они были сосчитаны дважды. Всего на 5 или на 3 делятся 3300 + 5500 – 1100 = 7700, а не делятся 16500 – 7700 = 8800 чисел.
в) На 11 делятся 16500 : 11 = 1500 чисел, на 5 и на 11 – 16500 : 55 = 300 чисел, на 3 и на 11 – 16500 : 33 = 500 чисел, на 3, на 5 и на
11 – 300 : 3 = 100 чисел.
По формуле включения-исключения всего на 3, на 5 или на 11 делятся 5500 + 3300 + 1500 – 1100 – 500 – 300 + 100 = 8500 чисел, а не делятся ни на одно из этих чисел 16500 – 8500 = 8000 чисел.
Ответ
а) 13200; б) 8800; в) 8000 чисел.
|
|
|
Задача 65891 |
|
|
У каждого из тридцати шестиклассников есть одна ручка, один карандаш и одна линейка. После их участия в олимпиаде оказалось, что 26 учеников потеряли ручку, 23 – линейку и 21 – карандаш. Найдите наименьшее возможное количество шестиклассников, потерявших все три предмета.
Решение
Из условия следует, что у четырёх шестиклассников есть ручка, у семи – линейка и у девяти – карандаш. Таким образом, обладать хотя бы одним предметом могут не более чем 4 + 7 + 9 = 20 человек. А значит, не менее чем 30 – 20 = 10 человек потеряли все три предмета.
Все три предмета потеряют ровно 10 человек, если каждый из остальных двадцати потеряет ровно два предмета.
Ответ
10 шестиклассников.
|
|
|
Задача 66576 |
|
|
Решение
Рассмотрим произвольную расстановку чашек и выпишем в строчку их цвета. Под этой строчкой выпишем также все её различные циклические сдвиги — всего 14 штук. Подсчитаем, сколько всего будет совпадений по цвету на одной и той же позиции в исходной расстановке и в расстановках, полученных сдвигами. Для чёрных чашек совпадения по цвету будут ровно в 6 сдвигах, а для белых — в 7 сдвигах. Следовательно, всего совпадений по цветам для 14 сдвигов будет $7\cdot6+8\cdot7=98$. Значит, существует сдвиг, в котором будет не более $98/14=7$ совпадений с исходной расстановкой.
Рассмотрим такую расстановку чашек: ббббчбчббччбччч. Непосредственной проверкой можно убедиться, что все её циклические сдвиги имеют с ней ровно 7 совпадений.
Ответ
7.|
|
|
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 101]
