Задачи. Олимпиадные задачи по математике за 6 класс - Погребникова Алена. Арифметика На карточках записаны цифры 1, 2, Из этих карточек составлены числа и записано неверное равенство. Покажите, как, переместив только одну карточку, сделать равенство верным. 1
 Скачать 0.53 Mb.
|
|
Комбинаторика Задача 1: Сколькими способами можно зажечь свет в нашем классе? (в классе 3 лампочки, у каждой – отдельный выключатель) Решение: Обсуждение путей решения: а) прямой подсчет – перебор возможных способов; упорядочение перебора – то есть суммирование 1 + 3 + 3 + 1 = 8; б) рассмотрение ситуации по отдельности для каждой лампочки – либо «вкл», либо «выкл»; правило произведения: 2 × 2 × 2 = 8; графическое отображение в виде графа с кратными дугами и в виде дерева перебора. Задача 2: Комбинация из трёх букв на автомобильном номере состоит только из тех русских букв, у которых есть похожие латинские, а именно из А, В, Е, К, М, Н, О, Р, С, Т, У, Х. Сколько всего таких комбинаций? Задача 3: Сколькими способами можно поставить на шахматную доску белую и черную ладьи так, чтобы они не били друг друга? Решение: Перебор по положениям белой ладьи. Задача 4: а) В магазине «Все для чая» продаются 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить там набор «чашка + блюдце»? б) В тот же магазин завезли еще 4 вида чайных ложек. Сколькими способами можно купить комплект «чашка + блюдце + ложка»? в) Известно, что одна из чашек, одно из блюдец и одна из ложек – золотые. Сколькими способами можно купить набор из 3-х различных предметов, в котором в1) нет золотых предметов? в2) 1 золотой предмет? в3) 2 золотых предмета? в4) 3 золотых предмета? г) Сколькими способами в магазине можно купить комплект из двух предметов? д) сколькими способами можно купить комплект из 1 предмета? е) Ясно, что «купить 0 предметов» можно единственным способом. Каков смысл равенства 1 + 12 + 47 + 60 = 6 × 4 × 5? Решение: а) по правилу произведения получаем 5 × 3 = 15. б) 5 × 3 × 4 = 60. в1) считаем количество не-золотых предметов: 4 чашки, 2 блюдца, 3 ложки. По правилу произведения получаем 4 × 2 × 3 = 24. в2) подметим, что 1 золотой предмет – либо чашка, либо ложка, либо блюдце. Если это чашка, то имеем 1 × 2 × 3 = 6 способов, если это блюдце, то число способов равно 4 × 1 × 3 = 12, наконец, для ложки получаем 4 × 2 × 1 = 8 способов. Итого – 26. в3) возможны 2 разумных перебора – либо по парам золотых предметов («чашка + блюдце», «чашка + ложка", «ложка + блюдце"), либо перебор не-золотых предметов. При обоих подходах получаем 1 × 1 × 3 + 1 × 2 × 1 + 4 × 1 × 1 = 9 способов. После задач в2) и в3) формулируем правило суммы и когда им надо пользоваться. в4) 1 способ. ( = 1 × 1 × 1). Усложняем задачу ученикам: как получить ответ другим способом? Вот этот способ: так как всего возможностей 60 (см. задачу б)), а в задачах в1)–в3) были найдены 24 + 26 + 9 = 59 из них, то на долю задачи в4) остался последний, единственный, способ. Обращаем внимание школьников на необязательность, но желательность проверки равенства 60 = 24 + 26 + 9 + 1 при самостоятельном решении подобных задач. г) по правилу суммы – 5 × 3 + 5 × 4 + 3 × 4 = 47 способов. д) 5 + 4 + 3 = 12. е) смысл состоит в том, что мы добавляем для каждого предмета еще одну возможность – либо покупать его, либо нет. Это значит, что мы как бы вводим шестую «липовую чашку», четвертое «липовое блюдце" и пятую «липовую ложку». Если выбран «липовый" предмет, это означает, что мы данный вид посуды просто не покупаем. Но теперь есть всего 6 × 4 × 5 способов выбрать набор из 3-х предметов (некоторые из которых будут липовыми), а сумма слева представляет собой разбиение на случаи «0 липовых», «1 липовый", «2 липовых", «3 липовых". Задача 1: а) У скольких двузначных чисел все цифры чётные? б) А у скольких трёхзначных? Решение: (а) оформить также в виде таблицы. Про (б) – 3 способа: разветвленное дерево, таблица, где строки занумерованы парами и трёхмерная таблица Задача 2: а) У скольких двузначных чисел все цифры разные? б) А у скольких трёхзначных? в) А у скольких 11-значных? Решение: Дополнительно можно изобразить все числа в виде таблицы, и получить второе решение с вычитанием лишних случаев (грубо говоря, квадрат минус диагональ). Задача 3: На окружности отмечены 5 красных и 7 синих точек. Рассмотрим всевозможные отрезки (хорды) с концами в отмеченных точках. У скольких отрезков концы а) разного цвета; б) одинакового цвета? Решение: Очень полезно разобрать два решения: с деревом перебора и с таблицей. Отметить формулу сложения случаев. Задача 4: В обычном домино на половинках доминошек бывает от 0 до 6 точек. Всего в комплекте 28 доминошек. А сколько доминошек будет в комплекте, где на половинке возможно от 0 до 13 точек? Решение: 105. Поскольку задача двухходовая, часто дают неправильные ответы. В этом случае рекомендовать проверить способ решения на обычном домино. При разборе обязательно оформить рассуждения в виде таблицы. Задача 5: Сколькими способами можно разменять 50 руб монетами в 1 и 2 руб? Решение: 26. Каждый способ однозначно задается числом 2-рублевых монет, а их может быть от 0 до 25. Задача 6: Сколькими способами можно поставить на доску черного и белого королей так, чтобы они не били друг друга? Решение: Если черный король стоит в углу доски (4 поля), то белого короля на доску можно поставить 60 способами. Если черный король стоит на границе доски (но не в углу – 6 × 4 = 24 поля), то белого короля можно поставить на любое из 58 «незапрещенных» полей. Для всех остальных (их 36) положений черного короля имеется ровно 55 «незапрещенных» положений белого короля. Итого получаем 4 × 60 + 24 × 58 + 36 × 55 = 3612 способов. Задача 7: В детский сад привезли кубики: красные и синие. Каждому из 100 детей выдали по 3 кубика, и каждый ребенок построил из своих кубиков башню. Какое наибольшее число различно раскрашенных башен могло получиться? А если выдали по 4 кубика? По 5? По 6? По 7? Решение: 8, 16, 32, 64, 100. Полезно обратить внимание на последний ответ и причины его появления в ряду степеней двойки. Задача 8: Сигнальное устройство состоит из пяти одноцветных лампочек, расположенных в ряд. Сколько различных сигналов можно подать с его помощью? А сколько, самое меньшее, надо взять лампочек, чтобы можно было подать 200 различных сигналов? А 1000 сигналов? Решение: 32 сигнала. Для 200 сигналов нужно взять 8 лампочек, для 1000 сигналов – 10 лампочек. Задача 9: Назовем число забавным, если все его цифры делятся на 4. Сколько забавных чисел среди четырёхзначных? А среди шестизначных? Решение: 54 = 2 × 3 × 3 × 3; 486 = 2 × 35. Задача 10: Как известно, компьютер работает с двоичными кодами, которые представляют собой записи, составленные из нулей и единиц (например, 11001011). Количество знаков в коде называется его длиной. Сколько разных символов можно закодировать двоичными кодами длины 5? Длины 6? Задача 11: Во рту у марсианина есть 10 гнезд для зубов. В каждом гнезде либо есть зуб, либо его нет. Известно, что любые два марсианина отличаются набором зубов (т.е., если взять любых двух, то найдется гнездо, в котором у одного есть зуб, а у другого нет). Каково наибольшее возможно число марсиан? Решение: Закодируем марсиан двоичными числами – ведь для каждого зуба имеется ровно две возможности: либо этот зуб есть, либо его нет. Таким образом, общее число марсиан не больше, чем число «кодировок» зубов, которое равно 2¹º = 1024. Задача 12: Сигнальный флажок состоит из шести горизонтальных полосок белого, синего или красного цвета, причём верхняя полоска всегда синяя, а соседние полоски – разноцветные. Сколько бывает разных сигнальных флажков? Решение: 32. Для каждой следующей полоски есть ровно две возможности! Придумайте способ их кодирования числами 0 и 1. Учтите, что таких способов существует не один, а несколько (а кстати, сколько??) Задача 13: Назовем две цифры близкими, если они отличаются на 1. Кроме того, будем считать близкими цифры 0 и 9. Сколько существует различных десятизначных чисел, у которых любые две соседние цифры – близкие? Решение: 9 • 29. Задача 14: Из Манчестера в Ливерпуль ведут два шоссе с односторонним движением, пересеченные десятью проселками (см. рисунок). Машина выезжает из М в Л по одному из шоссе, и, доезжая до любой развилки, может либо свернуть на проселок, либо не сворачивать. Свернув, она проезжает проселок до конца и продолжает опять по другому шоссе (по тем же правилам). Сколькими разными способами можно проехать из Манчестера в Ливерпуль?  Задача 15: Имеется 10 различных книг. Сколькими различными способами можно выбрать из них одну или несколько книг для подарка? Решение: «Одну или несколько» – значит, любое число, кроме нуля книг. Добавим еще и возможность подарить 0 книг – тогда общее число способов подарить книги будет равно 2¹º (объясните, почему?). Можно напомнить о связи этой задачи с задачей о «липовых» чашках-ложках-блюдцах. Задача 1: Сколькими способами Алексей Николаевич может построить 50 шестиклассников в шеренгу? Задача 2: Сколько сторон и диагоналей у 50-угольника? Задача 3: Сколькими способами можно расставить на шахматной доске размером 50 × 50 пятьдесят ладей, не бьющих друг друга? Решение: 50! Это пара к задаче 1 (а также 7 и 8). Задача 4: Сколькими способами победитель «Поля чудес» может выбрать два приза из 50 имеющихся? Решение: 50 × 49/2. Это пара к задаче 2. Каждый выбранный приз – вершина 50-угольника, а пара выбранных призов – это сторона или диагональ. Задача 5: Сколькими способами можно выдать 50 шестиклассникам два наряда: на уборку апельсиновых корок и дежурство в столовой? Задача 6: Сколькими способами можно из 50 участников собрания выбрать председателя и секретаря? Решение: 50 × 49. Это пара к задаче 5. Дадим председателю наряд на уборку корок, а секретарю – наряд на столовую. И наоборот. Задача 7: Есть два письма и 50 разных конвертов. Сколькими способами можно упаковать письма в конверты? Решение: 50! Это пара к задаче 3. Кодировка такая: по горизонтали разложим письма, а по вертикали – конверты. Будем ставить ладью на пересечении горизонтали и вертикали тогда и только тогда, когда письмо, соответствующее горизонтали, кладем в конверт, соответствующий вертикали. Задача 8: Есть 50 разных конфет. Сколькими способами можно раздать их по одной 50 шестиклассникам? Решение: 50! Это пара к задаче 1 (а также задачам 2 и 7). Тот, кто получил первую конфету, встанет в шеренгу самым первым, получивший вторую конфету – вторым, и т.д. Задача 9: Сколькими способами можно расставить в таблице 5 × 10 числа от 1 до 50? Решение: 50! Это пара к задаче 8 (а значит, и к задаче 1). Занумеруем конфетки числами от 1 до 50, а шестиклассников посадим в клетки таблицы 6 × 8. Дальнейшее очевидно. Задача 10: Сколькими способами можно отметить в таблице 5 × 10 две клетки? Решение: это еще одна пара к задаче 2 (и к задаче 4). Расположим в таблице 5 × 10 точки, соответствующие 50 вершинам многоугольника. Отрезок, соединяющий пару вершин, – это либо сторона, либо диагональ. Нам нужно посчитать и те, и другие. Задача 11: а) В левом верхнем углу доски 10 × 8 стоит ладья. Двое по очереди ходят ею, причём разрешается ходить только вправо или вниз. Выигрывает тот, кто ставит ладью в правый нижний угол. Кто выиграет при правильной игре: тот, кто ходит первым, или его партнер? б) В одной кучке лежит 7 спичек, в другой – 9. За один ход разрешается взять любое число спичек, но только из одной кучки. Выиграл тот, кто взял последнюю спичку. Кто выиграет при правильной игре? Решение: Заметим, что ладья может сдвинуться всего вправо на 9 клеток, а вниз – на 7. Будем кодировать каждый такой сдвиг взятием спичек из кучки. (А когда сдвинуться нельзя – это значит, что кучка опустела!) Выигрышная стратегия: сначала взять 2 спички из кучки-9 (встать ладьей на диагональ), а затем повторять ходы противника в другой кучке (возвращать ладью на диагональ). Задача 12: а) В городе Колоколамске живут 10 шпионов по кличкам Нелли, Одри, Долли, Тилли, Чарли, Петя, Штирлиц, Супер, Вилли, Деловой. Нелли шпионит за Супером, Одри – за Чарли и Тилли, Долли – за Одри, Штирлицем и Вилли, Тилли – за Петей и Деловым, Чарли – за Долли и Деловым, Петя – за Штирлицем и Долли, Штирлиц – за Тилли и Петей, Супер – за Нелли и Вилли, Вилли – за Чарли, Деловой – за Одри и Вилли. Какое наибольшее число шпионов сможет выстроиться в очередь так, чтобы перед каждым, кроме первого, стоял тот, за кем он шпионит? б) Какое наибольшее количество различных цифр можно выписать в ряд так, чтобы, подчеркнув любые две соседних, мы получили двузначное число, делящееся на 7 или 13? Число 07 тоже считается двузначным. Решение: Все 10. Например, 0784291356. Теперь к задаче 12a. Закодируем шпионов цифрами (Нелли = Ноль, Одри = Один, и т.д.) Шпионство обозначим стрелочкой: 0 → 7; 1 → 4,3; 2 → 1,6,8; 3 → 5,9; 4 → 2,9; 5 → 6,2; 6 → 3,5; 7 → 0,8; 8 → 4; 9 → 1,8. Обратим внимание на то, что выписаны все «двузначные числа», которые делятся на 7 или 13. Дальше остается решить любую из задач. Задача 13: а) Летучая ладья ходит как обычная, только не может становиться на соседнюю клетку. Может ли она пройти по доске 4 × 4, побывав на каждой ее клетке ровно один раз? б) Хромая ладья ходит как обычная, но только на соседнюю клетку. Может ли она пройти по доске 4 × 4, побывав на каждой ее клетке ровно один раз? Решение: Поля доски для летучей ладьи и поля доски для хромой ладьи находятся в таком соответствии:  (Если на левом рисунке может сделать ход хромая ладья, то на правом ход между аналогичными клетками будет у летучей ладьи. И наоборот: для каждого хода летучей ладьи на правом рисунке будет существовать соответствующий ход хромой ладьи на левом.) Принцип Дирихле Задача 1: Пятнадцать мальчиков собрали вместе 100 орехов. Докажите, что какие-то двое из них собрали одинаковое количество орехов. Решение: Предположим противное – тогда мальчики собрали не меньше, чем 0 + 1 + 2 + … + 14 = 105 орехов. Противоречие. Задача 2: 10 друзей послали друг другу праздничные открытки. Каждый послал 5 открыток. Докажите, что двое послали открытки друг другу. Решение: Всего было послано 50 открыток. Число «неориентированных» пар школьников равно  , поэтому на какую-то пару приходится не менее двух открыток, ч.т.д. Задача 3: Докажите, что в любой момент однокругового чемпионата найдутся две команды, сыгравшие одинаковое число матчей. Решение: Не может существовать двух команд, одна из которых не сыграла ни одного матча, а другая – все матчи. Задача 4: Числа 1, 2, …, 7 разбиты на две группы. Докажите, что произведение чисел хотя бы в одной из групп меньше 72. Задача 5: Цифры 1, 2, …, 9 разбили на 3 группы. Докажите, что произведение чисел в хотя бы одной группе меньше 72. Решение: Перемножим числа в трёх группах и докажем, что 9! < 72³. Задача 6: Докажите, что из любых 10 чисел можно выбрать несколько, сумма которых делится на 10. Решение: Эта задача содержит идею «вспомогательной последовательности сумм». Рассмотрим 10 сумм a1, a1 + a2, …a1 + a2 + … + a10. Среди них либо есть сумма, делящаяся на 10, либо две суммы с одинаковыми последними цифрами. Задача 7: Докажите, что из 65 целых чисел всегда можно найти ровно 9 таких, сумма которых делится на 9. Решение: Рассмотрим, сколько из чисел имеют одинаковые остатки при делении на 9. Если какой-то из остатков повторяется не менее 9 раз, то берем ровно 9 чисел с этим остатком. Если же такого остатка нет, то среди 65 чисел обязательно встретятся все 9 различных остатков. Возьмем по одному «представителю» – их сумма будет кратна 9. Задача 8: Докажите, что из 65 целых чисел либо найдутся 9 таких, что каждое из чисел этой девятки, кроме последнего, делится на число, стоящее за ним, либо найдется девять таких чисел, что ни одно из них не делится на другое. Решение: Будем выписывать в строчку числа до тех пор, пока следующее делится на предыдущее. Когда встретится число, не делящееся на предыдущее, начнем им новую строчку. В дальнейшем для каждого нового числа проверяем его делимость на последние числа во всех уже выписанных строчках, и если оно делится, то вписываем его. Если же делимости ни на одно из чисел нет, то снова начинаем новую строчку. В результате таких операций получим либо табличку, в которой более 8 строк, либо табличку, в которой хотя бы одна из строк содержит более восьми чисел. Задача 9: Верно ли, что среди любых 34 разных натуральных чисел, не превосходящих 50, всегда можно выбрать два числа, одно из которых вдвое больше другого? Решение: Да, верно. Разобьем числа на такие пары-клетки: (1,2), (3,6), (5,10), …, (25,50); (4,8), (12,24), (20,40); (16,32); Добавим к этим 17-ти парам ещё не использованные 16 чисел, не превосходящих 50 (27, 28, 29, 31, 33, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 49), каждое из них образует отдельную клетку. Всего получилось 33 клетки, поэтому в одну из них попадут хотя бы два данных числа. В «одноместную» клетку они попасть не могут, значит они попали в пару, так что одно из них действительно в два раза больше другого. |