Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
17.20. Взяли три числа x, y, z и вычислили абсолютные величины попарных разностей x 1 = |x − y|, y 1 = |y − z|, z 1 = |z − x|. Тем же способом по числам x 1 , y 1 , построили числа x 2 , y 2 , и т. д. Оказалось, что при некотором получилось x n = x, y n = y, z n = z. Зная, что x = 1, найдите и z. 17.21. Набору чисел a 1 , a 2 , . . ., сопоставляется набор+ a 2 2 , b 2 = a 2 + a 3 2 , . . ., b n −1 = a n −1 + a n 2 , b n = a n + a 1 Затем с полученным набором чисел производится аналогичная операция и т. д. Докажите, что если при этом всегда будут получаться наборы целых чисел, то b 1 = b 2 = . . . = См. также задачу Решения. Достаточно рассмотреть рациональные числа вида p/q, где p<q. В таком случае цифры десятичной записи p/q=0,a 1 a 2 a 3 . . . Глава 17. Принцип Дирихле. Правило крайнего находятся следующим образом a k = h 10 k p q i − 10 h 10 k −1 p q i . Пусть Mq + r k , где r k — остаток отделения на q. Тогда 10M + h 10r k q i − 10M = h 10r k q i . Среди чисел r 1 , . . . , есть два одинаковых r i = r i +n . Но r k +1 — остаток отделения на Поэтому r i +1 = и т. д. Значит, последовательность цифр тоже периодически повторяется (после номера i). 17.2. Два из чисел a, a 2 , . . . , дают одинаковые остатки при делении на b. Пусть это будут числа и a l , где k > l. Тогда a l = a l (a k −l − 1) делится на b. Числа и b взаимно простые, поэтому a k −l − 1 делится на b. 17.3. Пусть 10 n − 1 = rq. Тогда 1 = rp · 10 −n + + rp · 10 −2n + rp · 10 −3n + . . . При этом rp < rq = 10 n −1 17.4. Пусть a 1 , . . . , a 100 — данные числа. Предположим, что ни одно из чисел S 1 = a 1 , S 2 = a 1 + a 2 , . . . , S 100 = a 1 + a 2 + . . . + не делится на 100. Тогда при делении на 100 они могут давать только разных остатков 1, 2, . . . , 99. Поэтому два числа и S m , n > m, дают одинаковые остатки при делении на 100. Значит, число S n − S m = a m +1 + . . . + делится на 100. 17.5. Сопоставим каждому выбранному числу его наибольший нечётный делитель. Количество нечётных чисел, не превосходящих, равно n/2 прич тном n и (n + 1)/2 при нечётном Поэтому у двух из выбранных чисел наибольший нечётный делитель один и тот же. Большее из этих чисел делится на меньшее. Рассмотрим остатки отделения чисел a 1 , . . . , на p. Числа, простые и все они строго больше p, поэтому ни одно из них не делится на p. Таким образом, мы получили p остатков, отличных от p. Следовательно, есть два числа и a j , дающие одинаковые остатки при делении на p. Поэтому их разность делится на p. Но a i − a j = (i − j)d, где d — разность прогрессии. Число |i − строго меньше p, поэтому на p должно делиться число d. 17.7. Рассмотрим чисел ay + x, где x, y = 0, 1, 2, . . . , e − 1. Так как e 2 > n, среди этих чисел найдутся числа ay 1 + и ay 2 + дающие одинаковые остатки при делении на n. Следовательно y 2 ) ≡ x 2 − x 1 (mod n). Числа y 2 | и |x 1 − x 2 | не превосходят, поэтому они могут делиться на n лишь в том случае, когда они равны 0. По условию число a взаимно просто с n. Поэтому тогда и только тогда, когда y 1 = y 2 . Следовательно y 2 | 6= 0 и |x 1 − x 2 | 6= 0. Поэтому числа x = |x 1 − x 2 | и y = |y 1 − обладают требуемым свойством Решения задач. Сопоставим каждому изданных человек число, равное количеству его знакомых среди этих n человек. Это число может принимать одно из n значений 0, 1, . . . , n − 1. Но если у кого-то вообще нет знакомых, то никто не может быть знаком со всеми. Наоборот, если кто-то знаком со всеми, тонет человека, который ни с кем незнаком. Таким образом, количество знакомых принимает одно из не более чем n − 1 значений. Поэтому для каких-то двух человек эти значения одинаковы. Сопоставим члену данной последовательности два числа и y k , где x k — наибольшая длина возрастающей последовательности, начинающейся с a k , y k — наибольшая длина убывающей последовательности, начинающейся с a k . Предположим, что и y k 6 n для всех k. Тогда количество всех различных парне превосходит mn. Поэтому x k = и y k = для некоторых номеров k 6= l. Но этого не может быть. Действительно, пусть для определённости k < l. Тогда если a k < a l , то x k > x l , а если то y k > y l 17.10. Ответ Числа [x] и [y] различны тогда и только тогда, когда числа и [−y] различны. Поэтому достаточно рассмотреть случай, когда > 0. Если a < N − 1 N , то среди чисел [a], [2a], . . . , [Na] есть совпадающие, поскольку эти N чисел содержатся среди N − 1 чисел, 1, . . . , N − 2. Поэтому a > N − 1 N . Те же самые рассуждения для числа 1/a показывают, что 1 M , те Покажем, что если 1 N 6 a 6 M M − 1 , то все числа [a], [2a], . . . . . . , [Na] различны. Действительно, если a > 1, то вообще все числа, [2a], [3a], . . . различны, а если a < 1, то 1 − 1/N 6 a < 1, 2 − 2/N 6 a < 2, . . ., N− 16 a < N, поэтому [ka] = k − 1 для k = 1, 2, . . . . . . , N. Для чисел, [2/a], . . . , M/a] рассуждения аналогичны. Фиксируем натуральное число n. Дробные части чисел, 2 a , . . . , n a лежат в полуоткрытом интервале [0, 1), поэтому по крайней мере две из них попадают в один и тот же полуоткрытый интервал [k/n, (k + 1)/n), 0 6 k 6 n − 1. Это означает, что [p 1 a ] − (p 2 a − [p 2 a ])| < для некоторых целых чисел и p 2 , удовлетворяющих неравенствам. Положим y = p 1 − и x = [p 2 a ] − [p 1 a ]. Тогда <1/n. Числа x и y здесь можно считать взаимно простыми Глава 17. Принцип Дирихле. Правило крайнего поскольку после деления их на НОД(x, y) требуемое неравенство сохранится. Ясно также, что 0 < y 6 n, поэтому |x/y − a | < 1 ny 6 Выберем теперь натуральное число так, что |x/y − a | > Описанная выше конструкция даёт пару целых чисел x 1 , y 1 , для которых |x 1 /y 1 − a | < 1 n 1 y 1 < |x/y − a |. Так можно получить бесконечно многоразличных пар чисел x, y. 17.12. Предположим сначала, что число C целое. Рассмотрим число 1 и числа k a − [k a ] для k = 0, 1, . . . , C − 1. Эти C + 1 чисел лежат на отрезке [0, 1], поэтому расстояние между какими-то двумя из них не превосходит 1/C. Если это окажутся числа k 1 a − и k 2 a − [k 2 a ], где k 1 < k 2 , то положим x = k 2 − и y = [k 2 a ] − Тогда 0 < x < C и y| = |k 1 a − [k 1 a ] − (k 2 a − [k 2 a ])| 6 Если же это окажутся числа k a − [k a ] и 1, то положим x = и y = [k a ] + 1. Тогда y| = |k a − [k a ] − 1| 6 Из этого, в частности, следует, что x 6= Пусть теперь число C нецелое. Рассмотрим целое число C ′ = = [C] + 1. Как только что было доказано, можно выбрать натуральное число x и целое число y так, что x < и |x a − y| 6 Число C нецелое, поэтому любое целое число, не превосходящее, не превосходит и C. Следовательно, x < C. 17.13. а) Пусть ∆ = b − a. Для каждого целого числа можно выбрать целое число так, что 0 6 m 1 a − n 1 6 1. Разделим отрезок [0, 1] на равные отрезки, длина каждого из которых меньше ∆. Пусть количество этих отрезков равно k. Тогда среди чисел m 1 a − n 1 , . . . , m k +1 a − есть два числа, попадающих в один и тот же отрезок. Вычтем из большего числа меньшее n p − (m q a − n q ) = t. Ясно, что 0 6 t < ∆. Более того, t 6= поскольку иначе a = n p − n q m p − m q — рациональное число. Рассмотрим числа вида Nt, где N — целое число. Каждое из этих чисел имеет вид m a − n. А из того, что 0 < t < ∆, следует, что хотя бы одно из этих чисел расположено строго между a и б) Нужно доказать, что число t можно выбрать как вида N, таки вида −M a + N, где M и N — натуральные числа. Пусть t = M a − N. Между 0 и t есть бесконечно много чисел вида Решения задачи целые. Предположим, что у всех этих чисел > 0. Тогда для одного из них m > M, а в таком случае число M a − N − (m a − n) искомое. Если же t = −M a + N, то рассуждения аналогичны. Среди написанных чисел можно выбрать наименьшее. Действительно, сначала возьмём произвольное написанное число. Если есть число, которое меньше выбранного числа, тона следующем шаге выберем его и т. д. Этот процесс конечен, потому что всего мы можем выбрать не более n различных чисел. Пусть m — наименьшее из написанных чисел, a, b, c, d — соседние с ним числа. Тогда a, b, c, d > m и a + b + c + d = 4m. Поэтому b = c = d = Из любого поля шахматной доски можно попасть в любое другое поле, перемещаясь сначала по горизонтали, а затем поверти- кали. Поэтому на всех полях написано одно и тоже число m. 17.15. Рассмотрим квадрат, состоящий из 16 клеток, ивы- режем из него 4 угловые клетки. Среди оставшихся 12 клеток выберем ту, в которой стоит наименьшее число (если таких клеток несколько, то выбираем любую из них. Выбранная клетка обладает требуемым свойством. Предположим, что наибольшее число a стоит нес края. Тогда у него в таблице есть все четыре соседних числа a 1 , a 2 , a 3 , и при этом a = (a 1 + a 2 + a 3 + a 4 )/4. Но a > a 1 , a > a 2 , a > a 3 , a > Поэтому a > (a 1 + a 2 + a 3 + a 4 )/4. Приходим к противоречию. Сначала докажем, что все гири одновременно имеют либо чётный, либо нечётный вес. Пусть 12 гирь разложены на две чашки весов по 6 гирь так, что наступило равновесие. Предположим, что отложена гиря весом a га одна из гирь, лежащих на чашках, весит b г, причём числа a и b разной чётности. Заменим гирю a гирей b и снова разложим гири так, чтобы наступило равновесие. Вес гирь на каждой чашке весов изменился на 2 |a − поэтому число |a − b| чётно. Предположим, что не все гири одинаковые. Вычтем из каждой гири вес наименьшей гири. В результате получим набор гирь, которые снова удовлетворяют условию задачи (по крайней мере одна из полученных гирь имеет нулевой вес. Все новые гири имеют чётный вес, строго меньший веса первоначальных гирь. Поделив вес каждой гири пополам (в том числе и гири с нулевым весом), мы снова получим набор гирь, удовлетворяющий условию задачи. Если при этом мы не получим гири нечётного веса, то снова поделим веса всех гирь пополам и т. д. В конце концов получим Глава 17. Принцип Дирихле. Правило крайнего систему гирь, которая удовлетворяет условию задачи ив которой есть как гири чётного (нулевого) веса, таки гири нечётного веса. Но мы уже доказали, что такого быть не может. а) Рассмотрим наибольшие нечётные делители выбранных чисел. У чисел от 1 доесть ровно 100 различных наибольших нечётных делителей (числа 1, 3, . . . , 199). Итак, два из выбранных чисел имеют одинаковые наибольшие нечётные делители. Это означает, что два выбранных числа отличаются только тем, что множитель 2 входит в них в разных степенях. Большее из них делится на меньшее. б) Предположим, что из чисел 1, 2, 3, . . . , 199, 200 мы выбрали чисел так, что ни одно из них не делится на другое. Достаточно доказать, что среди выбранных чисел нет чисел, меньших Рассмотрим наибольшие нечётные делители всех выбранных чисел. Если наибольшие нечётные делители двух чисел совпадают, то одно из них делится на другое. Поэтому наибольшие нечёт- ные делители выбранных чисел — это в точности все числа 1, 3, 5, . . . , 199. В частности, среди выбранных чисел есть числа с наибольшими нечётными делителями 1, 3, 9, 27 и 81. Ни одно из выбранных чисел не делится на другое, поэтому выбранное число с наибольшим нечётным делителем 27 делится нас наибольшим нечётным делителем 9 делится нас наибольшим нечётным делителем 3 делится нас наибольшим нечётным делителем делится на 2 4 . Следовательно, среди выбранных чисел нет чисел, 2, 3, 4, 6, 8, 9 и 12. Далее, рассматривая выбранные числа с наибольшими нечётными делителями 5, 15 и 45, убеждаемся, что среди выбранных чисел нет чисел 5, 10 и 15; рассматривая выбранные числа с наибольшими нечётными делителями 7, 21 и 63, убеждаемся, что нет чисел 7 и 14; рассматривая выбранные числа с наибольшими нечётными делителями 11 и убеждаемся, что нет числа 11; рассматривая выбранные числа с наибольшими нечётными делителями 13 и 39, убеждаемся, что нет числа 13. 17.19. Пусть некая бактерия, из которой в конце получилось бактерий, разделилась на две бактерии. Из этих двух «сестёр» в конце получилось и бактерий, причём m ′ + m ′′ = Значит, одно из чисел и не меньше m/2. Будем каждый раз выбирать ту из бактерий, у которой не меньше потомков, чему её сестры. В результате получим последовательность a 1 > a 2 > . . . > a k = 1, причём a i > a i −1 /2 (здесь a i — количество потомков выбранной бактерии. Выберем номер i так, что > a i +1 . Тогда a i +1 > a i /2 > a, а значит, a 6 a i +1 6 2a − 1. Решения задач. Ответ. Числа x n , y n , z n неотрицательны, поэтому числа x, y, z тоже неотрицательны. Если бы все числа x, y, z были положительны, то наибольшее из чисел x 1 , y 1 , было быстрого меньше наибольшего из чисел x, y, z, а тогда и наибольшее из чисел x n , y n , было быстрого меньше наибольшего из чисел x, y, z. Поэтому среди чисел x, y, z есть 0. Аналогично доказывается, что среди чисел x 1 , y 1 , есть 0 (при n = 1 доказывать ничего ненужно, потому что тогда x 1 = x, y 1 = y, z 1 = Это означает, что два из чисел x, y, z равны. В итоге получаем, что неупорядоченный набор чисел x, y, z может быть равен либо, 0, 1, либо 0, 1, 1. Легко проверить, что второй набор не обладает требуемым свойством. Предположим, что не все числа x 1 , x 2 , . . . , x n равны. Пусть наибольшее из этих чисел равно N, причём оно встречается среди них ровно k раз. Тогда в новой последовательности нет чисел, превосходящих N, причём число N встречается не более 1 раз. Поэтому после нескольких операций наибольшее значение уменьшится. Ясно также, что наибольшее значение не может стать меньше наименьшего значения чисел исходной последовательности. Поэтому после конечного числа операций все числа становятся равными. Пусть набор равных чисел получается из набора x 1 , x 2 , . . . , Тогда x 1 = x 3 , x 2 = x 4 , . . . , x n −1 = x 1 , x n = x 2 . Если n нечётно, то все числа x 1 , . . . , равны. Если n чётно, то x 1 = x 3 = . . . = x n −1 = и x 2 = x 4 = . . . = x n = b. Остаётся проверить, что если a 6= b, то такой набор чисел x 1 , x 2 , . . . , нельзя получить ни из какого набора, y 2 , . . . , y n . Действительно, пусть 2 = y 3 + y 4 2 =. . и 2 = y 4 + y 5 2 = . . . = y n + y 1 2 = b. Тогда y 1 + y 2 + . . . + y n = и y 2 + y 3 + . . . + y n + y 1 = 2nb. Поэтому a = b. ГЛАВА ИНВАРИАНТЫ И ПОЛУИНВАРИАНТЫ Часто бывает так, что каждому состоянию системы можно сопоставить некоторую величину, не меняющуюся при любом допустимом переходе системы из одного состояния в другое. Такую величину называют инвариантом. Ясно, что инвариант не может измениться не только при одном переходе, но и при нескольких переходах, поэтому значение инварианта в начальном ив конечном состоянии системы одно и то же. На практике применение инвариантов к решению задач сводится к тому, что некоторая величина вычисляется двумя способами сначала она просто вычисляется в начальном и конечном состоянии, а затем прослеживается её изменение при последовательных мелких переходах. Помимо инвариантов бывают полезны и полуинварианты, т. е. величины, которые хотя и изменяются при переходах системы из одного состояния в другое, но предсказуемым образом: например, не увеличиваются (или не уменьшаются. Остатки отделения. На 44 деревьях, посаженных по окружности, сидели чижа (на каждом дереве по одному. Время от времени какие-то два чижа одновременно перелетают на соседние деревья в противоположных направлениях (один — почасовой стрелке, другой — против. Смогут ли чижи когда-ни- будь собраться на одном дереве. Стройкой чисел (a, b, c) разрешается проделать следующую операцию одно число увеличить на 2, а два других одновременно с этим уменьшить на 1. Можно лис помощью таких операций из тройки (13, 15, 17) получить тройку с двумя нулями Условия задач. В последовательности 1, 0, 1, 0, 1, 0, . . . каждый член начиная с седьмого равен последней цифре суммы шести предыдущих. Докажите, что в этой последовательности никогда не встретятся подряд шесть чисел 0, 1, 0, 1, 0, 1. |