WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 26 | 27 || 29 | 30 |   ...   | 65 |

20.15. Пусть вес самой лёгкой монеты равен a грамм, а вес самой тяжёлой монеты равен a + d - 1 грамм. Занумерует мешки числами 0, 1, 2,..., n - 1 и возьмём из мешка с номером i ровно di монет. Тогда если в мешке с номером i лежат монеты веса a + mi, то вес выбранных монет превышает вес такого же количества самых лёгких монет на m0+m1d+m2d2+...+mn-1dn-1. Это число можно узнать при помощи одного взвешивания. Кроме того, 0 mi d - 1.

Поэтому, записав полученное число в d-ичной системе счисления, мы узнаем все числа m0, m1,..., mn-1.

20.16. Положим на чашки весов по одному кубику. Возможны два случая.

Случай 1. При первом взвешивании один из кубиков оказался тяжелее.

В этом случае один выбранный кубик алюминиевый, а другой дюралевый. Положим выбранные кубики на одну чашку и будем с ними сравнивать остальные кубики. А именно, оставшиеся 18 кубиков разбиваем на 9 пар и поочерёдно кладём их на другую чашку. Каждый раз мы узнаём, сколько в паре дюралевых кубиков. Действительно, если эталонная пара легче, то мы положили два дюралевых кубика; если эталонная пара имеет тот же самый вес, то мы положили один алюминиевый и один дюралевый кубик; если эталонная пара тяжелее, то мы положили два алюминиевых кубика. Таким образом, в первом случае достаточно 10 взвешиваний.

Случай 2. При первом взвешивании кубики оказались равного веса.

В этом случае либо оба выбранных кубика алюминиевые, либо оба дюралевые. Положим выбранные кубики на одну чашку и будем последовательно Глава 20. Стратегии. Турниры. Таблицы сравнивать с ними остальные кубики. Пусть первые k пар оказались того же самого веса, а (k + 1)-я пара оказалась другого веса. (Если k = 9, то все кубики одного веса, поэтому дюралевых кубиков нет.) Пусть для определённости (k + 1)-я пара оказалась более тяжёлой. Тогда первые два кубика и кубики первых k пар алюминиевые. Положим на каждую чашку весов по одному кубику (k+1)-й пары. Если эти кубики одного веса, то они оба дюралевые. Если кубики разного веса, то один алюминиевый, а другой дюралевый. В обоих случаях мы можем составить пару кубиков, один из которых алюминиевый, а другой дюралевый. Оставшиеся пары кубиков мы можем сравнивать с этой парой, как и в первом случае. Общее число взвешиваний во втором случае равно 11.

20.17. а) Рассмотрим все n-значные числа в троичной системе счисления, за исключением чисел 00... 0, 11... 1 и 22... 2. Разобьём эти числа на пары так, чтобы сумма чисел в каждой паре была равна 22... 2. Каждой монете сопоставим одну из таких пар. Будем называть правым маркером монеты то из чисел соответствующей ей пары, для которого первая пара неравных цифр это 01, 12 или 20. Другое число будем называть левым маркером. Для него первая пара неравных цифр это 21, 10 или 02.

При k-м взвешивании положим на одну чашку весов те монеты, у которых k-й разряд правого маркера равен 0, а на вторую чашку те монеты, у которых k-й разряд правого маркера равен 2. Если перевесит первая чашка, то положим ak = 0; если перевесит вторая чашка, то положим ak = 2; если чашки уравновесятся, то положим ak = 1. Покажем, что тогда a1a2... an маркер фальшивой монеты, причём он левый, если фальшивая монета легче настоящей, и правый, если фальшивая монета тяжелее.

Прежде всего заметим, что на каждую чашку весов кладётся одинаковое число монет; более того, монет, у которых k-й разряд правого маркера равен 0, 1, 2, одинаковое число. Чтобы это доказать, нужно рассмотреть циклическую перестановку цифр 0 1 2 0; при такой замене цифр каждый правый маркер переходит в некоторый другой правый маркер, и в результате правые маркеры разбиваются на тройки.

Предположим, что k-й разряд правого маркера фальшивой монеты равен 1. Тогда на обеих чашках весов при k-м взвешивании лежат настоящие монеты, поэтому ak = 1. Именно так и должно быть (k-й разряд левого маркера тоже равен 1).

Предположим, что k-й разряд правого маркера фальшивой монеты равен 0. Тогда при k-м взвешивании фальшивая монета лежит на первой чашке весов. Если фальшивая монета тяжелее настоящей, то ak = 0 (k-й разряд правого маркера тоже равен 0). Если фальшивая монета легче настоящей, то ak = 2 (k-й разряд левого маркера тоже равен 2). Случай, когда k-й разряд правого маркера фальшивой монеты равен 2, разбирается аналогично.

б) Основная трудность, которая возникает в случае, когда количество монет меньше (3n - 3), связана с тем, что если мы применим ту же самую систему взвешиваний, то на одной чашке весов может оказаться меньше монет, 228 Глава 20. Стратегии. Турниры. Таблицы чем на другой. Чтобы преодолеть эту трудность, воспользуемся разбиением правых маркеров на тройки, которое возникает при циклической перестановке цифр 0 1 2 0. Кроме того, выделим тройку правых маркеров 00... 01, 11... 12 и 22... 20. Эти маркеры мы не будем использовать до тех пор, пока это возможно.

Будем разбивать монеты на тройки до тех пор, пока это возможно. Каждой тройке монет сопоставим тройку правых маркеров (и соответствующих им левых маркеров); при этом выделенную тройку маркеров мы не используем. Если остаётся одна монета, то ей сопоставляем маркер 11... 12, а если остаются две монеты, то им сопоставляем маркеры 00... 01 и 22... 20.

Для первых n-1 взвешиваний можно применить прежние правила. Более того, если количество монет делится на 3, то последнее взвешивание тоже можно сделать по прежним правилам.

Предположим, что осталась одна монета с маркером 11... 12. Тогда если после первых n - 1 взвешиваний получается число, отличное от 11... 1, то ясно, что монета с маркером 11... 12 не фальшивая. В таком случае последнее взвешивание производится без учёта этой монеты. Если же получилось число 11... 1, то под подозрением остаются только монеты с маркерами 11... 10 и 11... 12. Но это маркеры одной и той же монеты (левый и правый). Итак, фальшивая монета известна. Теперь за одно взвешивание её можно сравнить с настоящей и выяснить, какая из них легче.

Предположим, что остались две монеты с правыми маркерами 00... 01 и 22... 20; им соответствуют левые маркеры 22... 21 и 00... 02. Если после первых n - 1 взвешиваний получается число, отличное от 00... 0 и 22... 2, то фальшивая монета отлична от двух выделенных монет. Поэтому последнее взвешивание можно сделать без них. Если же после n - 1 взвешиваний получается число 00... 0 или 22... 2, то мы знаем, что фальшивая монета одна из двух выделенных, причём мы знаем, какая из выделенных монет легче.

Сравнив одну из этих монет с настоящей, мы узнаем, какая монета фальшивая, и узнаем, легче она настоящей или тяжелее.

20.18. а) П е р в о е р е ш е н и е. Пусть x1,..., xn суммы чисел в строках, y1,..., ym суммы чисел в столбцах. На пересечении i-й строки и j-го столбца стоит число xiyj. Поэтому сумма чисел в i-й строке равна xiy1 + + xiy2 +... + xiym. С другой стороны, эта сумма равна xi. Таким образом, xi = xi(y1 + y2 +... + ym). Число xi положительно; в частности, оно отлично от нуля, поэтому y1 + y2 +... + ym = 1. Но сумма y1 + y2 +... + ym это как раз и есть сумма всех чисел в таблице.

В т о р о е р е ш е н и е. Пусть aij стоящее на пересечении i-й стро число, m ки и j-го столбца. По условию aij = aip n aqj. Следовательно, p=1 q= m aij = aip n aqj = aij. Для числа S = aij i,j i,j p=1 q=1 i,j i,j мы получили уравнение S2 = S. Но S > 0, поэтому S = 1.

б) Пусть x1,..., xn суммы чисел в строках, y1,..., ym суммы чисел в столбцах. На пересечении i-й строки и j-го столбца стоит число xiyj. Поэтому Глава 20. Стратегии. Турниры. Таблицы сумма чисел в i-й строке равна xiy1 + xiy2 +... + +xiym. С другой стороны, эта сумма равна xi. Таким образом, xi = xi(y1 + y2 +... + ym). Сумма y1 + + y2 +... + ym это как раз сумма всех чисел в таблице. Если она не равна 1, то xi = 0. Аналогично доказывается, что в таком случае все числа x1,..., xn, y1,..., ym равны 0. Но тогда и все числа xiyj тоже равны 0.

20.19. Таблица симметрична относительно диагонали, поэтому каждому числу, расположенному вне диагонали, соответствует равное ему число на симметричном месте. Значит, вне диагонали расположено чётное число единиц, чётное число двоек и т.д. По условию в каждой строке встречаются все числа от 1 до n. Поэтому в каждой строке любое число от 1 до n встречается ровно один раз, а всего в таблице оно встречается ровно n раз. Число n нечётно, поэтому каждое число от 1 до n встречается на диагонали нечётное число раз; в частности, каждое число от 1 до n встречается на диагонали по крайней мере один раз. Но на диагонали всего n мест, поэтому каждое число от 1 до n встречается на диагонали ровно один раз.

20.20. а) Предположим, что сумма чисел в некотором столбце равна S 1035. Рассмотрим строку, симметричную этому столбцу относительно выделенной диагонали. Сумма чисел в этой строке тоже равна S, а сумма всех чисел, стоящих в этом столбце и этой строке, равна 2S -s, где s число, стоящее на их пересечении. Число s стоит на выделенной диагонали, поэтому s 112. Следовательно, 2S - s 2 · 1035 - 112 = 1958 > 1956. Приходим к противоречию.

б) Предположим, что сумма чисел в некоторой строке равна S 518.

Рассмотрим два столбца, симметричных этой строке относительно двух диагоналей, и ещё строку, симметричную этим столбцам. Таблица состоит из чётного числа строк и чётного числа столбцов, поэтому мы получим два разных столбца и две разных строки. На пересечениях этих строк и столбцов стоят 4 числа, сумма которых равна s 112. Сумма всех чисел, стоящих в этих двух строках и двух столбцах равна 4S - s 4 · 518 - 112 = 1960 > 1956.

Приходим к противоречию.

k(k2 + 1) 20.21. О т в е т:.

Запишем данную таблицу в виде k · 0 + 1, k · 0 + 2,..., k · 0 + k, k · 1 + 1, k · 1 + 2,..., k · 1 + k,............

(k - 1)k + 1, (k - 1)k + 2,..., (k - 1)k + k.

Каждое число таблицы представлено в виде ka + b, где 0 a k - 1 и 1 b k. Будем отдельно суммировать слагаемые ka и слагаемые b. Из каждой строки выписано в точности одно число, поэтому будут присутствовать слагаемые ka для каждого a = 0, 1,..., k -1. Из каждого столбца выписано в точности одно число, поэтому будут присутствовать слагаемые b для каждого 230 Глава 20. Стратегии. Турниры. Таблицы b = 1, 2,..., k. Таким образом, искомая сумма равна k(k - 1) k(k + 1) k(k2 + 1) k 0 + 1 + 2 +... + (k - 1) + (1 + 2 +... + k) = k · + =.

2 2 Глава 21.

Системы счисления 21.1. Последние цифры 21.1. Найдите все трёхзначные числа, любая натуральная степень которых оканчивается на три цифры, составляющие исходное число (в том же порядке).

21.2. а) Докажите, что для любого натурального n существуют ровно два натуральных n-значных1 числа an и bn (отличных от 00... 0 и 0... 01), для которых a2 оканчивается на an, а b2 оканчивается на bn.

n n б) Докажите, что an + bn = 10n + 1.

в) Пусть числа an и an+1 оканчиваются на одну и ту же цифру.

Докажите, что тогда an+1 оканчивается на an, а bn+1 оканчивается на bn.

г) Докажите, что если an+1 и an оканчиваются на 5, то an+1 это последние n + 1 цифр числа a2, а если bn+1 и bn оканчиваются на 6, то n bn+1 это последние n + 1 цифр числа b5.

n 21.2. Первые цифры 21.3. Числа 2n и 5n начинаются с цифры a. Чему равно a 21.4. а) Докажите, что число 2n может начинаться с любого набора цифр.

Первыми цифрами могут быть и нули, т.е. требуется лишь, чтобы выполнялось неравенство an, bn 10n - 1.

232 Глава 21. Системы счисления б) Докажите, что число 0, 12481632... (подряд записываются степени двойки) иррационально.

21.5. Докажите, что квадрат целого числа может начинаться с любого набора цифр.

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

21.3. Другие цифры 21.6. Докажите, что предпоследняя цифра числа 3n при любом n > 2 чётна.

21.7. Пусть a и b последняя и предпоследняя цифры числа 2n.

Докажите, что если n > 3, то ab делится на 6.

21.8. Пусть a1, a2,... различные натуральные числа, в десятичной записи которых не встречается цифра 1. Докажите, что среди чисел an/n есть сколь угодно большие числа.

21.4. Сумма цифр 21.9. Пусть a 2 натуральное число, которое не делится ни на 2, ни на 5. Докажите, что сумма цифр числа am при достаточно большом m может быть сколь угодно велика.

21.10. Докажите, что сумма цифр числа 2n может быть сколь угодно велика.

21.11. Пусть P (x) многочлен с натуральными коэффициентами, an сумма цифр числа P (n). Докажите, что некоторое число встречается в последовательности a1, a2, a3,... бесконечно много раз.

21.5. Разные задачи о десятичной записи 21.12. Найдите четырёхзначное число, которое является точным квадратом и у которого две первые цифры одинаковые и две последние тоже.

21.13. Числа 2n и 5n (в десятичной записи) записаны одно за другим. Сколько цифр имеет полученное число 21.14. Докажите, что любое положительное число a можно представить в виде суммы девяти чисел, десятичные записи которых содержат только цифры 0 и k, где k фиксированная цифра, отличная от нуля.

Глава 21. Системы счисления 21.15. Найдите все трёхзначные числа, равные сумме факториалов своих цифр.

21.16. Все целые числа выписаны подряд, начиная с единицы. Какая цифра стоит на 206 788-м месте 21.6. Периоды десятичных дробей и репьюниты Пусть p простое число, отличное от 2 и 5. Длиной периода числа p называют количество цифр в периоде десятичной записи дроби 1/p.

21.17. Пусть n натуральное число, не превосходящее p - 1. Докажите, что количество цифр в периоде десятичной записи числа n/p равно длине периода числа p.

21.18. Докажите, что длина периода числа p является делителем числа p - 1.

21.19. Периоды правильных дробей со знаменателем 7 получаются друг из друга циклической перестановкой:

1/7 = 0, (142857) 3/7 = 0, (428571) 2/7 = 0, (285714) 6/7 = 0, (857142) 4/7 = 0, (571428) 5/7 = 0, (714285) Докажите, что таким же свойством обладают все простые числа p, у которых длина периода равна p - 1.

21.20. Период дроби 1/7 = 0, (142857) обладает следующим свойством: 142 + 857 = 999. Докажите, что аналогичным свойством обладает период дроби 1/p для любого простого числа p, у которого длина периода равна p - 1.

* * * Репьюнитом называют натуральное число вида 111... 111, т.е. натуральное число, в десятичной записи которого встречаются только единицы.

21.21. Докажите, что длина периода простого числа p = 3 равна числу единиц в наименьшем репьюните, делящемся на p.

21.22. Пусть p 7 простое число. Докажите, что число 111... p-делится на p.

234 Глава 21. Системы счисления 21.7. Определение d-ичной записи числа 21.23. Пусть d > 1 натуральное число. Докажите, что любое натуральное число n единственным образом представляется в виде n = = a0 + a1d + a2d2 +... + akdk, где 0 ai d - 1 целые числа, причём ak = 0.

Pages:     | 1 |   ...   | 26 | 27 || 29 | 30 |   ...   | 65 |



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

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