Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
20.8. Общее количество выигрышей равно общему количеству проигрышей. Каждая команда сыграла 7 матчей. Поэтому среднее количество выигрышей равно 3,5. Значит, есть команда a 1 , выигравшая по крайней мере у четырёх команд. Для этих четырёх команд среднее число выигрышей в их матчах друг с другом равно. Поэтому есть команда a 2 , которая выиграла по крайней мере у двух команд и a 4 (a 3 — это та команда, которая выиграла у другой. Ответ да, могло. Чтобы построить соответствующий пример, рассмотрим три вида турниров со следующими турнир Решения задач 249 ными таблицами: Выигрыши Ничьи Проигрыши Очки Алик 0 4 0 Боря 2 1 Вася 2 1 2 Выигрыши Ничьи Проигрыши Очки Алик 1 2 1 Боря 2 1 Вася 4 0 2 Выигрыши Ничьи Проигрыши Очки Алик 0 1 1 Боря 1 1 Вася 0 0 Пусть было сыграно a турниров первого вида, b — второго — третьего. Тогда у Алика b + c проигрышей, у Бори и Васи+ b + c и a проигрышей. У Бори a + b выигрышей, у Алика и Васи и a + 2c выигрышей. У Васи 2(a + b + c) очков, у Алика и Бори по 2a + 2b + c/2 очков. Поэтому должны выполняться неравенства > b + c, b > 2c и c > 0. Например, можно взять c = 1, b = 3 и a = 5. 20.10. а) Ответили. Пусть x — число восьмиклассников число очков, набранных каждым восьмиклассником. Подсчитывая двумя способами сумму очков, набранных всеми участниками турнира, приходим к уравнению+ 8 = (x + 2)(x + те Поэтому x принимает одно из значений 1, 2, 7, 14. Значения 1 и отпадают, поскольку в этих случаях число y будет отрицательным. Задача имеет два ответа x = 7 и x = б) Ответ. Пусть в турнире участвовало x девятиклассников. Тогда всего было 11x участников и они набрали − 1) 2 Глава 20. Стратегии. Турниры. Таблицы очков. По условию отношение числа очков, набранных девятиклассниками, к числу очков, набранных десятиклассниками, равно. Поэтому девятиклассники набрали x(11x − 1) очков, а значит, каждый из девятиклассников выиграл все 11x − 1 партий, которые он сыграл. Но если бы среди участников турнира было два девятиклассника, то партию между собой они должны были оба выиграть, что невозможно. Поэтому в турнире участвовал один девятиклассник он набрал 10 очков. Применим индукцию по n. Для n = 1 утверждение очевидно. Предположим, что 2 n −1 боксёров можно упорядочить задней. Докажем, что тогда 2 n боксёров можно упорядочить задней. Разобьём боксёров на две группы X и по человек. Сначала будут происходить бои только между боксёрами из одной и той же группы. По предположению индукции задней в каждой из этих групп боксёров можно упорядочить X 1 < . . . < и Y 1 < . . . < Y N , где N = Теперь нужно задней повести поединки между боксёрами из разных групп и упорядочить всех боксёров. Это мы тоже будем делать по индукции. При n = 1 утверждение очевидно. Сделаем теперь шаг индукции. Возьмём «нечёт- ную» группу X 1 , X 3 , . . . , Y 1 , Y 3 , . . . и «чётную» группу X 2 , X 4 , . . . , Y 2 , Y 4 , . . . По предположению индукции задней можно упорядочить боксёров в каждой из этих групп (каждая группа состоит из двух уже упорядоченных меньших групп. Пусть. Тогда боксёра нужно сравнить с Y j . Но это сравнение необходимо лишь во том случае, когда Поэтому те пары боксёров {X i , Y j }, между которыми необходимо провести бой, определены так, что ни один из боксёров не входит в две группы. Занумеруем мешки и возьмём из каждого мешка столько монет, каков его номер. Взвесим все эти монеты. Их вес меньше веса такого же количества настоящих монет настолько же граммов, каков номер мешка с фальшивыми монетами. Возьмём 18 монет и положим половину из них на одну чашку весов, а другую половину на другую чашку. Если одна группа монет окажется легче, то фальшивая монета входит в эту группу. Если же чашки весов уравновесятся, то фальшивая монета находится среди восьми оставшихся монет. После первого взвешивания у нас осталось 8 или 9 подозрительных монет. Возьмём из них 6 монет и половину положим на одну чашку весов, половину на другую. После этого останется две или три подозрительных монеты. Положив на обе чашки весов по од Решения задач 251 ной подозрительной монете, мы сможем выяснить, какая монета фальшивая. Отложим выбранную монету и положим половину оставшихся монет на одну чашку весов, а другую половину — на другую чашку. Пусть среди первых n монет есть фальшивых, а среди других n монет есть фальшивых. Тогда на первой чашке лежит груз весом na ± k 1 , где a — вес настоящей монеты, а на второй чашке лежит груз весом na ± k 2 . Стрелка весов покажет разность k 2 ≡ k 1 + k 2 (mod 2). Таким образом, если выбранная монета фальшивая, то показание стрелки весов — нечётное число, а если выбранная монета настоящая, то показание стрелки весов — чёт- ное число. Пусть вес самой лёгкой монеты равен a грамма вес самой тяжёлой монеты равен a + d − 1 грамм. Занумерует мешки числами 0, 1, 2, . . . , n − 1 и возьмём из мешка с номером ровно монет. Тогда если в мешке с номером i лежат монеты веса a + m i , то вес выбранных монет превышает вес такого же количества самых лёгких монет на m 0 +m 1 d +m 2 d 2 +. . Это число можно узнать при помощи одного взвешивания. Кроме того, 0 6 m i 6 d − 1. Поэтому, записав полученное число в d-ичной системе счисления, мы узнаем все числа m 0 , m 1 , . . . , m n −1 20.16. Положим на чашки весов по одному кубику. Возможны два случая. С луча й 1. При первом взвешивании один из кубиков оказался тяжелее. В этом случае один выбранный кубик алюминиевый, а другой дюралевый. Положим выбранные кубики на одну чашку и будем сними сравнивать остальные кубики. А именно, оставшиеся кубиков разбиваем на 9 пари поочерёдно кладём их на другую чашку. Каждый раз мы узнаём, сколько в паре дюралевых кубиков. Действительно, если эталонная пара легче, то мы положили два дюралевых кубика если эталонная пара имеет тот же самый вес, то мы положили один алюминиевый и один дюралевый кубик; если эталонная пара тяжелее, то мы положили два алюминиевых кубика. Таким образом, в первом случае достаточно 10 взвеши- ваний. С луча й 2. При первом взвешивании кубики оказались равного веса. В этом случае либо оба выбранных кубика алюминиевые, либо оба дюралевые. Положим выбранные кубики на одну чашку и будем последовательно сравнивать сними остальные кубики. Пусть первые k пар оказались того же самого веса, а (k + я Глава 20. Стратегии. Турниры. Таблицы пара оказалась другого веса. (Если k = 9, то все кубики одного веса, поэтому дюралевых кубиков нет) Пусть для определённости (k + я пара оказалась более тяжёлой. Тогда первые два кубика и кубики первых k пар алюминиевые. Положим на каждую чашку весов по одному кубику (k + й пары. Если эти кубики одного веса, то они оба дюралевые. Если кубики разного веса, то один алюминиевый, а другой дюралевый. В обоих случаях мы можем составить пару кубиков, один из которых алюминиевый, а другой дюралевый. Оставшиеся пары кубиков мы можем сравнивать с этой парой, как ив первом случае. Общее число взвешиваний во втором случае равно 11. 20.17. а) Рассмотрим все n-значные числа в троичной системе счисления, за исключением чисел 00 . . . 0, 11 . . . 1 и 22 . . . 2. Разо- бьём эти числа на пары так, чтобы сумма чисел в каждой паре была равна 22 . . . 2. Каждой монете сопоставим одну из таких пар. Будем называть правым маркером монеты то из чисел соответствующей ей пары, для которого первая пара неравных цифр — это, 12 или 20. Другое число будем называть левым маркером. Для него первая пара неравных цифр — это 21, 10 или Прим взвешивании положим на одну чашку весов те монеты, у которых й разряд правого маркера равен 0, а на вторую чашку те монеты, у которых й разряд правого маркера равен Если перевесит первая чашка, то положим a k = 0; если перевесит вторая чашка, то положим a k = 2; если чашки уравновесятся, то положим a k = 1. Покажем, что тогда a 1 a 2 . . . a n — маркер фальшивой монеты, причём он левый, если фальшивая монета легче настоящей, и правый, если фальшивая монета тяжелее. Прежде всего заметим, что на каждую чашку весов кладёт- ся одинаковое число монет более того, монету которых й разряд правого маркера равен 0, 1, 2, одинаковое число. Чтобы это доказать, нужно рассмотреть циклическую перестановку цифр при такой замене цифр каждый правый маркер переходит в некоторый другой правый маркер, ив результате правые маркеры разбиваются на тройки. Предположим, что й разряд правого маркера фальшивой монеты равен 1. Тогда на обеих чашках весов прим взвешивании лежат настоящие монеты, поэтому a k = 1. Именно таки должно быть (й разряд левого маркера тоже равен Предположим, что й разряд правого маркера фальшивой монеты равен 0. Тогда прим взвешивании фальшивая монета лежит на первой чашке весов. Если фальшивая монета тяжелее настоящей, той разряд правого маркера тоже равен 0). Решения задач 253 Если фальшивая монета легче настоящей, той разряд левого маркера тоже равен 2). Случай, когда й разряд правого маркера фальшивой монеты равен 2, разбирается аналогично. б) Основная трудность, которая возникает в случае, когда количество монет меньше 2 (3 n − 3), связана стем, что если мы применим туже самую систему взвешиваний, тона одной чашке весов может оказаться меньше монет, чем на другой. Чтобы преодолеть эту трудность, воспользуемся разбиением правых маркеров на тройки, которое возникает при циклической перестановке цифр 0 → 1 → 2 → 0. Кроме того, выделим тройку правых маркеров . . . 01, 11 . . . 12 и 22 . . . 20. Эти маркеры мы не будем использовать до тех пор, пока это возможно. Будем разбивать монеты на тройки до тех пор, пока это возможно. Каждой тройке монет сопоставим тройку правых маркеров (и соответствующих им левых маркеров при этом выделенную тройку маркеров мы не используем. Если остаётся одна монета, то ей сопоставляем маркера если остаются две монеты, то им сопоставляем маркеры 00 . . . 01 и 22 . . . Для первых n −1 взвешиваний можно применить прежние правила. Более того, если количество монет делится на 3, то последнее взвешивание тоже можно сделать по прежним правилам. Предположим, что осталась одна монета с маркером 11 . . . Тогда если после первых n − 1 взвешиваний получается число, отличное от 11 . . . 1, то ясно, что монета с маркером 11 . . . 12 не фальшивая. В таком случае последнее взвешивание производится без учёта этой монеты. Если же получилось число 11 . . . 1, то под подозрением остаются только монеты с маркерами 11 . . . и 11 . . . 12. Но это — маркеры одной и той же монеты (левый и правый. Итак, фальшивая монета известна. Теперь заодно взвешивание её можно сравнить с настоящей и выяснить, какая из них легче. Предположим, что остались две монеты с правыми маркерами и 22 . . . 20; им соответствуют левые маркеры 22 . . . и 00 . . . 02. Если после первых n−1 взвешиваний получается число, отличное от 00 . . . 0 и 22 . . . 2, то фальшивая монета отлична от двух выделенных монет. Поэтому последнее взвешивание можно сделать без них. Если же после n − 1 взвешиваний получается число . . . 0 или 22 . . . 2, то мы знаем, что фальшивая монета — одна из двух выделенных, причём мы знаем, какая из выделенных монет легче. Сравнив одну из этих монет с настоящей, мы узнаем, какая монета фальшивая, и узнаем, легче она настоящей или тяжелее Глава 20. Стратегии. Турниры. Таблицы. а) Первое решение. Пусть x 1 , . . . , x n — суммы чисел в строках, y 1 , . . . , y m — суммы чисел в столбцах. На пересечении й строки иго столбца стоит число x i y j . Поэтому сумма чисел в й строке равна x i y 1 + x i y 2 + . . . + x i y m . С другой стороны, эта сумма равна x i . Таким образом, x i = x i (y 1 + y 2 + . . . + y m ). Число положительно в частности, оно отлично от нуля, поэтому+ y 2 + . . . + y m = 1. Но сумма y 1 + y 2 + . . . + это как рази есть сумма всех чисел в таблице. В тор о ере ш е ни е. Пусть a ij — число, стоящее на пересечении й строки иго столбца. По условию Следовательно. Для числа S = P i,j a ij мы получили уравнение S 2 = S. Но S > 0, поэтому S = б) Пусть x 1 , . . . , x n — суммы чисел в строках, y 1 , . . . , y m — суммы чисел в столбцах. На пересечении й строки иго столбца стоит число x i y j . Поэтому сумма чисел в й строке равна+ x i y 2 + . . . + +x i y m . С другой стороны, эта сумма равна Таким образом, x i =x i (y 1 +y 2 +. . .+y m ). Сумма y 1 +y 2 +. . .+y m — это как раз сумма всех чисел в таблице. Если она неравна, то x i = Аналогично доказывается, что в таком случае все числа x 1 , . . . , x n , y 1 , . . . , равны 0. Но тогда и все числа тоже равны 0. 20.19. Таблица симметрична относительно диагонали, поэтому каждому числу, расположенному вне диагонали, соответствует равное ему число на симметричном месте. Значит, вне диагонали расположено чётное число единиц, чётное число двоек и т. д. По условию в каждой строке встречаются все числа от 1 до n. Поэтому в каждой строке любое число от 1 до n встречается ровно один раза всего в таблице оно встречается ровно n раз. Число n нечётно, поэтому каждое число от 1 до n встречается на диагонали нечёт- ное число разв частности, каждое число от 1 до n встречается на диагонали по крайней мере один раз. Нона диагонали всего мест, поэтому каждое число от 1 до n встречается на диагонали ровно один раза) Предположим, что сумма чисел в некотором столбце равна S > 1035. Рассмотрим строку, симметричную этому столбцу относительно выделенной диагонали. Сумма чисел в этой строке тоже равна S, а сумма всех чисел, стоящих в этом столбце и этой строке, равна 2S − s, где s — число, стоящее на их пересечении. Число s стоит на выделенной диагонали, поэтому s 6 112. Решения задач 255 Следовательно, 2S − s > 2 · 1035 − 112 = 1958 > 1956. Приходим к противоречию. б) Предположим, что сумма чисел в некоторой строке равна > 518. Рассмотрим два столбца, симметричных этой строке относительно двух диагоналей, и ещё строку, симметричную этим столбцам. Таблица состоит из чётного числа строки чётного числа столбцов, поэтому мы получим два разных столбца и две разных строки. На пересечениях этих строки столбцов стоят 4 числа, сумма которых равна s 6 112. Сумма всех чисел, стоящих в этих двух строках и двух столбцах равна 4S − s > 4 · 518 − 112 = 1960 > Приходим к противоречию. Отв е т: k(k 2 + 1) 2 Запишем данную таблицу в виде · 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 + Каждое число таблицы представлено в виде ka + b, где 0 6 a 6 k − и 1 6 b 6 k. Будем отдельно суммировать слагаемые ka и слагаемые. Из каждой строки выписано в точности одно число, поэтому будут присутствовать слагаемые ka для каждого a = 0, 1, . . . , k − Из каждого столбца выписано в точности одно число, поэтому будут присутствовать слагаемые b для каждого b = 1, 2, . . . , k. Таким образом, искомая сумма равна. . .+(k−1))+(1+2+. . .+k)=k· k(k −1) 2 + k(k+1) 2 = k(k 2 + 1) 2 ГЛАВА СИСТЕМЫ СЧИСЛЕНИЯ. Последние цифры. Найдите все трёхзначные числа, любая натуральная степень которых оканчивается натри цифры, составляющие исходное число (в том же порядке. а) Докажите, что для любого натурального n существуют ровно два натуральных n-значных* числа и отличных от 00 . . . 0 и 0 . . . 01), для которых оканчивается на a n , а оканчивается наб) Докажите, что a n + b n = 10 n + в) Пусть числа и оканчиваются на одну и туже цифру. Докажите, что тогда оканчивается на a n , а оканчивается наг) Докажите, что если и оканчиваются на 5, то это последние n + 1 цифр числа a 2 n , а если и оканчиваются на 6, то b n+1 — это последние n + 1 цифр числа. Первые цифры. Числа и начинаются с цифры a. Чему равно. а) Докажите, что число может начинаться с любого набора цифр Первыми цифрами могут быть и нули, те. требуется лишь, чтобы выполнялось неравенство a n , b n 6 10 n − 1. Условия задач 257 б) Докажите, что число 0,12481632 . . . подряд записываются степени двойки) иррационально. Докажите, что квадрат целого числа может начинаться с любого набора цифр. См. также задачу 25.35. |