Лекции по математике 269 Литература 274 Предисловие в этой книге собраны материалы по курсу математики в одном из классов московской Пятьдесят седьмой школы
 Скачать 1.26 Mb.
|
|
13. Имеется 4 различных по весу камня. Как упорядочить камни по весу, сделав не более 5 взвешиваний на чашечных весах без гирь? Можно ли придумать способ, гарантирующий это за 4 взвешивания? 14. Та же задача для 5 камней. 15. В таблице из 11 строк и 10 столбцов написаны целые числа. Доказать, что можно вычеркнуть некоторые строки (не все | воз- можно, ни одной), после чего сумма чисел в каждом столбце будет чётной. Треугольник Паскаля Число k-элементных подмножеств n-элементного множе- ства называется числом сочетаний из n по k, и обозначается C k n (или (︀ n k )︀ ). 1. Чему равны C 0 n и C n n ? Доказать, что C k n = C n−k n при n > 0 и 0 6 k 6 n. 2. Доказать, что C k n = n! k!(n − k)! 3. Доказать, что C k n = C k n−1 + C k−1 n−1 Задачи 1996 { 1997 года 69 4. С использованием обозначения C k n записать (а) число последовательностей из a нулей и b единиц; (б) число ре- шений уравнения x 1 + x 2 + . . . + x m = d , где все x 1 , . . . , x m равны 1 или 2 (здесь m и d | целые положительные числа, m 6 d). 5. С использованием обозначения C k n записать число ре- шений уравнения x 1 + x 2 + . . . + x m = d (а) в целых неотри- цательных числах; (б) в целых положительных числах. 6. Переплётчик должен переплести 12 одинаковых книг в красный, синий или зелёный переплёты. Сколькими спо- собами он может это сделать? (Не обязательно использовать все цвета.) 7. В треугольнике Паскаля C 0 0 C 0 1 C 1 1 C 0 2 C 1 2 C 2 2 C 0 3 C 1 3 C 2 3 C 3 3 C 0 4 C 1 4 C 2 4 C 3 4 C 4 4 вычислить первые 7 строк. 8. Доказать, что в треугольнике Паскаля каждое число равно сумме двух стоящих над ним. 9. Вычислить сумму чисел в первых 7 строках треуголь- ника Паскаля. Объяснить наблюдаемую закономерность. 10. Знакопеременная сумма чисел в любой строке тре- угольника Паскаля равна нулю. (Другими словами: сумма чисел, стоящих на чётных местах в любой строке, равна сум- ме чисел, стоящих на нечётных местах.) Почему? * * * 11. Доказать, что произведение любых 11 последовательных де- лится на 11! (факториал 11). 12. Сколько есть подмножеств множества {1, 2, 3, . . . , n}, для которых выполнено такое условие: никакие два их элемента не от- личаются ровно на 1? 70 Задачи 1996 { 1997 года 13. Сколькими способами можно переставить буквы в слове âòáëïäåì, если требуется, чтобы и гласные, и согласные (по от- дельности) шли в алфавитном порядке? 14. Вычислить 11 2 , 11 3 , 11 4 . Сравнить результат с треугольни- ком Паскаля. Объяснить наблюдаемую закономерность. Будет ли она продолжаться и дальше? Тот же вопрос для чисел 1001 2 , 1001 3 , . . . 15. Какие строки треугольника Паскаля состоят целиком из нечётных чисел? целиком (не считая краёв) из чётных чисел? 16. Какие строки треугольника Паскаля состоят целиком (не считая краёв) из чисел, делящихся на 3? 17. Возьмём любое число в треугольнике Паскаля и сложим все элементы, начиная с него и идя по прямой вверх-налево. Сумма окажется равной элементу, стоящему снизу под ним. Почему? Комбинаторика и алгебра 1. Доказать, что коэффициент при x 10 , который получит- ся после раскрытия скобок и приведения подобных в (1+x+ + x 2 + x 3 + . . . + x 9 + x 10 ) 3 , равен числу решений уравнения a + b + c = 10 в целых неотрицательных числах. 2. Найти коэффициент при abcde в (a + b + c + d + e) 5 3. Доказать, что число способов разменять 20 долларов бумажками в 1, 2 и 5 долларов равно коэффициенту при x 20 в выражении (1 + x + x 2 + x 3 + . . . + x 20 ) · (1 + x 2 + x 4 + x 6 . . . + x 20 ) × × (1 + x 5 + x 10 + x 15 + x 20 ). 4. Доказать формулу бинома Ньютона: (a + b) n =a n +C 1 n a n−1 b + . . . + C k n a n−k b k + . . . +C n−1 n ab n−1 +b n 5. Используя формулу бинома, доказать, что сумма чисел в любой строке треугольника Паскаля есть степень 2 и что знакопеременная сумма чисел в любой строке равна 0. 6. Найти коэффициент при a 10 b 15 c 20 в (a + b + c) 45 7. Гоша вычислил произведение (1+x)·(1+x 2 ) ·(1+x 4 ) × × (1 + x 8 ) · (1 + x 16 ) . Тоша доказал, что, имея по одной гире в 1, 2, 4, 8 и 16 граммов, можно набрать любой вес от 1 Задачи 1996 { 1997 года 71 до 31 грамма, причём единственным способом. Юра сказал Гоше и Тоше: «Вы решали одну и ту же задачу». Почему он так сказал? Сравнения Говорят, что числа a и b сравнимы по модулю m, ес- ли их разность делится на m. (Числа предполагаются целы- ми; мы считаем, что модуль m положителен.) Обозначение: a ≡ b( mod m). 1. Доказать, что a ≡ b(mod m) в том и только том слу- чае, когда a и b дают одинаковые остатки при делении на m. 2. Найти положительное целое число, которое сравнимо с −1 по любому из модулей 1, 2, 3, 4, 5, 6, 7. 3. Доказать, что сравнения по одному модулю можно складывать и перемножать: если a ≡ b(mod m) и c ≡ d(mod m), то a + c ≡ b + d(mod m) и ac ≡ bd(mod m). 4. Доказать, что если a≡b(mod m), то a n ≡b n ( mod m) при n = 1, 2, 3, 4, . . . 5. Доказать, что a n ≡ b n ( mod (a − b)) при n = 1, 2, 3, 4, . . . (и при любых a ̸= b). 6. Какие остатки может давать точный квадрат при де- лении на 3, 5 и 7? 7. Найти остатки от деления 16 101 и 18 101 на 17. 8. Доказать, что четырёхзначное число abcd сравнимо с a + b + c + d по модулю 9 и с −a + b − c + d по модулю 11. 9. Известно, что 7a ≡ 3(mod 13). Найти остаток от де- ления a на 13. (Сколько есть возможностей?) 10. Известно, что 8a ≡ 4(mod 14). Найти остаток от де- ления a на 14. (Сколько есть возможностей?) 11. Доказать, что 1 99 + 2 99 + 3 99 + 4 99 + 5 99 + 6 99 делится на 7. 12. Известно, что ac ≡ bc(mod mc). Доказать, что a ≡ ≡ b( mod m). 13. Найти остаток от деления (n 2 − 1) 101 (n + 1) 100 на n 72 Задачи 1996 { 1997 года * * * 14. Доказать, что 7777 2222 + 2222 7777 делится на 9. 15. Найти остаток от деления числа 1234567891011. . .99100 на 9 16. Доказать, что 1 100 + 2 100 + 3 100 + 4 100 + 5 100 + 6 100 делится на 7. 17. При каких n число 11 2n + 12 n делится на 133? 18. Известно, что сумма двух точных квадратов делится на 21. Доказать, что она делится на 441. Арифметика остатков 1. Составить таблицу сложения для остатков по моду- лю 11. (Такая таблица состоит из 11 строк и 11 столбцов, пронумерованных от 0 до 10. В m-ой клеточке n-ой строки стоит остаток от деления суммы двух чисел, дающих остат- ки m и n.) Верно ли такое утверждение: в каждой строке и каждом столбце встречаются все остатки ровно по одному разу? 2. Решить ту же задачу для умножения. (В этом случае в таблице будет нулевая строка и нулевой столбец.) 3. Решить те же задачи для сложения и умножения по модулю 7 и 10. 4. Какие числа и по скольку раз встречаются на диа- гонали (идущей из левого верхнего угла в правый нижний) таблиц сложения и умножения по модулям 5, 7, 11, 17 и 19? 5. В последовательности 1, 2, 5, 8, 11, . . . каждое следую- щее число на 1 больше суммы цифр квадрата предыдущего числа. Какое число стоит на 100-м месте? 6. Последовательность остатков от деления a, 2a, 3a, . . . на 12 (каждый член получается прибавлением a по моду- лю 12) периодична (при любом a от 0 до 11). Почему? Какие периоды тут встречаются (при различных a)? 7. Тот же вопрос при делении на 11. Какие периоды тут возможны? 8. Последовательность остатков от деления a, a 2 , a 3 , . . . на 11 (каждый член получается умножением на a по моду- лю 11) периодична при любом a от 0 до 10. Почему? Какие Задачи 1996 { 1997 года 73 периоды тут возможны? 9. В последовательности Фибоначчи (1, 1, 2, 3, 5, 8, 13, . . . ) каждый член равен сумме двух предыдущих. Заменив ка- ждое число остатком от деления его на 11, мы получим по- следовательность, в который каждый член равен сумме двух предыдущих по модулю 11. Доказать, что эта последователь- ность периодична, и найти период. 10. Будет ли периодична аналогичная последователь- ность, если 11 заменить на 13? Каков будет её период? * * * 11. Доказать, что для любого n последовательность остатков от деления чисел Фибоначчи на n периодична (и не имеет предпе- риода | повторяющийся кусок стоит с самого начала) 12. Доказать, что существует число Фибоначчи, оканчивающее- ся двумя нулями. Доказать, что существует число Фибоначчи, окан- чивающееся двумя девятками. 13. Запишем два произвольных числа от 0 до 10. Продолжим последовательность, беря каждый член равным сумме двух преды- дущих по модулю 11. Доказать, что члены этой последовательности будут повторяться через 10. 14. При каких α (не обязательно целых) последовательность дробных частей {α}, {2α}, {3α}, . . . будет периодична? Что в лоб, что по лбу 1. В таблице 57 × 91 расставлены числа. Может ли быть так, что сумма чисел в каждом столбце положительна, а в каждой строке | отрицательна? 2. В таблице m × n расставлены числа так, что сумма чисел в любой строке или столбце равна 57. Доказать, что m = n 3. Может ли в таблице 4 × 4 сумма чисел в любой строке быть чётным числом, а в любом столбце | нечётным? Тот же вопрос для таблицы 3 × 5. 4. Может ли работа фирмы за любые пять подряд идущих месяцев быть прибыльной, а по итогам года | убыточной? Может ли такое положение продолжаться в течение 6 лет? 74 Задачи 1996 { 1997 года 5. Кассир считает деньги так: сначала он считает все ку- пюры независимо от их достоинства, потом считает еще раз купюры достоинством больше 1 рубля, затем прибавляет чи- сло купюр достоинством больше 2 рублей и так далее. По- чему у него получается правильный ответ? 6. Все грани многогранника | треугольники, и их n штук. Сколько у него рёбер? 7. Для каждой вершины многогранника подсчитали ко- личество граней, сходящихся в этой вершине, и полученные числа сложили. Доказать, что полученная сумма чётна. 8. При входе в библиотеку стоят две доски. На одной из них приходящие читатели записывают, сколько человек уже было в библиотеке, когда они пришли. На другой уходящие читатели записывают, сколько осталось человек, когда они ушли. Утром и вечером в библиотеке никого не было. Дока- зать, что за день на обеих досках были написаны одни и те же числа. 9. Клетки шахматной доски пронумерованы от 1 до 64 (в первой строке от 1 до 8 слева направо, во второй | от 9 до 16 и так далее). Как ни поставь на доску 8 ладей, не бьющих друг друга, сумма номеров клеток, на которых они стоят, будет одна и та же. Почему? Инварианты 1. В турнире по олимпийской системе (проигравший вы- бывает) приняло участие 100 человек. Сколько было сыгра- но партий, прежде чем был определён победитель? 2. В ящик положили 3 меньших ящика. Затем в неко- торые из них также положили по 3 ещё меньших ящика, и так далее. В конце концов оказалось 17 заполненных ящиков (внутри которых есть другие ящики). Сколько в этот момент пустых ящиков? 3. По окружности расположено 20 плюсов и 20 минусов. Доказать, что пар соседних плюсов столько же, сколько пар соседних минусов. 4. Hа доске выписаны числа 1, 2, . . . , 20. Разрешается сте- реть любые два числа a и b и написать число (а) a + b − 1; Задачи 1996 { 1997 года 75 (б) a + b + ab. Какое число может остаться после 19 таких операций? 5. Любую вершину треугольника можно сдвигать по про- ходящей через нее прямой, параллельной противоположной стороне. Можно ли такими операциями сделать из равно- стороннего треугольника со стороной 1 прямоугольный тре- угольник с катетами, равными 1? 6. У числа 100! = 1·2·. . .·100 вычислили сумму цифр, у полученного числа также вычислили сумму цифр и так да- лее, пока не осталось однозначное число. Что это за число? 7. В ряд стоят 6 сосен и на каждой сидит чиж. Каждую минуту два чижа (на одной или разных соснах) перелетают на соседнюю сосну | один направо, другой налево. Могут ли чижи собраться на одной сосне? 8. (Продолжение) А если сосны стоят по кругу, и один из чижей летит по часовой стрелке, а другой | против? 9. (Продолжение) А если в ряд стоят 4 сосны, на которых сидят 1, 2, 3, 4 чижа, на какой сосне они смогут собраться? 10. В строчку написаны 10 чисел, причём сумма любых трёх соседних равна 15. Первое число равно 7. Чему может быть равно последнее число? 11. В мешке лежит 57 чёрных фасолин и 33 белых. Борис Михайлович вынимает из мешка наугад две фасолины. Если они оказываются одного цвета, то он заменяет их на белую фасолину, если разного | то на чёрную. Так он делает до тех пор, пока в мешке не останется только одна фасолина. Какого цвета она будет? * * * 12. K любым двум числам последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 разрешается одновременно прибавить или отнять по еди- нице. Можно ли несколькими такими операциями сделать все числа равными? 13. Стоят 57 стаканов вверх дном. За ход разрешается перевер- нуть любые (а) 5; (б) 6 стаканов. Можно ли за несколько ходов поставить стаканы вниз дном? 14. В стране Серобуромалин живет 13 серых, 15 бурых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного 76 Задачи 1996 { 1997 года цвета, они одновременно принимают окраску третьего цвета (на- пример, при встрече серого и бурого хамелеона оба становятся ма- линовыми). Может ли через некоторое время оказаться, что все хамелеоны имеют один цвет? 15. На каждой клетке доски 9×9 сидит жук. В какой-то момент каждый жук переполз на одну из соседних клеток. Доказать, что после этого хотя бы одна клетка стала пустой. 16. Hа шахматной доске 9 × 9 стояли 9 ладей, не бьющих друг друга. В какой-то момент каждая ладья сделала ход коня. Дока- зать, что теперь какие-то две ладьи бьют друг друга. Графы 1. В углах доски 3 × 3 стоят шахматные кони | два чёр- ных и два белых (рис. 17). (а) Можно ли поменять чёрных и белых коней местами (получив конфигурацию рис. 18)? (б) Можно ли поменять одного чёрного коня с одним белым (получив конфигурацию рис. 19)? (в) Если можно (в преды- дущих пунктах), какое минимальное число ходов для этого необходимо? Б Б Ч Ч Рис. 17 Ч Ч Б Б Рис. 18 Б Ч Ч Б Рис. 19 2. Выписать в ряд цифры от 1 до 9 (каждую по разу) так, чтобы любые две подряд идущие цифры давали бы двузнач- ное число, делящееся на 7 или на 13. 3. Каждый из учеников класса подсчитал, сколько у не- го в классе друзей (не считая себя). Полученные числа сло- жили. Получилось нечётное число. Доказать, что кто-то из школьников числит среди своих друзей человека, который не считает его своим другом. 4. Доказать, что в любой компании из шести человек най- дутся либо трое попарно знакомых, либо трое попарно незна- комых. (Считается, что если А знаком с Б, то Б знаком с А.) Задачи 1996 { 1997 года 77 5. Нарисовано несколько точек. Некоторые из них соеди- нены линиями. (Такую картинку называют графом, точки называют вершинами, линии | рёбрами.) Известно, что граф связен, то есть из любой вершины можно пройти в любую, идя по рёбрам. Доказать, что (число рёбер) > (число вершин)−1. 6. (Продолжение) Доказать, что если число рёбер не мень- ше числа вершин, то граф имеет цикл: можно найти замкну- тый путь, проходящий по рёбрам, и не проходящий два раза по одному ребру. 7. Можно ли нарисовать открытый конверт (рис. 20) и закрытый конверт (рис. 21), не отрывая карандаша от бумаги и не проходя по одному участку линии дважды? H H H H H H Рис. 20 H H H H Рис. 21 8. Каждый из 20 школьников решил 2 из 20 задач, при- чём каждую задачу решили ровно два школьника. Доказать, что можно организовать разбор задач так, чтобы каждый школьник рассказал одну из решённых им задач и чтобы все задачи были рассказаны. * * * 9. Доска имеет форму креста, который получается, если из ква- дратной доски 4×4 выкинуть угловые клетки. Можно ли её обойти ходом шахматного коня, побывав на каждом по одному разу и вер- нуться на исходное поле? 10. Имеется кусок проволоки длиной 120 см. Можно ли, не ло- мая его, сделать из него каркас куба со стороной 10 см? И если нельзя, то в скольких местах придётся эту проволоку сломать? 11. Имеется группа островов, соединённых мостами. Турист по- бывал на всех островах, пройдя по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ве- дёт с Троекратного, если турист (а) не с него начал и не на нём закончил? (б) с него начал, но не на нём закончил? (в) с него начал и на нём закончил? 12. Что можно нарисовать, не отрывая карандаша от бумаги и не проходя по одной линии дважды, а что нет? 78 Задачи 1996 { 1997 года 13. В связном графе число вершин ровно на единицу больше числа рёбер. Доказать, что в нём нет циклов. 14. На доске отметили 17 точек и соединили каждые 2 из них цветным отрезком: белым, синим или красным. Доказать, что най- дутся 3 точки в вершинах одноцветного треугольника. 15. Некоторые из 9 школьников подрались. Доказать, что най- дутся либо три такие школьника, что каждый подрался с каждым, либо четыре школьника, между которыми не было драк. 16. Имеется связный граф. Доказать, что можно удалить одну из его вершин (и все входящие в неё ребра), не нарушив его связно- сти. Экзаменационная контрольная работа Вариант 1 1. Нарисовать на плоскости точки с координатами ⟨x, y⟩, для которых (а) x 2 +2x+y 2 > 3 ; (б) (x+y)(x−1)(y+2) < 0. 2. Найти минимальное значение выражения |x + 1| + |x| + + |x − 1| + |x + 2|. При каких x оно достигается? 3. Найти все пары целых (не обязательно положитель- ных) чисел (x, y), для которых x + y + xy = 35. Сколько таких пар существует? (Порядок членов в паре существен.) 4. Доказать, что отрезки длиной 1 + √ 2 и 2 + 3 √ 2 несо- измеримы. 5. Найти наименьшее возможное значение x + 2y, если xy = 1 |