WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 27 | 28 || 30 | 31 |   ...   | 65 |

Выражение n = a0+a1d+a2d2+...+akdk называют d-ичной записью числа n.

21.8. Двоичная система 21.24. Пусть n натуральное число, a0 остаток от деления n на 2. Положим n1 = (n - a0)/2, a1 остаток от деления n1 на 2 и т.д.

до тех пор, пока не получим nm = 1 и am = 1. Докажите, что am2m + + am-12n-1 +... + a1 · 2 + a0 двоичная запись числа n.

n 21.25. Докажите, что (1 + x)(1 + x2)(1 + x4)... (1 + x2 ) = 1 + x + n++ x2 + x3 +... + x2 -1.

21.26. Докажите, что количество нечётных коэффициентов многочлена (1 + x)n равно 2d, где d сумма цифр в двоичной записи числа n (т.е. количество единиц в двоичной записи числа n).

21.27. (Игра ним) Есть три кучки камней. Двое игроков по очереди берут произвольное число камней из любой кучки, но только одной.

Выигрывает тот, кто берёт последний камень.

Запишем числа камней в кучках в двоичной системе: a0 + a1 · 2 + + a2 · 22 +..., b0 + b1 · 2 + b2 · 22 +..., c0 + c1 · 2 + c2 · 22 +.... Положим di = ai + bi + ci.

а) Докажите, что если среди чисел di есть хотя бы одно нечётное, то игрок, делающий первый ход, всегда может обеспечить себе выигрыш.

б) Докажите, что если все числа di чётные, то второй игрок всегда может обеспечить себе выигрыш.

21.28. Докажите, что для любого натурального n число n n n n - - - -...

2 22 равно сумме цифр двоичной записи числа n.

См. также задачи 19.5, 33.5.

Глава 21. Системы счисления 21.9. Другие системы счисления 21.29. Пусть a1, a2,... различные натуральные числа, в десятичной записи которых не встречается подряд 100 единиц. Докажите, что среди чисел an/n есть сколь угодно большие числа.

21.30. Запишем натуральное число n в p-ичной системе счисления:

n n n = a0 + a1p + a2p2 +... + ampm. Докажите, что число + + p p n n - (a0 + a1 +... + am) + +... равно.

p3 p - 21.31. Пусть p простое число. Докажите, что если pk наиболь n + m шая степень числа p, делящая, то k количество переносов m при сложении чисел m и n в p-ичной системе счисления.

21.32. Пусть p простое число. Запишем натуральные числа a и b в p-ичной системе: a = a0 + a1p +... + ampm, b = b0 + b1p +... + bmpm.

Докажите, что b b0 b1 bm... (mod p).

a a0 a1 am 21.33. Если считать цифры, стоящие в разных разрядах, разными, то в d-ичной системе счисления nd цифр позволяют записать dn чисел (от 0 до dn - 1). Какая система счисления в этом отношении самая экономная, т.е. позволяет записать наибольшее количество чисел с помощью данного числа цифр (Сравнивая системы счисления с основаниями d1 и d2, мы рассматриваем только наборы из m цифр, где m делится на d1 и d2.) См. также задачи 20.15, 20.17.

21.10. Другие представления чисел 21.34. Докажите, что любое натуральное число n единственным образом представляется в виде n = a1 · 1! + a2 · 2! +... + ak · k!, где ai целые числа, удовлетворяющие неравенствам 0 ai i, и ak = 0.

21.35. Докажите, что любое рациональное число p/q = 0 однозначно представляется в виде p x2 x3 xn = x1 + + +... +, q 2! 3! n! где x1,..., xn целые числа, причём 0 xk < k при k 2 и xn = 0.

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

236 Глава 21. Системы счисления Решения 21.1. О т в е т: 376 и 625. Пусть N искомое число. Тогда N2 - N = = N(N - 1) делится на 1000. Числа N и N - 1 взаимно простые, поэтому одно из них делится на 8, а другое на 125. Пусть сначала N = 125k. Тогда k 8. Среди чисел 125k - 1, k = 1,..., 8, только число 624 делится на 8.

Пусть теперь N - 1 = 125k. Тогда N = 125k + 1, поэтому k 7. Среди чисел 125k + 1, k = 1,..., 7, только число 376 делится на 8.

Если N2 - N = N(N - 1) делится на 1000, то Nk - N = N(Nk-1 - 1) тоже делится на 1000, поскольку Nk-1 - 1 делится на N - 1.

21.2. а) Число a2 -an = an(an -1) должно делиться на 10n = 2n5n. Числа n an и an - 1 взаимно простые и an = 0 и 1, поэтому либо an делится на 2n и an - 1 делится на 5n, либо an делится на 5n и an - 1 делится на 2n. В первом случае an = 2na, где 1 a 5n - 1. Все числа 2na, где 1 a 5n - 1, при делении на 5n дают разные остатки, причём ни одно из них не делится на 5n.

Действительно, если число (a-a )2n делится на 5n, то a-a должно делиться на 5n. Таким образом, при делении чисел an = 2na, где 1 a 5n - 1, на 5n мы получим все разные остатки от 1 до 5n - 1, причём ровно по одному разу.

Требуемое число an = 2na это то, которое при делении на 5n даёт остаток 1. Аналогично разбираем второй случай и получаем, что bn = 5nb и bn даёт остаток 1 при делении на 2n.

б) Из решения задачи а) следует, что an = 2na 1 (mod 5n) и bn = = 5nb 1 (mod 2n). Значит, an + bn 1 (mod 5n) и an + bn 1 (mod 2n), т.е.

число an + bn - 1 делится на 10n.

в) Последние n цифр числа a2 определяются последними n цифрами n+числа an+1. Значит, если an число, которое получается из an+1 вычёркиванием первой цифры, то a2 оканчивается на an.

n г) Пусть a2 = x · 10n+1 + an+1. Нужно доказать, что a2 - an+1 делится n n+на 10n+1. Ясно, что a2 - an+1 = (a2 - x · 10n+1)2 - (a2 - x · 10n+1) = n+1 n n = a4 - 2xa2 ·10n+1 + x2 ·102n+2 - a2 + x ·10n+1. Далее, a4 - a2 = (a2 - an)(a2 + n n n n n n n + an). Число a2 - an делится на 10n, а число a2 + an делится на 10, поскольку n n оно чётно и оба числа a2 и an оканчиваются на 5.

n Пусть b5 = y · 10n+1 + bn+1. Нужно доказать, что b2 - bn+1 делится n n+на 10n+1. Ясно, что b2 - bn+1 b10 - b5 (mod 10n+1). Далее, b10 - b5 = n+1 n n n n = (b2 - bn)(b8 + b7 + b6 + b5 + b4 ). Число b2 - bn делится на 10n, а число n n n n n n n b8 +... + b4 делится на 10, поскольку оно представляет собой сумму пяти n n чисел, оканчивающихся на 6.

21.3. О т в е т: 3. По условию a · 10p < 2n < (a + 1)10p и a · 10q < 5n < (a + + 1)10q. Поэтому a210p+q < 10n < (a + 1)210p+q, т.е. a2 < 10n-p-q < (a + 1)2.

При этом (a + 1)2 100. Значит, a2 < 10 < (a + 1)2, т.е. a = 3. С цифры начинаются числа 25 и 55.

21.4. а) Пусть A данное натуральное число. Покажем, что натуральное число n можно выбрать так, что 10mA < 2n < 10m(A + 1), т.е. m + + lg A < n lg 2 < m + lg(A + 1). Эквивалентное условие таково: существуют Глава 21. Системы счисления натуральные числа m и n, для которых lg A < n lg 2 - m < lg(A + 1). Число lg 2 иррационально (это доказывается точно так же, как в решении задачи 27.25 а). Поэтому можно воспользоваться результатом задачи 17.13 б).

б) Очевидным образом следует из а).

21.5. Достаточно доказать, что число 4n может начинаться с любого набора цифр. Это делается точно так же, как при решении задачи 21.4.

21.6. Пусть N = a0 + a1 · 10 + a2 · 100 +... Тогда 3N = 3a0 + 30a1 + 300a2 + +... Поэтому если число a1 чётно, то предпоследняя цифра числа 3N имеет такую же чётность, как и предпоследняя цифра числа 3a0. Равенство 34 = показывает, что последними цифрами чисел вида 3n могут быть только 3, 9, 7 и 1. При этом 3 · 3 = 9, 3 · 9 = 27, 3 · 7 = 21 и 3 · 1 = 3; во всех случаях предпоследняя цифра чётна.

21.7. Поскольку 24 = 16, число 24k оканчивается на 6. Соответственно, числа 24k+1, 24k+2, 24k+3 оканчиваются на 2, 4, 8. Для чисел вида 24k требуемое утверждение очевидно, поскольку b = 6. Заметим также, что число b всегда чётно. Поэтому достаточно проверить, что числа 24k+1 - 2, 24k+2 - 4, 24k+3 - 8 делятся на 3, иными словами, достаточно проверить, что 24k - делится на 3. Число 24 = 16 при делении на 3 даёт остаток 1, поэтому число 24k тоже даёт остаток 1 при делении на 3.

21.8. Количество натуральных чисел, которые не превосходят 10k и в десятичной записи которых не встречается цифра 1, не превосходит 9k - 1.

Действительно, на каждом из k разрядов стоит одна из 9 цифр, причём все эти цифры не могут быть одновременно нулями. Значит, an 10k для некоторого n 9k. В таком случае an/n (10/9)k. Число (10/9)k может быть сколь угодно велико.

21.9. Предположим, что сумма цифр чисел вида am ограничена. Тогда сумма цифр числа am не превосходит суммы цифр числа aN для некоторого фиксированного N. Пусть aN < 10k. Согласно задаче 17.2 существует натуральное число n, для которого an -1 делится на 10k. Тогда сумма цифр числа an+N = aN (an - 1) + aN больше суммы цифр числа aN. Получено противоречие.

21.10. Это очевидным образом следует из задачи 21.4.

21.11. Пусть P (x) = bmxm + bm-1xm-1 +... + b0. Выберем натуральное число k так, что число 10k больше любого из чисел b0, b1,..., bm. Тогда в десятичной записи числа P (10k) сначала идут цифры числа bm, затем нули, затем цифры числа bm-1, затем нули и т.д. Для любого натурального числа l десятичная запись числа P (10k+l) устроена аналогично. У всех этих чисел сумма цифр одна и та же.

21.12. Пусть a первая и вторая цифры, b третья и четвёртая. Тогда данное число равно 11(b + 100a), поэтому b + 100a = 11x2 для некоторого натурального числа x. Кроме того, 100 b + 100a 908, а значит, 4 x 9.

Вычисляя квадраты чисел 44,..., 99, получаем, что ровно одно из них имеет требуемый вид: 882 = 7744.

238 Глава 21. Системы счисления 21.13. О т в е т: n + 1. Предположим, что число 2n имеет p цифр, а число 5n q цифр. Тогда 10p-1 < 2n < 10p и 10q-1 < 5n < 10q. Перемножив эти неравенства, получаем 10p+q-2 < 10n < 10p+q. Следовательно, p + q = n + 1.

21.14. Представим число a/k в виде суммы девяти чисел, десятичные записи которых содержат только цифры 0 и 1. Воспользовавшись тем, что a = k(a/k), получим требуемое представление.

21.15. О т в е т: 145. Пусть N = 100x + 10y + z искомое число, для которого N = x! + y! + z!. Число 7! = 5040 четырёхзначное, поэтому ни одна цифра числа N не превосходит 6. Поэтому число N меньше 700. Но тогда ни одна цифра числа N не превосходит 5, поскольку 6! = 720. Неравенство 3 · 4! = 72 < 100 показывает, что хотя бы одна цифра числа N равна 5. При этом x = 5, поскольку 3 · 5! = 360 < 500. Равенство 3 · 5! = 360 показывает также, что x 3. Более того, x 2, поскольку 3!+2·5! = 246 < 300. Число не удовлетворяет условию задачи, а если лишь одна цифра искомого числа равна 5, то x 1, поскольку 2! + 5! + 4! = 146 < 200. Так как 1! + 5! + 4! = = 145 < 150, получаем y 4. Следовательно, z = 5. Учитывая, что x = 1 и 0 y 4, находим единственное решение N = 145.

21.16. О т в е т: цифра 7. Однозначных чисел ровно 9, двузначных 99-9 = = 90, трёхзначных 999 - 99 - 9 = 900, четырёхзначных 9000 и т.д. Однозначные числа займут в выписанном ряду первые 9 мест, двузначные 90 · 2 = мест, трёхзначные 900 · 3 = 2700 мест, четырёхзначные 9000 · 4 = 36 000 мест, пятизначные 90000 · 5 = 450 000 мест. Поэтому интересующая нас цифра принадлежит пятизначному числу.

Цифры, принадлежащие не более чем четырёхзначным числам, имеют номера от 1 до 9+180+2700+36 000 = 38 889. Разность 206 788-38 889 = 167 нужно разделить на 5 с остатком: 167 899 = 5 · 33 579 + 4. Интересующая нас цифра принадлежит 33 580-му пятизначному числу, т.е. числу 43 579 (первое пятизначное число это число 10 000). В этом числе интересующая нас цифра стоит на 4-м месте.

21.17. Длина периода десятичной записи дроби n/p равна наименьшему натуральному числу d, для которого n(10d - 1) делится на p. Числа n и p взаимно простые, поэтому n(10d - 1) делится на p тогда и только тогда, когда 10d - 1 делится на p.

21.18. Длина периода числа p равна наименьшему натуральному числу d, для которого 10d - 1 делится на p. Согласно малой теореме Ферма (задача 31.1) 10p-1 - 1 делится на p. Пусть p - 1 = ad + r, где 0 r < d. Требуется доказать, что r = 0. Предположим, что r > 0. Тогда 10p-1 = (10d)a10r 10r (mod p), поэтому 10r 1 (mod p). Это противоречит минимальности числа d.

21.19. Будем делить 1 на p столбиком. В результате периодически будут повторяться некоторые остатки. Например, при делении 1 на 7 периодически повторяются остатки 1, 3, 2, 6, 4, 5. В случае, когда длина периода равна p-1, в этой последовательности встречаются все возможные остатки 1, 2,..., p-1.

Глава 21. Системы счисления Вернёмся к примеру дробей со знаменателем 7. Деление в столбик показывает, что 1/7 = 0, (142857). Вслед за остатком 1 встречается остаток 3. Это означает, что десятичная запись дроби 3/7 получается из десятичной записи дроби 1/7 вычёркиванием первой цифры после нуля. Дробь 2/7 получается вычёркиванием первых двух цифр, дробь 6/7 первых трёх и т.д.

21.20. Число p-1 чётно; запишем его в виде p-1 = 2k. Период дроби 1/p, записанный как натуральное число, имеет вид a · 10k + b. Требуется доказать, что a + b = 10k - 1.

Число 102k - 1 = (10k - 1)(10k + 1) делится на p. При этом 10k - 1 не делится на p, поскольку иначе длина периода числа p была бы меньше 2k.

Следовательно, 10k + 1 делится на p.

10k + Ясно, что 102k-1 = (a·10k+b)·p. Поэтому число a·10k+b = (10k-1) p делится на 10k -1. Далее, a+b a·10k +b (mod 10k -1), поэтому a+b делится на 10k - 1. Кроме того, a + b < 2(10k - 1), поэтому a + b = 10k - 1.

21.21. Пусть длина периода простого числа p равна d. Это означает, что d наименьшее натуральное число, для которого 10d-1 делится на p. Ясно, что 10d - 1 = 9Rd, где Rd репьюнит, содержащий d единиц. Если p простое число, отличное от 3, то 9Rd делится на p тогда и только тогда, когда Rd делится на p.

21.22. Если p простое число, отличное от 2 и 5, то число 10p-1 - делится на p (задача 31.1). Это число имеет вид 99.. 9. Поэтому если p = 3,.

p-то число 11.. 1 тоже делится на p.

.

p-21.23. Выберем k так, что dk n < dk+1. Положим ak = [n/dk]. Тогда 1 ak d - 1 и n = akdk + n, где 0 n < dk. Если n = 0, то выберем l < k так, что dl n < dl+1, и положим al = [n /dl] и al+1 =... = ak-1 = (если l < k - 1). Тогда n = akdk + aldl + n. Для n поступаем аналогичным образом и т.д.

Число ak определяется единственным образом. Действительно, если n = = a0 + a1d + a2d2 +... + akdk, то dk n (d - 1) + d(d - 1) +... + dk(d - 1) = = dk+1 - 1 < dk+1. Все остальные числа al тоже определяются однозначно.

21.24. Пусть n = bk2k + bk-12k-1 +... + b1 · 2 + b0. Тогда a0 = b0 и n1 = = bk2k-1+bk-12k-2+...+b1. Поэтому a1 = b1 и n2 = bk2k-2+bk-12k-3+...+bи т.д.

21.25. Каждое число от 0 до 2n+1 - 1 можно единственным образом представить в виде суммы различных чисел 0, 1, 2, 22,..., 2n. Поэтому слагаемое xm, где 0 m 2n+1 - 1, при раскрытии скобок в указанном произведении встречается ровно один раз.

21.26. Ясно, что (1 + x)2 1 + x2 (mod 2). Поэтому индукция по m поm m казывает, что (1 + x)2 1 + x2 (mod 2). Пусть n = 2m1 + 2m2 +... + 2md, 240 Глава 21. Системы счисления где 0 m1 < m2 <... < md. Тогда m1 m2 md (1 + x)n = (1 + x)2 (1 + x)2... (1 + x)m1 m2 md (1 + x2 )(1 + x2 )... (1 + x2 ) (mod 2).

Все члены, которые получаются при раскрытии скобок в последнем выражении, различны. Их количество равно 2d, причём коэффициент при каждом члене равен 1.

Pages:     | 1 |   ...   | 27 | 28 || 30 | 31 |   ...   | 65 |



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

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