Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
21.3. Другие цифры. Докажите, что предпоследняя цифра числа при любом n > 2 чётна. 21.7. Пусть a и b — последняя и предпоследняя цифры числа 2 n . Докажите, что если n > 3, то ab делится на 6. 21.8. Пусть a 1 , a 2 , . . . — различные натуральные числа, в десятичной записи которых не встречается цифра 1. Докажите, что среди чисел a n /n есть сколь угодно большие числа. Сумма цифр. Пусть a > 2 — натуральное число, которое не делится ни на 2, ни на 5. Докажите, что сумма цифр числа при достаточно большом m может быть сколь угодно велика. Докажите, что сумма цифр числа может быть сколь угодно велика. Пусть P(x) — многочлен с натуральными коэффициентами сумма цифр числа P(n). Докажите, что некоторое число встречается в последовательности a 1 , a 2 , a 3 , . . . бесконечно много раз. Разные задачи о десятичной записи. Найдите четырёхзначное число, которое является точным квадратом и у которого две первые цифры одинаковые и две последние тоже. Числа ив десятичной записи) записаны одно за другим. Сколько цифр имеет полученное число Глава 21. Системы счисления. Докажите, что любое положительное число a можно представить в виде суммы девяти чисел, десятичные записи которых содержат только цифры 0 и k, где k — фиксированная цифра, отличная от нуля. Найдите все трёхзначные числа, равные сумме факториалов своих цифр. Все целые числа выписаны подряд, начиная с единицы. Какая цифра стоит нам месте. Периоды десятичных дробей и репьюниты Пусть p — простое число, отличное от 2 и 5. Длиной периода числа p называют количество цифр в периоде десятичной записи дроби 1/p. 21.17. Пусть n — натуральное число, не превосходящее. Докажите, что количество цифр в периоде десятичной записи числа n/p равно длине периода числа p. 21.18. Докажите, что длина периода числа p является делителем числа p − 1. 21.19. Периоды правильных дробей со знаменателем получаются друг из друга циклической перестановкой = 0,(142857), 3/7 = 0,(428571), 2/7 = 0,(285714), 6/7 = 0,(857142), 4/7 = 0,(571428), 5/7 = Докажите, что таким же свойством обладают все простые числа p, у которых длина периода равна p − 1. 21.20. Период дроби 1/7 = 0,(142857) обладает следующим свойством 142 + 857 = 999. Докажите, что аналогичным свойством обладает период дроби 1/p для любого простого числа p, у которого длина периода равна p − 1. * * * Репьюнитом называют натуральное число вида 111 . . . те. натуральное число, в десятичной записи которого встречаются только единицы Условия задач. Докажите, что длина периода простого числа p 6= равна числу единиц в наименьшем репьюните, делящемся на p. 21.22. Пусть p > 7 — простое число. Докажите, что число . . . делится на p. 21.7. Определение d-ичной записи числа. Пусть d > 1 — натуральное число. Докажите, что любое натуральное число n единственным образом представляется в виде n = a 0 + a 1 d + a 2 d 2 + . . . + a k d k , где 0 6 a i 6 6 d − 1 — целые числа, причём a k 6= Выражение n=a 0 +a 1 d +a 2 d 2 +. . называют d-ичной записью числа n. 21.8. Двоичная система. Пусть n — натуральное число, a 0 — остаток отделения на 2. Положим n 1 = (n − a 0 )/2, a 1 — остаток отделения на 2 и т. д. до тех пор, пока не получим n m = и a m = 1. Докажите, что a m 2 m + a m −1 2 n −1 + . . . + a 1 · 2 + двоичная запись числа n. 21.25. Докажите, что (1 + x)(1 + x 2 )(1 + x 4 ) . . . (1 + x 2 n ) = = 1 + x + x 2 + x 3 + . . . + x 2 n+1 −1 21.26. Докажите, что количество нечётных коэффициентов многочлена (1 + равно 2 d , где d — сумма цифр в двоичной записи числа n те. количество единиц в двоичной записи числа n). 21.27. Игра ним) Есть три кучки камней. Двое игроков по очереди берут произвольное число камней из любой кучки, но только из одной. Выигрывает тот, кто берёт последний камень. Запишем числа камней в кучках в двоичной системе 2 +. . . , b 0 +b 1 ·2 +b 2 ·2 2 +. . . , c 0 +c 1 ·2 +c 2 ·2 2 +. . Положим d i = a i + b i + c i Глава 21. Системы счисления а) Докажите, что если среди чисел есть хотя бы одно нечётное, то игрок, делающий первый ход, всегда может обеспечить себе выигрыш. б) Докажите, что если все числа d i чётные, то второй игрок всегда может обеспечить себе выигрыш. Докажите, что для любого натурального n число 2 i − h n 2 3 i − . . равно сумме цифр двоичной записи числа См. также задачи 19.5, 33.5. 21.9. Другие системы счисления. Пусть a 1 , a 2 , . . . — различные натуральные числа, в десятичной записи которых не встречается подряд единиц. Докажите, что среди чисел a n /n есть сколь угодно большие числа. Запишем натуральное число n в p-ичной системе счисления n = a 0 + a 1 p + a 2 p 2 + . . . + a m p m . Докажите, что число h n p i + h n p 2 i + h n p 3 i + . . . равно (a 0 + a 1 + . . . + a m ) p − 1 21.31. Пусть p — простое число. Докажите, что если наибольшая степень числа p, делящая C m n+m , то k — количество переносов при сложении чисел m ив p-ичной системе счисления. Пусть p — простое число. Запишем натуральные числа a ив p-ичной системе a = a 0 + a 1 p + . . . + a m p m , b = b 0 + b 1 p + . . . + b m p m . Докажите, что C a 0 b 0 C a 1 b 1 . . . C a m b m (mod p). 21.33. Если считать цифры, стоящие в разных разрядах, разными, тов d-ичной системе счисления nd цифр позволяют записать чисел (от 0 до d n − 1). Какая система счисления в этом отношении самая экономная, те. позволяет записать наибольшее количество чисел с помощью данного числа цифр (Сравнивая системы счисления с основаниями Решения задачи d 2 , мы рассматриваем только наборы из m цифр, где делится на и См. также задачи 20.15, 20.17. 21.10. Другие представления чисел. Докажите, что любое натуральное число n единственным образом представляется в виде n=a 1 · 1! + a 2 · 2! + . . . . . . + a k · k!, где a i — целые числа, удовлетворяющие неравенствами. Докажите, что любое рациональное число p/q 6= однозначно представляется в виде x 1 + x 2 2! + x 3 3! + . . . где x 1 , . . . , x n — целые числа, причём 0 6 x k < k при k > и x n 6= См. также задачу Решения. Ответ и 625. Пусть N — искомое число. Тогда N = N(N − 1) делится на 1000. Числа N и N − 1 взаимно простые, поэтому одно из них делится на 8, а другое на 125. Пусть сначала N = 125k. Тогда k 6 8. Среди чисел 125k − 1, k = 1, . . ., только число 624 делится на 8. Пусть теперь N − 1 = 125k. Тогда 125k + 1, поэтому k 6 7. Среди чисел 125k + 1, k = 1, . . . , только число 376 делится на Если N 2 − N = N(N − 1) делится на 1000, то N k − N = N(N k −1 − тоже делится на 1000, поскольку N k −1 − 1 делится на N − 1. 21.2. а) Число a 2 n −a n = a n (a n −1) должно делиться на 10 n = Числа и a n − 1 взаимно простые и a n 6= 0 и 1, поэтому либо a n делится на и a n − 1 делится на 5 n , либо делится на и a n − 1 делится на 2 n . В первом случае a n = 2 n a, где 1 6 a 6 5 n − Все числа 2 n a, где 1 6 a 6 5 n − 1, при делении надают разные остатки, причём ни одно из них не делится на 5 n . Действительно, если число делится на 5 n , то должно делиться на Таким образом, при делении чисел a n = 2 n a, где 1 6 a 6 5 n − 1, на мы получим все разные остатки от 1 до 5 n − 1, причём ровно по одному разу. Требуемое число a n = 2 n a — это то, которое при де Глава 21. Системы счисления лении на дат остаток 1. Аналогично разбираем второй случай и получаем, что b n = 5 n b и дат остаток 1 при делении наб) Из решения задачи а) следует, что a n = 2 n a ≡ 1 (mod и b n = 5 n b ≡ 1 (mod 2 n ). Значит, a n + b n ≡ 1 (mod 5 n ) и a n + b n ≡ ≡ 1 (mod 2 n ), те. число a n + b n − 1 делится на в) Последние n цифр числа определяются последними цифрами числа a n +1 . Значит, если a n — число, которое получается из a n +1 вычёркиванием первой цифры, то оканчивается наг) Пусть a 2 n = x · 10 n +1 + a n +1 . Нужно доказать, что a 2 n +1 − делится на 10 n +1 . Ясно, что a n +1 = (a 2 n − x · 10 n +1 ) 2 − (a 2 n − x · 10 n +1 ) = = a 4 n − 2xa 2 n · 10 n +1 + x 2 · 10 2n+2 − a 2 n + x · Далее, a 4 n − a 2 n = (a 2 n − a n )(a 2 n + a n ). Число a 2 n − делится на а число a 2 n + делится на 10, поскольку оно чётно и оба числа и оканчиваются на Пусть b 5 n = y · 10 n +1 + b n +1 . Нужно доказать, что b 2 n +1 − делится на 10 n +1 . Ясно, что b 2 n +1 − b n +1 ≡ b 10 n − b 5 n (mod 10 n +1 ). Далее (b 2 n −b n )(b 8 n + b 7 n + b 6 n + b 5 n + b 4 n ). Число делится на а число b 8 n + . . . + делится на 10, поскольку оно представляет собой сумму пяти чисел, оканчивающихся на 6. 21.3. Ответ. По условию a·10 p < 2 n < (a + и a·10 q < 5 n < < (a +1)10 q . Поэтому a 2 10 p +q < 10 n < (a +1) 2 10 p +q , те. При этом (a + 1) 2 6 100. Значит, a 2 < 10 < (a + те. С цифры 3 начинаются числа 2 и 5 5 21.4. а) Пусть A — данное натуральное число. Покажем, что натуральное число n можно выбрать так, что 10 m A < 2 n < 10 m (A + те. Эквивалентное условие таково существуют натуральные числа m и n, для которых lg A < < n lg 2 −m б) Очевидным образом следует из а. Достаточно доказать, что число может начинаться с любого набора цифр. Это делается точно также, как при решении задачи 21.4. 21.6. Пусть N = a 0 + a 1 · 10 + a 2 · 100 + . . . Тогда 3N = 3a 0 + 30a 1 + + 300a 2 + . . . Поэтому если число a 1 чётно, то предпоследняя цифра числа 3N имеет такую же чётность, как и предпоследняя цифра числа 3a 0 . Равенство 3 4 = 81 показывает, что последними цифрами чисел вида могут быть только 3, 9, 7 и 1. При этом 3 · 3 = 9, Решения задачи во всех случаях предпоследняя цифра чётна. 21.7. Поскольку 2 4 = 16, число 2 оканчивается на 6. Соответственно, числа 2 4k+1 , 2 4k+2 , 2 оканчиваются на 2, 4, 8. Для чисел вида 2 требуемое утверждение очевидно, поскольку b = Заметим также, что число b всегда чётно. Поэтому достаточно проверить, что числа 2 4k+1 − 2, 2 4k+2 − 4, 2 4k+3 − 8 делятся на иными словами, достаточно проверить, что 2 4k − 1 делится на Число 2 4 = 16 при делении на 3 даёт остаток 1, поэтому число 2 тоже даёт остаток 1 при делении на 3. 21.8. Количество натуральных чисел, которые не превосходят ив десятичной записи которых не встречается цифра 1, не превосходит 9 k − 1. Действительно, на каждом из k разрядов стоит одна из 9 цифр, причём все эти цифры не могут быть одновременно нулями. Значит, для некоторого n 6 9 k . В таком случае > (10/9) k . Число может быть сколь угодно велико. Предположим, что сумма цифр чисел вида a m ограничена. Тогда сумма цифр числа не превосходит суммы цифр числа для некоторого фиксированного N. Пусть a N < 10 k . Согласно задаче существует натуральное число n, для которого a n − делится на 10 k . Тогда сумма цифр числа a n +N = a N (a n − 1) + больше суммы цифр числа a N . Получено противоречие. Это очевидным образом следует из задачи 21.4. 21.11. Пусть P(x) = b m x m + b m −1 x m −1 + . . . + b 0 . Выберем натуральное число k так, что число больше любого из чисел, b 1 , . . . , b m . Тогда в десятичной записи числа P(10 k ) сначала идут цифры числа b m , затем нули, затем цифры числа b m −1 , затем нули и т. д. Для любого натурального числа l десятичная запись числа P(10 k +l ) устроена аналогично. У всех этих чисел сумма цифр одна и та же. Пусть a — первая и вторая цифры, b — третья и четвёр- тая. Тогда данное число равно 11(b+100a), поэтому для некоторого натурального числа x. Кроме того, 100 6 b + 100a 6 6 908, а значит, 4 6 x 6 9. Вычисляя квадраты чисел 44, . . . , получаем, что ровно одно из них имеет требуемый вид 88 2 = 7744. 21.13. Ответ. Предположим, что число имеет p цифра число 5 n — q цифр. Тогда и Перемножив эти неравенства, получаем 10 p +q−2 < 10 n < 10 p +q . Следовательно. Представим число a/k в виде суммы девяти чисел, десятичные записи которых содержат только цифры 0 и 1. Воспользовавшись тем, что a = k(a/k), получим требуемое представление Глава 21. Системы счисления. Ответ. Пусть N = 100x + 10y + z — искомое число, для которого N = x! + y! + z!. Число 7! = 5040 четырёхзначное, поэтому ни одна цифра числа N не превосходит 6. Поэтому число меньше 700. Но тогда ни одна цифра числа N не превосходит поскольку 6! = 720. Неравенство 3 · 4! = 72 < 100 показывает, что хотя бы одна цифра числа N равна 5. При этом x 6= 5, поскольку · 5! = 360 < 500. Равенство 3 · 5! = 360 показывает также, что x 6 Более того, x 6 2, поскольку 3! + 2 · 5! = 246 < 300. Число 255 не удовлетворяет условию задачи, а если лишь одна цифра искомого числа равна 5, то x 6 1, поскольку 2! + 5! + 4! = 146 < 200. Так как 1! + 5! + 4! = 145 < 150, получаем y 6 4. Следовательно, z = Учитывая, что x = 1 и 0 6 y 6 4, находим единственное решение 145. |