Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
21.16. Ответ цифра 7. Однозначных чисел ровно 9, двузначных, трёхзначных 999 − 99 − 9 = 900, четырёх- значных 9000 и т. д. Однозначные числа займут в выписанном ряду первые 9 мест, двузначные 90 · 2 = 180 мест, трёхзначные 900 · 3 = 2700 мест, четырёхзначные 9000 · 4 = 36 000 мест, пятизначные мест. Поэтому интересующая нас цифра принадлежит пятизначному числу. Цифры, принадлежащие не более чем четырёхзначным числам, имеют номера от 1 до 9 + 180 + 2700 + 36 000 = 38 889. Разность нужно разделить нас остатком 899 = 5 · 33 579 + 4. Интересующая нас цифра принадлежит 580-му пятизначному числу, те. числу 43 579 (первое пятизначное число — это число 10 000). В этом числе интересующая нас цифра стоит нам месте. Длина периода десятичной записи дроби n/p равна наименьшему натуральному числу d, для которого n(10 d − 1) делится на p. Числа n и p взаимно простые, поэтому n(10 d −1) делится на тогда и только тогда, когда 10 d − 1 делится на p. 21.18. Длина периода числа p равна наименьшему натуральному числу d, для которого 10 d − 1 делится на p. Согласно малой теореме Ферма (задача 31.1) 10 p −1 − 1 делится на p. Пусть 1 = ad + r, где 0 6 r < d. Требуется доказать, что r = 0. Предположим, что r > 0. Тогда 10 p −1 = (10 d ) a 10 r ≡ 10 r (mod p), поэтому 1 (mod p). Это противоречит минимальности числа d. 21.19. Будем делить 1 на p столбиком. В результате периодически будут повторяться некоторые остатки. Например, при делении 1 на 7 периодически повторяются остатки 1, 3, 2, 6, 4, В случае, когда длина периода равна p − 1, в этой последовательности встречаются всевозможные остатки 1, 2, . . . , p − 1. Решения задач 265 Вернёмся к примеру дробей со знаменателем 7. Деление в столбик показывает, что 1/7=0,(142857). Вслед за остатком 1 встречается остаток 3. Это означает, что десятичная запись дроби 3/7 получается из десятичной записи дроби 1/7 вычёркиванием первой цифры после нуля. Дробь 2/7 получается вычёркиванием первых двух цифр, дробь 6/7 — первых трёх и т. д. Число p − 1 чётно; запишем его в виде p − 1 = 2k. Период дроби 1/p, записанный как натуральное число, имеет вид Требуется доказать, что a + b = 10 k − Число 10 2k −1=(10 k −1)(10 k + 1) делится на p. При этом не делится на p, поскольку иначе длина периода числа p была бы меньше 2k. Следовательно, 10 k + 1 делится на Ясно, что 10 2k − 1 = (a · 10 k + b) · p. Поэтому число a · 10 k + b = = (10 k − делится на 10 k − 1. Далее+ b ≡ a · 10 k + b (mod 10 k − поэтому a + b делится на 10 k − 1. Кроме того, a + b < 2(10 k − поэтому a + b = 10 k − 1. 21.21. Пусть длина периода простого числа p равна d. Это означает, что d — наименьшее натуральное число, для которого 1 делится на p. Ясно, что 10 d − 1 = 9R d , где R d — репью- нит, содержащий d единиц. Если p — простое число, отличное от 3, то делится на p тогда и только тогда, когда делится на p. 21.22. Если p — простое число, отличное от 2 и 5, то число 1 делится на p задача 31.1). Это число имеет вид 99 . . . 9 | {z Поэтому если p 6= 3, то число 11 . . . 1 | {z тоже делится на p. 21.23. Выберем k так, что d k 6 n < d k +1 . Положим a k = Тогда 1 6 a k 6 d − 1 и n = a k d k + n ′ , где 0 6 n ′ < d k . Если n ′ 6= то выберем l < k так, что d l 6 n ′ < d l +1 , и положим a l = и a l +1 = . . . = a k −1 = 0 (если l < k − 1). Тогда n = a k d k + a l d l + n ′′ . Для n ′′ поступаем аналогичным образом и т. д. Число определяется единственным образом. Действительно, если n = a 0 + a 1 d + a 2 d 2 + . . . + a k d k , то d k 6 n 6 (d − 1) + d(d − 1) + . . . . . . + d k (d − 1) = d k +1 − 1 < d k +1 . Все остальные числа тоже определяются однозначно. Пусть n = b k 2 k + b k −1 2 k −1 + . . . + b 1 · 2 + b 0 . Тогда a 0 = и n 1 = b k 2 k −1 + b k −1 2 k −2 + . . . + b 1 . Поэтому a 1 = и n 2 = b k 2 k −2 + + b k −1 2 k −3 + . . . + и т. д Глава 21. Системы счисления. Каждое число от 0 до 2 n +1 −1 можно единственным образом представить в виде суммы различных чисел 0, 1, 2, 2 2 , . . . , Поэтому слагаемое x m , где 0 6 m 6 2 n +1 − 1, при раскрытии скобок в указанном произведении встречается ровно один раз. Ясно, что (1 + x) 2 ≡ 1 + x 2 (mod 2). Поэтому индукция по m показывает, что (1 + x) 2 m ≡ 1 + x 2 m (mod 2). Пусть n = 2 m 1 + + 2 m 2 + . . . + 2 m d , где 0 6 m 1 < m 2 < . . . < m d . Тогда+ x) n = (1 + x) 2 m1 (1 + x) 2 m2 . . . (1 + x) 2 md ≡ ≡ (1 + x 2 m1 )(1 + x 2 m2 ) . . . (1 + x 2 md ) (mod Все члены, которые получаются при раскрытии скобок в последнем выражении, различны. Их количество равно 2 d , причём коэффициент при каждом члене равен 1. 21.27. а) Пусть d k — нечётное число с наибольшим номером Тогда одно из чисел a k , b k , равно 1, например a k = 1. Начинающий берёт из первой кучки камни так, чтобы числа a k +1 , a k +2 , . . не изменились, а каждое из чисел d k , d k −1 , d k −2 , . . . , стало чёт- ным. В частности, число изменяется оно становится равно это означает, что первый игрок действительно берёт по крайней мере один камень. Второй игрок любым своим ходом обязательно сделает одно из чисел d i нечётным, поэтому первый игрок снова сможет применить туже самую стратегию. Игра закончится за конечное число ходов. При этом после хода второго игрока в какой-то кучке обязательно остаётся хотя бы один камень. Поэтому второй игрок выиграть не может. б) После первого хода начинающего хотя бы одно из чисел станет нечётным, поэтому второй игрок может воспользоваться той же самой стратегией, которой в случае а) пользовался первый игрок. Пусть n = a 0 + 2a 1 + 2 2 a 2 + . . . + 2 k a k — двоичная запись числа n. Тогда h n 2 i = a 1 + 2a 2 + 2 2 a 3 + . . . + 2 k −1 a k , h n 2 2 i = a 2 + 2a 3 + . . . + 2 k −2 a k , h n 2 3 i = a 3 + . . . + 2 k −3 a k , h n 2 k i = a k Решения задач 267 Поэтому h n 2 i + h n 2 2 i + . . . + h n 2 k i = = (2 − 1)a 1 + (2 2 − 1)a 2 + (2 3 − 1)a 3 + . . . + (2 k − 1)a k = = n − (a 0 + a 1 + . . . + a k ). 21.29. В d-ичной системе счисления, где d = 10 100 , мы получаем последовательность натуральных чисел, которые не содержат цифры. Как ив задаче 21.8, получаем для некоторого 6 (d − 1) k . В таком случае a n /n > “ 1 + 1 d − 1 ” k 21.30. Легко видеть, что h n p k i = 0 при k > m и h n p m i = a m , h n p m −1 i = a m p + a m −1 , h n p i = a m p m −1 + a m −1 p m −2 + . . . + Поэтому h n p i + h n p 2 i + . . . + h n p m i = = a m (1 + p + . . . + p m −1 ) + a m −1 (1 + p + . . . + p m −2 ) + . . . + a 1 = = a m p m − 1 p − 1 + a m −1 p m −1 − 1 p − 1 + . . . + a 1 p − 1 p − 1 = = a m p m + a m −1 p m −1 + . . . + a 1 p + a 0 − (a m + a m −1 + . . . + a 0 ) p − 1 21.31. Наибольшая степень простого числа p, на которую делится, равна h n p i + h n p 2 i + h n p 3 i + . . . Поэтому согласно задаче наибольшая степень числа p, на которую делится C m n +m = = (m + n)! m! n! , равна + n − s(m + n) p − 1 − m − s(m) p − 1 − n − s(n) p − 1 = s(m) + s(n) − s(m + n) p − где s(m) — сумма цифр числа m в p-ичной системе счисления Глава 21. Системы счисления Остаётся доказать, что s(m + n) = s(m) + s(n) − (p − 1)k, где — количество переносов при сложении чисел m и n. При каждом переносе сумма цифр уменьшается на p−1: вместо p+a получается + a. 21.32. Согласно задаче 14.30 (1 + x) p ≡ 1 + x p (mod p). Индукцией по k получаем (1 + x) p k ≡ 1 + x p k (mod p). Значит+ x) b = (1 + x) b 0 +b 1 p +...+b m p m = (1 + x) b 0 (1 + x) b 1 p . . . (1 + x) b m p m ≡ ≡ (1 + x) b 0 (1 + x p ) b 1 . . . (1 + x p m ) b m ≡ m Y i =0 b i X k =0 C k b i x kp i (mod Поэтому коэффициент при x a = в выражении для+ по модулю p равен C a 0 b 0 C a 1 b 1 . . . C a m b m . С другой стороны, он равен C a b 21.33. Ответ система с основанием 3. С помощью m = цифр мы можем записать чисел. Поэтому нужно доказать, что, те. для любого натурального d. Это неравенство доказано в решении задачи 13.11. 21.34. Согласно задаче 13.5 имеет место неравенство 1 · 1! + + 2 · 2! + 3 · 3! + . . . + k · k! < (k + 1)!, поэтому для данного n число определяется однозначно. А именно, должны выполняться неравенства. Затем выбираем так, чтобы выполнялись неравенства a k · k! 6 n < (a k + 1)k!. Тогда a k · k! 6 n < (k + 1)!, поэтому. Кроме того, n − a k · k! < (a k + 1)k! − a k · k! = k!. Поэтому для числа n − a k · k! можно повторить те же самые рассуждения. Предположим, что требуемое равенство имеет место. Домножив обе части равенства на n!, получим равенство вида · p q = nX + x n , где X — целое число. Таким образом · p q — целое число и x n — остаток отделения этого числа на n. Отметим, что если число · целое и m>n, то число · делится на m, поэтому 0. Ясно также, что если число n достаточно велико, то n! делится на q. Таким образом, числа n и определены однозначно. Аналогично получаем, что x n −1 — это остаток отделения числа · p q − на n − 1 и т. д. В конце остаётся целое число x 1 ГЛАВА 22 ГРАФЫ Графом называют набор точек (называемых вершинами графа), некоторые из которых соединены рёбрами. При этом нас интересует только то, какие именно пары точек соединены рёбрами. Многие задачи естественно формулируются на языке графов. Граф называют связным, если для любых его вершин v и v ′ найдётся последовательность вершин v 1 = v, v 2 , v 3 , . . . , v n = в которой любые две соседние вершины и соединены реб- ром. Циклом называют последовательность рёбер v 1 v 2 , v 2 v 3 , . . . , v n −1 v n , v n v 1 (n > 3). 22.1. Докажите, что среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. (Иными словами, в любом графе с шестью вершинами есть либо три вершины, попарно соединённые рёбрами, либо три вершины, попарно не соединённые рёбрами.) 22.2. Докажите, что в любом графе число вершин, из которых выходит нечётное число рёбер, чётно. 22.3. Дан отрезок OA. Из конца отрезка A выходит 5 отрезков. Из каждой точки могут выходить ещё пять новых отрезков, или ни одного нового отрезка и т. д. Может ли число свободных концов построенных отрезков равняться 1001? 22.4. а) Докажите, что граф, в котором из каждой вершины выходит чётное число рёбер, можно представить в виде объединения непересекающихся циклов. б) Докажите, что граф, в котором количество вершин, из которых выходит нечётное число рёбер, равно 2n, можно Глава 22. Графы представить в виде объединения непересекающихся циклов и n несамопересекающихся путей, идущих пор брам. Обходы графов Назовём обходом графа путь, идущий пор брам графа и проходящий по каждому ребру ровно один раз. Докажите, что если обход графа существует, то количество вершин, из которых выходит нечётное число рёбер, не превосходит двух (Эйлер. Докажите, что если граф связен и количество вершин, из которых выходит нечётное число рёбер, не превосходит двух, то существует обход этого графа (Эйлер. Ориентированные графы Граф называют ориентированным, если на каждом его ребре указано направление движения, те. ребро выходит из одной вершины и входит в другую. Докажите, что любой связный граф сч тным числом рёбер можно ориентировать так, что из каждой вершины будет выходить чётное число рёбер. 22.3. Паросочетания Паросочетанием называют набор рёбер графа, не имеющих общих вершин. Паросочетание называют максимальным, если в него входит наибольшее возможное число рёбер (те. любое паросочетание для данного графа содержит не больше рёбер, чем максимальное паросочетание). 22.8. Докажите, что паросочетание максимально тогда и только тогда, когда в графе нет пути, который идёт пор брам графа и обладает следующими свойствами 1) из любых двух соседних рёбер пути одно принадлежит паросочета- нию, а другое не принадлежит 2) изначальной и конечной точек путине выходят рёбра паросочетания; 3) начало и конец разные вершины ( Берж). Решения задач. Пусть вершины графа разбиты на два непересека- ющихся множества X и Y, причём все рёбра соединяют вершины из разных множеств. Докажите, что паросочета- ние, включающее все вершины множества X, существует тогда и только тогда, когда для любого набора выделенных вершин из множества X количество вершин, соединённых с выделенными вершинами, не меньше количества выделенных вершин (Холл. На танцы пришло несколько юношей и несколько девушек, причём каждая девушка знакома ровно с юношами и каждый юноша знаком ровно с k девушками, причём k > 1. Докажите, что они могут разбиться на пары так, что в каждой паре будут юноша и девушка, знакомые друг с другом. |