WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |   ...   | 65 |

Правило крайнего Самая популярная формулировка принципа Дирихле такова: Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца. На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь зайцы и клетки и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод дает неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путем явного построения или указания требуемого объекта, может привести к гораздо б трудностям.

ольшим 17.1. Остатки от деления 17.1. Докажите, что десятичная запись рационального числа является периодической дробью.

Замечание. По поводу обратного утверждения см. задачу 9.3.

17.2. Докажите, что если натуральные числа a и b взаимно простые, то an - 1 делится на b для некоторого натурального n.

198 Глава 17. Принцип Дирихле. Правило крайнего 17.3. Пусть p < q натуральные числа, причём q не делится на и на 5. Согласно задаче 17.2 можно выбрать n так, что 10n - 1 делится на q. Докажите, что p/q чисто периодическая дробь, длина периода которой делится на n.

* * * 17.4. Докажите, что из любых ста целых чисел можно выбрать одно или несколько чисел так, чтобы их сумма оканчивалась двумя нулями.

17.5. Из чисел 1, 2,..., n выбрано более (n + 1)/2 различных чисел.

Докажите, что одно из выбранных чисел делится на другое.

17.6. Простые числа a1, a2,..., ap образуют возрастающую арифметическую прогрессию и a1 > p. Докажите, что если p простое число, то разность прогрессии делится на p.

17.7. Пусть n > 1 натуральное число, e наименьшее целое чис ло, превосходящее n. Докажите, что для любого натурального числа a, взаимно простого с n, можно выбрать натуральные числа x и y, не превосходящие e - 1, так, что ay ±x (mod n).

См. также задачу 15.10.

17.2. Разные задачи 17.8. Докажите, что среди любых n 2 человек найдутся два человека, имеющих одинаковое число знакомых среди этих n человек.

17.9. Докажите, что любая последовательность из mn + 1 попарно различных чисел содержит либо возрастающую последовательность из m + 1 чисел, либо убывающую последовательность из n + 1 чисел.

17.10. Числа [a], [2a],..., [Na] различны между собой, и числа, a M,..., тоже различны между собой. Найдите все такие a.

a a 17.3. Приближения иррациональных чисел рациональными 17.11. Пусть иррациональное число. Докажите, что существует бесконечно много пар взаимно простых чисел x, y, для которых |x/y - | < 1/y2.

Глава 17. Принцип Дирихле. Правило крайнего 17.12. Пусть положительное число. Докажите, что для любого числа C > 1 можно выбрать натуральное число x и целое число y так, что x < C и |x - y|.

C 17.13. а) Пусть иррациональное число. Докажите, что для любых чисел a < b можно выбрать целые числа m и n, для которых a < m - n < b.

б) Докажите, что числа m и n можно выбрать натуральными.

17.4. Правило крайнего Правило крайнего заключается в том, чтобы рассмотреть тот элемент, для которого некая величина имеет наибольшее или (наименьшее) значение. Правило крайнего помогает при решении многих задач.

17.14. На полях бесконечной шахматной доски написаны натуральные числа так, что каждое число равно среднему арифметическому четырёх соседних чисел верхнего, нижнего, левого и правого. Докажите, что все числа на доске равны между собой.

17.15. В каждой клетке бесконечного листа клетчатой бумаги написано какое-то действительное число. Докажите, что найдётся клетка, в которой написано число, не превосходящее чисел, написанных по крайней мере в четырёх из восьми граничащих с ней клеток.

17.16. В каждой клетке прямоугольного листа клетчатой бумаги написано число, причём в каждой клетке, не стоящей с края, написано среднее арифметическое чисел, стоящих в соседних клетках. Все написанные числа различны. Докажите, что наибольшее число стоит с края (т.е. по крайней мере одна из соседних клеток отсутствует).

17.17. Есть 13 гирь, каждая из которых весит целое число граммов.

Известно, что любые 12 из них можно так разложить на 2 чашки весов, по 6 гирь на каждой, что наступит равновесие. Докажите, что все гири одного веса.

17.18. а) Из чисел 1, 2, 3, 4, 5, 6, 7,..., 199, 200 произвольно выбрали 101 число. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.

б) Из двухсот чисел: 1, 2, 3,..., 199, 200 выбрали одно число, меньшее 16, и ещё 99 чисел. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.

17.19. Из одной бактерии получилось n бактерий следующим образом. Сначала бактерия разделилась на две, затем одна из двух получив200 Глава 17. Принцип Дирихле. Правило крайнего шихся бактерий разделилась на две, затем одна из трёх получившихся бактерий разделилась на две и т.д. Докажите, что для любого натурального числа a n/2 в некоторый момент существовала бактерия, число потомков которой среди получившихся в конце n бактерий не меньше a и не больше 2a - 1.

17.20. Взяли три числа x, y, z и вычислили абсолютные величины попарных разностей x1 = |x-y|, y1 = |y-z|, z1 = |z-x|. Тем же способом по числам x1, y1, z1 построили числа x2, y2, z2 и т.д. Оказалось, что при некотором n получилось xn = x, yn = y, zn = z. Зная, что x = 1, найдите y и z.

17.21. Набору чисел a1, a2,..., an сопоставляется набор b1 = a1 + a2 a2 + a3 an-1 + an an + a=, b2 =,..., bn-1 =, bn =. Затем с 2 2 2 полученным набором чисел производится аналогичная операция и т.д.

Докажите, что если при этом всегда будут получаться наборы целых чисел, то b1 = b2 =... = bn.

См. также задачу 19.6.

Решения 17.1. Достаточно рассмотреть рациональные числа вида p/q, где 1 p < q. В таком случае цифры десятичной записи p/q = 0, a1a2a3...

10kp 10k-1p находятся следующим образом: ak = - 10. Пусть 10k-1p = q q = Mq + где rk остаток от деления 10k-1p на q. Тогда ak = 10M + rk, 10rk 10rk + - 10M =. Среди чисел r1,..., rq+1 есть два одинаковых:

q q ri = ri+n. Но rk+1 остаток от деления 10rk на q. Поэтому ri+1 = ri+n+и т.д. Значит, последовательность цифр ak тоже периодически повторяется (после номера i).

17.2. Два из чисел a, a2,..., ab+1 дают одинаковые остатки при делении на b. Пусть это будут числа ak и al, где k > l. Тогда ak - al = al(ak-l - 1) делится на b. Числа al и b взаимно простые, поэтому ak-l - 1 делится на b.

p rp rp 17.3. Пусть 10n - 1 = rq. Тогда = = = rp · 10-n + rp · 10-2n + q rq 10n - + rp · 10-3n +.... При этом rp < rq = 10n-1.

17.4. Пусть a1,..., a100 данные числа. Предположим, что ни одно из чисел S1 = a1, S2 = a1 + a2,..., S100 = a1 + a2 +... + a100 не делится на 100.

Тогда при делении на 100 они могут давать только 99 разных остатков: 1, 2,..., 99. Поэтому два числа Sn и Sm, n > m, дают одинаковые остатки при делении на 100. Значит, число Sn - Sm = am+1 +... + an делится на 100.

Глава 17. Принцип Дирихле. Правило крайнего 17.5. Сопоставим каждому выбранному числу его наибольший нечётный делитель. Количество нечётных чисел, не превосходящих n, равно n/2 при чётном n и (n + 1)/2 при нечётном n. Поэтому у двух из выбранных чисел наибольший нечётный делитель один и тот же. Большее из этих чисел делится на меньшее.

17.6. Рассмотрим остатки от деления чисел a1,..., ap на p. Числа a1,..., ap простые и все они строго больше p, поэтому ни одно из них не делится на p.

Таким образом, мы получили p остатков, отличных от p. Следовательно, есть два числа ai и aj, дающие одинаковые остатки при делении на p. Поэтому их разность делится на p. Но ai - aj = (i - j)d, где d разность прогрессии.

Число |i - j| строго меньше p, поэтому на p должно делиться число d.

17.7. Рассмотрим e2 чисел ay+x, где x, y = 0, 1, 2,..., e-1. Так как e2 > n, среди этих чисел найдутся числа ay1 + x1 и ay2 + x2, дающие одинаковые остатки при делении на n. Следовательно, a(y1 -y2) x2 -x1 (mod n). Числа |y1 - y2| и |x1 - x2| не превосходят e - 1, поэтому они могут делиться на n лишь в том случае, когда они равны 0. По условию число a взаимно просто с n. Поэтому x1 = x2 тогда и только тогда, когда y1 = y2. Следовательно, |y1 - y2| = 0 и |x1 - x2| = 0. Поэтому числа x = |x1 - x2| и y = |y1 - y2| обладают требуемым свойством.

17.8. Сопоставим каждому из данных n человек число, равное количеству его знакомых среди этих n человек. Это число может принимать одно из n значений: 0, 1,..., n - 1. Но если у кого-то вообще нет знакомых, то никто не может быть знаком со всеми. Наоборот, если кто-то знаком со всеми, то нет человека, который ни с кем не знаком. Таким образом, количество знакомых принимает одно из не более чем n - 1 значений. Поэтому для каких-то двух человек эти значения одинаковы.

17.9. Сопоставим члену ak данной последовательности два числа xk и yk, где xk наибольшая длина возрастающей последовательности, начинающейся с ak, yk наибольшая длина убывающей последовательности, начинающейся с ak. Предположим, что xk m и yk n для всех k. Тогда количество всех различных пар (xk, yk) не превосходит mn. Поэтому xk = xl и yk = yl для некоторых номеров k = l. Но этого не может быть. Действительно, пусть для определённости k < l. Тогда если ak < al, то xk > xl, а если ak > al, то yk > yl.

N - 1 M 17.10. О т в е т: |a|.

N M - Числа [x] и [y] различны тогда и только тогда, когда числа [-x] и [-y] разN - личны. Поэтому достаточно рассмотреть случай, когда a > 0. Если a <, N то среди чисел [a], [2a],..., [Na] есть совпадающие, поскольку эти N чисел N - содержатся среди N -1 чисел 0, 1,..., N -2. Поэтому a. Те же самые N 1 M - 1 M рассуждения для числа 1/a показывают, что, т.е. a.

a M M - 202 Глава 17. Принцип Дирихле. Правило крайнего N - 1 M Покажем, что если a, то все числа [a], [2a],..., [Na] N M - различны. Действительно, если a 1, то вообще все числа [a], [2a], [3a], 1... различны, а если a < 1, то 1- a < 1, 2- a < 2,..., N -1 a < N, N N 1 2 M поэтому [ka] = k - 1 для k = 1, 2,..., N. Для чисел,,..., расa a a суждения аналогичны.

17.11. Фиксируем натуральное число n. Дробные части чисел 0,, 2,..., n лежат в полуоткрытом интервале [0, 1), поэтому по крайней мере две из них попадают в один и тот же полуоткрытый интервал [k/n, (k + 1)/n), 0 k n - 1. Это означает, что |p1 - [p1] - (p2 - [p2])| < 1/n для некоторых целых чисел p1 и p2, удовлетворяющих неравенствам 0 p2 < p1 n. Положим y = p1 - p2 и x = [p2] - [p1]. Тогда |y - x| < 1/n.

Числа x и y здесь можно считать взаимно простыми, поскольку после деления их на НОД(x, y) требуемое неравенство сохранится. Ясно также, что 1 0 < y n, поэтому |x/y - | <.

ny yВыберем теперь натуральное число n1 так, что |x/y - | > 1/n1.

Описанная выше конструкция даёт пару целых чисел x1, y1, для которых |x1/y1 - | < < |x/y - |. Так можно получить бесконечно много разn1yличных пар чисел x, y.

17.12. Предположим сначала, что число C целое. Рассмотрим число 1 и числа k - [k] для k = 0, 1,..., C - 1. Эти C + 1 чисел лежат на отрезке [0, 1], поэтому расстояние между какими-то двумя из них не превосходит 1/C.

Если это окажутся числа k1 - [k1] и k2 - [k2], где k1 < k2, то положим x = k2 - k1 и y = [k2] - [k1]. Тогда 0 < x < C и |x - y| = |k1 - [k1] - (k2 - [k2])|.

C Если же это окажутся числа k - [k] и 1, то положим x = k и y = [k] + 1.

Тогда |x - y| = |k - [k] - 1|.

C Из этого, в частности, следует, что x = 0.

Пусть теперь число C не целое. Рассмотрим целое число C = [C] + 1.

Как только что было доказано, можно выбрать натуральное число x и целое 1 число y так, что x < C и |x - y| <. Число C не целое, поэтому C C любое целое число, не превосходящее C, не превосходит и C. Следовательно, x < C.

17.13. а) Пусть = b - a. Для каждого целого числа m1 можно выбрать целое число n1 так, что 0 m1 - n1 1. Разделим отрезок [0, 1] на равные отрезки, длина каждого из которых меньше. Пусть количество этих отрезков равно k. Тогда среди чисел m1 - n1,..., mk+1 - nk+1 есть два числа, Глава 17. Принцип Дирихле. Правило крайнего попадающих в один и тот же отрезок. Вычтем из большего числа меньшее:

mp - np - (mq - nq) = t. Ясно, что 0 t <. Более того, t = 0, поскольку np - nq иначе = рациональное число.

mp - mq Рассмотрим числа вида Nt, где N целое число. Каждое из этих чисел имеет вид m - n. А из того, что 0 < t <, следует, что хотя бы одно из этих чисел расположено строго между a и b.

б) Нужно доказать, что число t можно выбрать как вида M - N, так и вида -M+N, где M и N натуральные числа. Пусть t = M-N. Между и t есть бесконечно много чисел вида m - n, m и n целые. Предположим, что у всех этих чисел m > 0. Тогда для одного из них m > M, а в таком случае число t = M - N - (m - n) искомое. Если же t = -M + N, то рассуждения аналогичны.

17.14. Среди написанных чисел можно выбрать наименьшее. Действительно, сначала возьмём произвольное написанное число n. Если есть число, которое меньше выбранного числа, то на следующем шаге выберем его и т.д.

Этот процесс конечен, потому что всего мы можем выбрать не более n различных чисел.

Пусть m наименьшее из написанных чисел, a, b, c, d соседние с ним числа. Тогда a, b, c, d m и a + b + c + d = 4m. Поэтому a = b = c = d = m.

Из любого поля шахматной доски можно попасть в любое другое поле, перемещаясь сначала по горизонтали, а затем по вертикали. Поэтому на всех полях написано одно и то же число m.

17.15. Рассмотрим квадрат, состоящий из 16 клеток, и вырежем из него 4 угловые клетки. Среди оставшихся 12 клеток выберем ту, в которой стоит наименьшее число (если таких клеток несколько, то выбираем любую из них).

Выбранная клетка обладает требуемым свойством.

17.16. Предположим, что наибольшее число a стоит не с края. Тогда у него в таблице есть все четыре соседних числа a1, a2, a3, a4 и при этом a = = (a1 + a2 + a3 + a4)/4. Но a > a1, a > a2, a > a3, a > a4. Поэтому a > (a1 + + a2 + a3 + a4)/4. Приходим к противоречию.

17.17. Сначала докажем, что все гири одновременно имеют либо чётный, либо нечётный вес. Пусть 12 гирь разложены на две чашки весов по 6 гирь так, что наступило равновесие. Предположим, что отложена гиря весом a г, а одна из гирь, лежащих на чашках, весит b г, причём числа a и b разной чётности. Заменим гирю a гирей b и снова разложим гири так, чтобы наступило равновесие. Вес гирь на каждой чашке весов изменился на |a - b|, поэтому число |a - b| чётно.

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.