Задачи. Олимпиадные задачи по математике за 6 класс - Погребникова Алена. Арифметика На карточках записаны цифры 1, 2, Из этих карточек составлены числа и записано неверное равенство. Покажите, как, переместив только одну карточку, сделать равенство верным. 1
 Скачать 0.53 Mb.
|
Принцип Дирихле". Решения.Задача 1: В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок. Решение: Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной клетке, то количество иголок у них одинаково. Задача 2: Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11. Решение: Остатки по модулю 11 – «клетки», числа – «кролики». Задача 3: В городе Ленинграде живет более 5 миллионов человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове менее миллиона волос. Решение: Постройте миллион клеток с номерами от 0 до 999999 и рассадите там людей, поместив каждого ленинградца в клетку, номер которой равен количеству волос на его голове. Задача 4: В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта. Решение: 25 ящиков-«кроликов» рассадим по 3 клеткам-сортам. Так как 25 = 3 • 8 + 1, то применим «обобщенный принцип Дирихле» для N = 3, k = 8 и получим, что в какой-то клетке-сорте не менее 9 ящиков. Задача 5: В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну. Решение: Так как перевезено всего 10m + 1 футболистов, то, рассадив их по клеткам-командам, получаем, что в какой-то клетке сидит 11 футболистов. Задача 6: Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых. Решение: Различных разностей может быть 14 – от 1 до 14 – это те 14 клеток, в которые мы будем сажать кроликов. Кто же будет нашими кроликами? Ими, конечно, должны быть разности между парами данных нам натуральных чисел. Однако имеется 28 пар и их можно рассадить по 14 клеткам так, что в каждой клетке будет сидеть ровно два «кролика» (и значит, в каждой меньше трех). Здесь надо использовать дополнительное соображение: в клетке с номером 14 может сидеть не более одного кролика, ведь число 14 можно записать как разность двух натуральных чисел, не превосходящих 15, лишь одним способом: 14 = 15 – 1. Значит, в оставшихся 13 клетках сидят не менее 27 кроликов, и применение обобщенного принципа Дирихле дает нам желаемый результат. Задача 7: Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании. Решение: Вариантов числа знакомых всего 5: от 0 до 4. Осталось заметить, что если у кого-то 4 знакомых, то ни у кого не может быть 0 знакомых. Задача 8: Несколько футбольных команд проводят турнир в один круг. Докажите, что в любой момент турнира найдутся две команды, сыгравшие к этому моменту одинаковое число матчей. Решение: Пусть всего команд n. Тогда вариантов числа команд, с которыми сыграла данная команда n: от 0 до n – 1. Осталось заметить, что если одна команда сыграла со всеми n – 1-й, то никакая другая команда не могла ни с кем не сыграть. Задача 9: а) Какое наибольшее число полей на доске 8 ? 8 можно закрасить в черный цвет так, чтобы в любом уголке вида из трех полей было по крайней мере одно незакрашенное поле? б) Какое наименьшее число полей на доске 8 ? 8 можно закрасить в черный цвет так, чтобы в каждом уголке вида было по крайней мере одно черное поле? Решение: а) Разбейте доску на 16 квадратиков 2 ? 2 – это клетки; кроликами, конечно, будут черные поля. Задача 10: 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно две задачи и школьники, решившие ровно три задачи. Докажите, что есть школьник, решивший не менее пяти задач. Решение: Из условий следует, что найдутся 7 школьников, решивших 35 – 6 = 29 задач. Так как 29 = 4 • 7 + 1, то найдется школьник, решивший не менее пяти задач. Задача 11: Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга? Решение: Ответ: 16 королей. Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля. Задача 12: Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками. Решение: Каждый из меньших треугольников не может накрывать более одной вершины большого треугольника. Задача 13: В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см. Решение: Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадет по крайней мере три точки из 51 брошенной. Задача 14: Пятеро молодых рабочих получили на всех зарплату – 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты. Решение: Если бы каждый из рабочих мог купить магнитофон, то у них в сумме было бы не менее 5 • 320 = 1600 рублей. Задача 15: В бригаде 7 человек и их суммарный возраст – 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142 лет. Решение: Покрасим всю сушу в синий цвет, а все точки, диаметрально противоположные суше – в красный. Тогда обязательно есть точка, которая покрашена в оба цвета. В ней и надо рыть туннель. Задача 16: Докажите, что среди степеней двойки есть две, разность которых делится на 1987. Решение: Рассмотрите 1988 степеней и их остатки по модулю 1987. Задача 17: Докажите, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100. Решение: Квадраты при делении на 100 могут давать лишь 51 остаток, так как остатки x и 100 – x при возведении в квадрат дают один и тот же остаток. Задача 18: Докажите, что среди чисел, записываемых только единицами, есть число, которое делится на 1987. Решение: Рассмотрим 1988 чисел-«кроликов» 1, 11, 111, …, 111 … 11 (1988 единиц) и посадим их в 1987 клеток с номерами 0, 1, 2, …, 1986 – каждое число попадает в клетку с номером, равным остатку от деления этого числа на 1987. Тогда (по принципу Дирихле) найдутся два числа, которые имеют одинаковые остатки при делении на 1987. Пусть это числа 11 … 11 (m единиц) и 11 … 11 (n единиц), причем m > n. Но их разность, которая делится на 1987, равна 11 … 1100 … 00 (m – n единиц и n нулей). Сократим все нули – ведь они не имеют никакого отношения к делимости на 1987 – и получим число из одних единиц, которое делится на 1987. Задача 19: Докажите, что существует степень тройки, оканчивающаяся на 001. Решение: Если 3m и 3n – степени тройки, дающие один и тот же остаток при делении на 1000, то 3m – 3n = 3n(3m – n – 1) делится на 1000 (мы считаем для определенности, что m > n). Задача 20: В клетках таблицы 3 ? 3 расставлены числа – 1, 0, 1. Докажите, что какие-то две из 8 сумм по всем строкам, всем столбцам и двум главным диагоналям будут равны. Решение: Эти суммы могут принимать лишь 7 разных значений: от – 3 до 3. Задача 21: Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что какие-то два мужчины сидят друг напротив друга. Решение: Разобьем всех людей на 50 пар так, что в каждой паре – два человека, сидящих друг напротив друга. Ясно, что в одной из этих пар-«клеток» оба человека – мужчины. Задача 22: 15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов. Решение: Если это не так, то, очевидно, что мальчики собрали не менее, чем 0 + 1 + 2 + … + 14 = 105 орехов – противоречие. Задача 23: Цифры 1, 2, …, 9 разбили на три группы. Докажите, что произведение чисел в одной из групп не меньше 72. Решение: Произведение чисел во всех группах равно 9! = 362880, а 71? = 357911. Задача 24: В таблице 10 ? 10 расставлены целые числа, причем любые два числа в соседних клетках отличаются не более, чем на 5. Докажите, что среди этих чисел есть два равных. Решение: Поскольку от любой клетки до любой другой можно добраться, не более 19 раз сдвинувшись в соседнюю клетку, то все числа находятся между числами a и a + 95, где a – минимальное из всех расставленных чисел. Значит, среди этих чисел не более 96 различных. Задача 25: Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых. Решение: У данного человека среди остальных пяти есть либо не менее трех знакомых, либо не менее трех незнакомых ему. Разберем, например, первый случай. Среди этих трех людей есть либо двое знакомых – тогда они вместе с выбранным нами исходно человеком образуют нужную тройку, либо они все трое попарно незнакомы. Задача 26: На клетчатой плоскости дано 5 произвольных узлов сетки. Докажите, что середина одного из отрезков, соединяющих какие-то две из этих точек, также является узлом сетки. Решение: Рассмотрите координаты этих точек и их остатки при делении на 2. Задача 27: На складе имеется по 200 сапог 41, 42 и 43 размеров, причем среди этих 600 сапог 300 левых и 300 правых. Докажите, что из них можно составить не менее 100 годных пар обуви. Решение: В каждом размере каких-то сапог меньше: правых или левых. Выпишем эти типы сапог по размерам. Какой-то тип, например, левый, повторится по крайней мере дважды, например, в 41 и 42 размерах. Но так как количество левых сапог в этих размерах суммарно не меньше 100 (почему?), то мы имеем не менее 100 годных пар обуви в этих размерах. Задача 28: В алфавите языка племени Ни-Бум-Бум 22 согласных и 11 гласных, причем словом в этом языке называется произвольное буквосочетание, в котором нет двух согласных подряд и ни одна буква не использована дважды. Алфавит разбили на 6 непустых групп. Докажите, что из всех букв одной из групп можно составить слово. Решение: Докажите, что в одной из групп разность между числом согласных и числом гласных не больше 1. Задача 29: Докажите, что среди любых 10 целых чисел найдется несколько, сумма которых делится на 10. Решение: Рассмотрите 10 сумм: x1, x1 + x2, …, x1 + x2 + … + x10 и их остатки при делении на 10. Задача 30: Дано 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать два числа, одно из которых делится на другое. Решение: Разбейте числа от 1 до 20 на 10 наборов, в каждом из которых в любой паре чисел одно делится на другое: 11, 13, 15, 17, 19, 1,2,4,8,16, 3,6,12, 5,10,20, 7,14, 9,18. "Делимость и остатки". Ответы.Задача 1: а) a + 1 делится на 3. Докажите, что 4 + 7a делится на 3. б) 2 + a и 35 – b делятся на 11. Докажите, что a + b делится на 11. Решение: Указания: а) 4 + 7a = 4(a + 1) + 3a; б) a + b = (2 + a) – (35 – b) + 33. Задача 2: Найдите последнюю цифру числа 1? + 2? + … + 99?. Решение:0 Задача 3: Про семь натуральных чисел известно, что сумма любых шести из них делится на 5. Докажите, что каждое из данных чисел делится на 5. Решение: Докажите, что любые два числа из этих семи дают одинаковый остаток от деления на 5. Для этого рассмотрите две шестерки: одну – не содержащую первое из них, вторую – не содержащую второе. Задача 4: Найдите наименьшее число, дающее следующие остатки: 1 – при делении на 2, 2 – при делении на 3, 3 – при делении на 4, 4 – при делении на 5, 5 – при делении на 6. Решение: Заметим, что это число, увеличенное на 1, делится на 2, 3, 4, 5, 6. Ответ: 59. Задача 5: Докажите, что если (n – 1)! + 1 делится на n, то n – простое число. Решение: Если n – составное число (n > 4), то (n – 1)! делится на n. Задача 6: Докажите, что существует такое натуральное n, что числа n + 1, n + 2, …, n + 1989 – составные. Решение: Попробуем рассказать, как можно придти к решению. Число n + 1 должно быть составным. Попытаемся пойти по самому простому пути: сделаем так, чтобы n + 1 делилось на 2. n + 2 также должно быть составным, но делиться на 2 уже не может. Попытаемся опять пойти по самому простому пути: хотелось бы сделать так, чтобы n + 2 делилось на 3. Продолжая в том же духе, можно пытаться найти число n такое, что n + 1 делится на 2, n + 2 – на 3, n + 3 – на 4 и так далее. Это равносильно тому, что n – 1 делится на 2, 3, 4, …, 1990. Такое число, конечно, существует – например, 1990!. Итак, в качестве искомого n можно взять число 1990! + 1. Задача 7: Докажите, что существует бесконечно много простых чисел. Решение: Предположим противное. Пусть p1, p2, …, pn – все простые числа. Рассмотрим число p1p2 … pn + 1. Это число не делится ни на одно из чисел p1, p2, …, pn и, следовательно, не может быть разложено в произведение простых. Противоречие. Алгоритм Евклида".Ответы.Задача 1: Найти наибольший общий делитель чисел 2n + 13 и n + 7. Решение: НОД (2n + 13,n + 7) = НОД (n + 7,n + 6) = НОД (n + 6,1) = 1. Задача 2: Найдите НОД (2??? – 1,2??? – 1). Решение: Указание: Воспользуйтесь алгоритмом Евклида. Задача 3: Найдите НОД (111 … 111,11 … 11) – в записи первого числа 100 единиц, в записи второго – 60. Решение: Указание: Воспользуйтесь алгоритмом Евклида. |