Лекции по математике 269 Литература 274 Предисловие в этой книге собраны материалы по курсу математики в одном из классов московской Пятьдесят седьмой школы
 Скачать 1.26 Mb.
|
|
16. Как отложить на прямой отрезок в 3 см, имея металлический прямоугольник со сторонами 75 и 21 сантиметров? 17. К прямоугольнику, стороны которого не больше 1 метра, 20 раз применили операцию Евклида. Доказать, что стороны остав- шегося прямоугольника не превышают 1 мм. 18. Кузнечик умеет прыгать по прямой в любую сторону на расстояние 1 м и на расстояние √ 2 м. Доказать, что он может по- пасть в точку, отстоящую менее чем на 1 мм от исходной, но не совпадающую с ней. 19. Из угла прямоугольного биллиарда пускают шар под уг- лом 45 ∘ , который отражается от стенок по закону «угол падения равен углу отражения». Доказать, что шар снова попадёт в один из углов в том и только случае, если стороны биллиарда соизмеримы. (Шар считается точкой.) 20. Прямоугольник со сторонами 1 и π разрезают на квадра- ты описанным способом. Используя калькулятор, подсчитать число квадратов первых трёх уровней. При этом остаётся прямоугольник с почти равными сторонам. Как надо изменить отношение сторон исходного прямоугольника, чтобы остаточный прямоугольник стал квадратом? Задачи 1996 { 1997 года 59 21. Отношение двух отрезков равно 1,625, а меньший из них равен √ 2 . (а) Найти их наибольшую общую меру. (б) Найти наи- меньший отрезок, в котором оба они укладываются целое число раз. 22. Отрезок a соизмерим с отрезками b и c. Следует ли отсюда, что отрезки b и c соизмеримы между собой? 23. В трапеции средняя линия соизмерима с одним из основа- ний. Следует ли отсюда, что она соизмерима с другим основанием? 24. Будут ли следующие пары отрезков соизмеримы: (а) 2+3 √ 2 и 3 + 2 √ 2 ; (б) 1/ √ 2 и √ 2 ; (в) 1/( √ 2 − 1) и 2 + √ 2 ; (г) √ 2 и √ 3 ? Индукция 1. Доказать, что любая сторона (а) четырёхугольника; (б) пятиугольника; (в) произвольного n-угольника меньше суммы остальных его сторон. 2. Доказать, что (а) n! > 3 n для n = 7, 8, 9, . . . ; (б) 2 n > > n 2 для n = 4, 5, 6, . . . 3. Плоскость поделена на области несколькими прямыми. Доказать, что эти области можно так раскрасить в два цвета, что любые две соседние (граничащие по отрезку или лучу) области будут покрашены в разные цвета. 4. Доказать, что двузначные числа от 00 до 99 можно записать в таком порядке, что в каждом следующем отли- чается от предыдущего только одна цифра и ровно на 1. Доказать аналогичное утверждение для трёхзначных чисел (000, . . . , 999), четырёхзначных и т. д. 5. Доказать, что квадраты 4 × 4, 8 × 8, 16 × 16, . . . с вырезанной угловой клеткой можно разрезать на «уголки» из трёх клеток (квадраты 2 × 2 с вырезанным углом). 6. На сколько изменятся суммы 1 − 1 2 + 1 3 − 1 4 + . . . + 1 2n − 1 − 1 2n и 1 n + 1 + 1 n + 2 + 1 n + 3 + . . . + 1 2n − 1 + 1 2n , если увеличить n на 1? Доказать, что эти суммы равны друг другу при всех n. 60 Задачи 1996 { 1997 года 7. Число x+1/x | целое. Доказать, что числа x 2 +1/x 2 , x 3 + 1/x 3 , x 4 + 1/x 4 , . . . также целые. 8. Чтобы разрезать выпуклый n-угольник на треугольни- ки, проводя непересекающиеся диагонали, нужно ровно n−3 диагонали, не больше и не меньше. Почему? 9. Число 111 . . . 111 (3 n единиц) делится на 3 n . Почему? * * * 10. Игра «Ханойские башни» имеет три вертикальных стержня. На один из них надета пирамидка из колец разного размера (мень- шие на больших). (а) Как переложить кольца на другой стержень, если перекладывать можно только по одному, большее на меньшее класть нельзя, пирамидка состоит из n колец? (б) Доказать, что это можно сделать за 2 n − 1 перекладываний. (в) Доказать, что за меньшее число перекладываний это сделать невозможно. 11. Последовательность 2, 3, 5, 9, . . . составлена по такому пра- вилу: если из утроенного члена этой последовательности вычесть удвоенный предыдущий, то получится следующий (3 · 3 − 2 · 2 = 5, 3 · 5 − 2 · 3 = 9 и т. д.). Доказать, что все члены этой последова- тельности | степени двойки, увеличенные на 1. 12. Доказать, что квадрат размера 4 × 4, 8 × 8, 16 × 16, . . . с вырезанной клеткой (любой) можно разрезать на «уголки» из трёх клеток (квадраты 2 × 2 с вырезанным углом). 13. В стране n городов. Каждый год открывается авиасообще- ние между какими-то двумя городами. Доказать, что должно прой- ти по крайней мере n − 1 лет, прежде чем из любого города можно будет попасть в любой (с пересадками). 14. Один выпуклый многоугольник расположен внутри другого. Доказать, что периметр внутренного многоугольника меньше пери- метра внешнего. 15. На доске написаны два числа 1, 1. Затем между ними впи- сывают их сумму; получается 1, 2, 1. Затем между каждыми двумя снова вписывают их сумму: 1, 3, 2, 3, 1. Такое действие выполняют ещё 10 раз. Сколько чисел будет на доске? Какова будет их сумма? 16. Из чисел 1, 2, 3, 4, . . . , 2n − 1, 2n можно выбрать не более n чисел, если требуется, чтобы ни одно из выбранных чисел не дели- лось на другое. Доказать это (а) для n = 3; (б) для n = 4; (в) для n = 5 ; (г) для произвольного n. 17. В теории относительности скорости складываются по та- кому правилу: v, w ↦→ v+w 1+vw . Доказать, что результат сложения Задачи 1996 { 1997 года 61 нескольких скоростей не зависит от того, в каком порядке мы их складываем. 18. Доказать, что 2 n > n 10 при n > 100. 19. В последовательности из 10 нулей и единиц разрешается (1) менять первый член; (2) менять член, стоящий после первой единицы. Доказать, что из любой последовательности можно полу- чить любую. Неравенства и оценки 1. Все стороны треугольника меньше 1. Может ли его площадь быть больше 100? 2. Все стороны треугольника больше 100. Может ли его площадь быть меньше 1? 3. Все высоты треугольника больше 100. Может ли его площадь быть меньше 1? 4. Сумма нескольких положительных чисел больше 1. Может ли сумма их квадратов быть меньше 0,001? 5. Сумма нескольких положительных чисел меньше 1. Может ли сумма их квадратов быть больше 100? 6. Сумма двух положительных чисел больше 10. Может ли их произведение быть меньше 0,001? 7. Произведение двух положительных чисел больше 10. Может ли их сумма быть меньше 0,001? 8. Стороны прямоугольника увеличили на сантиметр. Мо- жет ли его площадь увеличиться более чем на квадратный метр? 9. Два положительных числа отличаются не более чем на 0,1. Могут ли их квадраты отличаться более чем на 10? 10. Два положительных числа отличаются не более чем на 0,1. Могут ли их квадратные корни отличаться более чем на 10? * * * 11. Все медианы треугольника меньше 1. Может ли его площадь быть больше 100? 12. Все высоты треугольника меньше 1. Может ли его площадь быть больше 100? 62 Задачи 1996 { 1997 года Сумма и произведение двух чисел 1. Сумма двух положительных чисел равна 2. Доказать, что их произведение не превосходит 1. 2. Сумма двух положительных чисел меньше 2. Доказать, что их произведение меньше 1. 3. Доказать, что x + 1/x > 2 для любого положительно- го x 4. Из всех прямоугольников данного периметра наиболь- шую площадь имеет квадрат. Почему? 5. Из всех прямоугольников данной площади наименьший периметр имеет квадрат. Почему? 6. Доказать, что √ xy 6 (x + y)/2 для любых неотрица- тельных x, y. 7. Доказать, что xy 6 (x 2 + y 2 )/2 для любых x и y. 8. Доказать, что при постоянной сумме двух чисел их произведение тем больше, чем ближе числа друг к другу. * * * 9. Рычажные весы имеют не совсем одинаковые плечи, и потому продавец отвешивал один килограмм сахара на левой чашке весов, а второй (тому же покупателю) | на правой. Выиграл покупатель или проиграл? 10. Корабль плывёт из А в Б по течению реки, а затем возвра- щается против течения (скорости течения и корабля постоянны). Потратит ли он на все путь больше или меньше времени, чем на равный путь по озеру? 11. Какую наибольшую площадь можно отгородить на берегу прямоугольным забором длины не более 100 метров? (Четвёртая сторона прямоугольника | берег; там забор не нужен.) 12. Доказать неравенство √ xy 6 (x + 2y)/(2 √ 2) Системы счисления 1. Имеется 6 больших мешков с монетами, во всех мо- неты настоящие и весят 10 граммов, а в одном фальшивые и на один грамм легче. Как с помощью одного взвешивания (на весах, показывающих суммарный вес положенных на них монет) определить, в каком мешке фальшивые монеты? Задачи 1996 { 1997 года 63 2. Тот же вопрос, если фальшивые монеты могут быть в нескольких мешках. 3. Доказать, что каждое целое положительное число мож- но представить в виде суммы различных степеней двойки, причём единственным способом. 4. Продолжить таблицу и объяснить правило её построе- ния: 0 1 2 3 4 5 0 1 10 11 100 101 (Записи в нижней строке называют сделанными в двоичной системе счисления.) 5. На доске написано число 0. С написанным числом раз- решается выполнять два действия: (1) увеличить его вдвое; (2) увеличить его вдвое и прибавить 1. Сколькими способами можно получить на доске число 1000 (если вообще можно)? 6. Найти четыре тройки целых неотрицательных чисел, чтобы выполнялось такое свойство: каждое число от 0 до 80 можно представить в виде суммы четырёх чисел | по одному из каждой тройки. 7. На доске написано число 0. С написанным числом раз- решается выполнять два действия: (1) увеличить его втрое; (2) увеличить его втрое и прибавить 1. Число назовём до- ступным, если его можно получить на доске таким способом. Сколько доступных чисел от 0 до 1000? * * * 8. Разложить 1/3 в двоичную периодическую дробь. 9. Превратить двоичную периодическую дробь 0,101101101. . . в обыкновенную. 10. Перевести восьмеричное число 2736454 в 16-ричную сис- тему. 11. В последовательности чисел 1, 2, 3, 5, 8, . . . (числа Фибонач- чи) каждое число равно сумме двух предыдущих. Доказать, что любое целое положительное число можно представить в виде сум- мы некоторых чисел Фибоначчи, среди которых нет стоящих рядом, и что это можно сделать ровно одним способом. 12. Купец хочет взвешивать любое количество фунтов товара от 0 до 40 с помощью чашечных весов, имея всего четыре гири 64 Задачи 1996 { 1997 года (которые можно класть на любую из чашек). Удастся ли ему это? (Делать несколько взвешиваний нельзя.) 13. Бесконечная вправо и вниз таблица заполняется по такому правилу: в каждую клеточку ставится минимальное целое неотри- цательное число, которого нет ни слева, ни сверху от него. (Таким образом, первая строка и первый столбец содержат числа 0, 1, 2, 3, . . . ) Какое число стоит в 101-ой строке на 201-ом месте? Каково общее правило? Рекуррентные формулы 1. Пешка стоит в углу доски 5 × 5 на поле ⟨1, 1⟩. За один ход ей разрешается сдвинуться вправо или вверх. Найти для каждого поля доски, сколькими способами пешка может на него попасть (например, на поле ⟨2, 2⟩ можно попасть двумя способами: вправо { вверх и вверх { вправо). 2. (Продолжение) Тот же вопрос, если можно идти впра- во, вверх, и по диагонали (вправо-вверх). 3. (Продолжение) Тот же вопрос, если можно идти впра- во и вверх и нельзя делать два шага вправо подряд. 4. Обозначим через a(m, n) количество различных по- следовательностей, составленных из m нулей и n единиц. Доказать, что a(m, n) = a(m − 1, n) + a(m, n − 1) при лю- бых m, n > 0. Составить таблицу a(m, n) для 0 6 m, n 6 5. 5. Для n = 1, 2, 3, . . . , 9, 10 найти количество (а) всех последовательностей нулей и единиц длины n; (б) тех из них, в которых нет двух идущих подряд нулей; (в) тех из них, в которых нет трёх идущих подряд нулей. 6. Сколькими способами можно расставить скобки в про- изведении n сомножителей? Для n = 3, 4, 5 это число было подсчитано; сделать это для n = 6, 7, 8. (Указание. Послед- нее умножение может быть в одной из n−1 позиций, поэтому искомое число равно сумме . . . ) 7. Рассмотрим все разбиения целого положительного чи- сла n в сумму целых положительных слагаемых (разбиения, отличающиеся порядком, мы считаем за одно). Подсчитать количество разбиений числа n, у которых все слагаемые не превосходят m, при m и n, не превосходящих 8. Ответом Задачи 1996 { 1997 года 65 должна быть таблица 8 × 8. (Указание. Все разбиения чи- сла n, в которых слагаемые не превосходят m, делятся на две группы: где слагаемые не превосходят m − 1 и где наи- большее слагаемое равно m.) * * * 8. На окружности имеется 2n точек. Сколькими способами их можно соединить n непересекающимися хордами? Подсчитать это число для n = 1, 2, 3, 4, . . . , 7. 9. Имеется выпуклый n-угольник. Сколькими способами его можно разрезать на треугольники, проводя непересекающиеся диа- гонали? Подсчитать это число для n = 3, 4, 5, . . . , 8. 10. Кольцевой забор состоит из n досок, каждую из них надо покрасить в один из трёх цветов, причём соседние доски должны быть покрашены в разные цвета. Сколькими способами можно это сделать для n = 3, 4, 5, 6? Найти общую формулу для произволь- ного n. 11. На контурной карте нарисовано несколько стран, каждую из которых надо раскрасить в один из n цветов, причём соседние страны должны быть раскрашены в разные цвета. Доказать, что количество вариантов раскраски есть многочлен от n. 12. Рассмотрим раскраски забора из n досок в три цвета так, чтобы соседние доски были раскрашены в разные цвета. Пусть d n | число способов раскрасить забор для фиксированных и раз- личных цветов крайних досок, а e n | то же число для одинаковых цветов крайних досок. Найти e n и d n для n = 3, 4, 5, 6, 7. 13. Сколько решений имеет уравнение x 1 + x 2 + x 3 + . . . + x m = = n , если все x i должны быть равны 0 или 1? Подсчитать ответ для 1 6 m, n 6 7. 14. (Продолжение) Тот же вопрос, если все x i должны быть равны 0, 1 или 2. 15. Автобусный билет называется счастливым, если сумма пер- вых трёх его цифр равна сумме последних трёх. Подсчитать число счастливых билетов. (Указание. Один из возможных способов: под- считать для двузначных и четырёхзначных билетов, сколько име- ется билетов с данной разностью между суммами первой и второй половин.) 16. Для n = 1, 2, 3, . . . , 9, 10 найти количество последователь- ностей нулей и единиц длины n, в которых нет комбинации 001; тот же вопрос для комбинации 0101. 66 Задачи 1996 { 1997 года Взаимно однозначные соответствия 1. Сколько (а) пятизначных чисел, содержащих только цифры 1 и 2? (б) вариантов освещения коммунальной кух- ни, где у каждой из пяти соседок | своя лампочка? (в) сла- гаемых в произведении (a + b)(c + d)(e + f)(g + h)(i + j)? (г) подмножеств у пятиэлементного множества (в подмноже- ство каждый элемент может входить или не входить, порядок элементов не учитывается)? Как убедиться, что во всех этих задачах ответ одинаков, не решая ни одной из них? 2. (а) Сколькими способами можно назначить двух де- журных среди пяти зазевавшихся школьников? (б) Город имеет форму прямоугольника 3×2, который разбит прямыми улицами на квадраты 1×1. Сколько кратчайших путей ведут из одного угла в противоположный? (в) Какой коэффици- ент окажется при a 3 b 2 , если раскрыть скобки в выражении (a + b) 5 и привести подобные слагаемые? (г) Сколько раз- личных слов можно получить, переставляя буквы в слове ïçïçï? (д) Сколько двухэлементных подмножеств у пяти- элементного множества? (е) Сколько трёхэлементных под- множеств у пятиэлементного множества? Как убедиться, что во всех этих задачах ответ одинаков, не решая ни одной из них? 3. Сколько решений в целых неотрицательных числах имеет уравнение x + y + z = 3? Почему в этой задаче ответ тот же самый, что и в предыдущей? (Указание: ïçïçï ↔ ↔ 1 + 1 + 1, ççïïï ↔ 0 + 0 + 3, . . . ) 4. Почему число решений уравнения x + y + z = 30 в по- ложительных целых числах равно числу решений уравнения x + y + z = 27 в неотрицательных целых числах? 5. Каких подмножеств больше у множества {1, 2, 3, . . . , 9, 10 } | содержащих 1 или не содержащих 1? 6. Все последовательности из 20 нулей и единиц делятся на две группы | те, в которых чётное число единиц, и те, в которых нечётное. Каких больше? 7. Сколько существует шестизначных автобусных биле- тов, сумма цифр которых чётна? Задачи 1996 { 1997 года 67 * * * 8. Доказать, что счастливых автобусных билетов (у которых сумма первых трёх цифр равна сумме трёх последних) столько же, сколько автобусных билетов с суммой цифр 27. 9. Доказать, что число разбиений выпуклого n-угольника на треугольники непересекающимися диагоналями равно числу спосо- бов расстановки скобок в произведении n − 1 сомножителей. 10. Доказать, что количество разбиений целого положительного числа n на целые положительные слагаемые, не превосходящие k, равно количеству разбиений числа n на не более чем k целых по- ложительных слагаемых. 11. Сколько существует автобусных билетов, сумма цифр кото- рых делится на 3? Принцип Дирихле 1. В математической олимпиаде участвовало 900 школь- ников. Доказать, что можно найти трёх участников, у кото- рых общий день рождения. 2. В классе 25 школьников, которые писали четыре кон- трольные; ни один школьник не прогулял ни одну из кон- трольных, и все они получили четвёрки и пятёрки. Доказать, что найдутся два школьника, у которых результаты за все контрольные одинаковы. 3. Двенадцати школьникам досталось 65 конфет. Дока- зать, что какие-то двое школьников съели одинаковое число конфет. 4. В квадрате со стороной 10 выбрано 100 точек. Может ли так случиться, что расстояние между любыми точками не меньше 2? 5. Боря утверждает, что может отгадать любое целое чи- сло от 1 до 100, задав не более 6 вопросов, требующих ответа «да» или «нет». Почему он не прав? Скольких вопросов было бы достаточно? Почему? 6. На контрольной каждую задачу решило не меньше по- ловины школьников. Доказать, что есть школьник, решив- ший не меньше половины задач. 7. Доказать, что равносторонний треугольник нельзя на- крыть двумя равносторонними треугольниками меньшего раз- 68 Задачи 1996 { 1997 года мера. 8. Написано 10 положительных чисел, причём сумма лю- бых трёх из них больше 6. Доказать, что сумма всех чисел больше 20. 9. Какое максимальное количество целых чисел можно написать, если требуется, чтобы сумма и разность любых двух из них не делилась на 37? * * * 10. Футбольный турнир проводится в один круг (каждая коман- да играет с каждой). Доказать, что в любой момент турнира най- дутся две команды, сыгравшие одинаковое число матчей. 11. В клетках шахматной доски 100 на 100 написаны целые числа, причём числа в соседних клетках отличаются не более чем на 20. Доказать, что на доске есть три одинаковых числа. 12. Имеется 11 бесконечных десятичных дробей. Доказать, что найдутся две дроби, совпадающие в бесконечном числе разрядов. |