Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
В каких моментах решения задача) и 2 а) использовалась конечность множества? Во всех задачах 3–7 ответ на вопрос положителен. Как ив задачах б, 2 б, объект, существование которого требуется доказать, можно конструировать за счетное число шагов. Предположим, что после го шага построено множество K n . Нам шаге множество достраивается до множества K n+1 ⊃ K n . Искомой конструкцией является множество K Ниже используется тот факт, что для счетных множеств A i множество те. множество упорядоченных наборов, a 2 , . . . , a k ), a i ∈ A i ), счетно. Занумеруем клетки произвольным образом. Расставляем числа, 2, 3, . . . по порядку, руководствуясь следующим правилом. Напер- вом шаге поставим число 1 в клетку с номером 1. Пусть после n шагов уже расставлены числа 1, 2, . . . , n и пусть k — минимальный номер клет- Конечное и счетное 343 ки, в которой еще нет числа. Поставим число n + 1 в клетку с номером k, если n + 1 просто. В противном случае поставим n + 1 в любую такую клетку, что в ее строке и столбце еще не расставлено чисел. Через несколько шагов клетка с номером k будет занята, так как простых чисел бесконечно много. Занумеруем произвольным образом все бесконечные арифметические прогрессии, состоящие из натуральных чисел (множество прогрессий счетно, так как прогрессия определяется первым членом и разностью. Положим A = {a 1 , a 2 , . . .}, где числа a 1 , a 2 , . . . определяются следующим образом. Пусть a 1 — любое число из прогрессии с номером Если a уже определено, то возьмем a из прогрессии с номером n + так, чтобы выполнялось неравенство a n+1 > 2a n . Легко видеть, что множества и B = N \ A удовлетворяют условию. Опишем построение последовательности M = {a 1 , a 2 , . . .}, для которой наборы M k = {a 1 , a 2 , . . . , a 2k }, k = 1, 2, . . . , удовлетворяют условиям) a 1 < a 2 < . . . < a 2k ; 2) все разности вида r ij = a j − a для 1 6 i < j 6 2k различны) множество R k = {r ij | 1 6 i < j 6 2k} содержит числа 1, 2, . . . , Это даст нам нужный пример. Положим a 1 = 1, a 2 = 2, те, и для условия 1)– 3) выполнены. Пусть уже построено M k = {a 1 , a 2 , . . . , a 2k }, для которого условия 3) выполнены. Если k + 1 / ∈ R k , то положим a 2k+1 = 2a 2k , a 2k+2 = = 2a 2k + k + 1. Если k + 1 ∈ R k , то положим a 2k+1 = 2a 2k , a 2k+2 = Нетрудно показать, что для M k+1 = {a 1 , a 2 , . . . , a 2k+2 } условия выполнены. Занумеруем прямые, содержащие бесконечное множество целочисленных точек. Занумеруем ненулевые целочисленные векторы. На первом шаге покрасим первую прямую периодично, используя 2007 цветов. Нам) шаге покрасим периодичною прямую, (это возможно, так как до го шага на ней покрашено конечное число точек), а затем найдем две еще не покрашенные точки, отстоящие на вектор с номером i − 1, и окрасим их в разные цвета. Из определения процедуры вытекает, что окраска каждой прямой периодична, но окраска плоскости непериодична, так как раскраска не совмещается сдвигом ни на какой целочисленный вектор. Опишем построение нужной функции f. Занумеруем рациональные числа q 1 , q 2 , . . . На первом шаге положим f (q 1 , y) = f (x, q 1 ) = 0 для всех x, y ∈ Q. Нам) шаге будем задавать значения f(x, y) на прямых и y = q i . Перед м шагом уже определены значения функ- Гл. 13. Алгоритмы, конструкции, инварианты ции f лишь в конечном числе точек прямой x = q а именно в точках i , q 1 ), (q i , q 2 ), . . . , (q i , q i−1 )). Подберем такой многочлен g i (y) степени больше i, что g i (q k ) = f (q i , q k ) для k = 1, 2, . . . , i − 1 (такой многочлен найдется это можно доказать, например, с использованием интерполяционного многочлена Лагранжа, и положим f(q i , y) = g i (y). Далее, положим f (x, q i ) = h i (x), где h i (x) — такой многочлен степени больше что h i (q k ) = f (q k , q i ) для k = 1, 2, . . . , i. Этим завершается й шаг по- строения. Если бы функция f (x, y), полученная в результате такого построения, была многочленом от двух переменных, то степени многочленов f (x, q i ) (i = 1, 2, . . .) были бы ограничены, что неверно. Другой взгляд на задачи 1, 2 1. Пусть M — некоторое подмножество натурального ряда. Рассмотрим последовательность q n = k(n) n , где k(n) — количество чисел множества среди чисел 1, 2, . . . , n. Если существует предел Q = lim n→∞ q то назовем Q мерой подмножества M , Q = µ(M ). (Конечно, это понятие отличается от классического определения меры, скажем, тем, что объединение двух измеримых множеств, те. множеств, для которых определена мера, необязательно измеримо) В некотором смысле, мера) представляет собой вероятность того, что случайно выбранное натуральное число будет числом из множества M . Легко заметить, что) = 1, мера конечного множества равна 0, мера бесконечной арифметической прогрессии с разностью d равна 1/d. (Покажите, что существуют неизмеримые подмножества найдите меру множества точных квадратов, множества простых чисел и т. д) Нетрудно доказать, что мера µ аддитивна, те. для измеримых непересекающихся подмножеств и B, множество A ∪ B измеримо, причем µ(A ∪ B) = µ(A) + µ(B). Из аддитивности меры µ вытекает равенство из задачи 1 а. Однако, мера не является аддитивной, те. для попарно непересекающихся измеримых подмножеств A 1 , A 2 , . . . равенство µ ∞ S i=1 A i = ∞ P i=1 µ(A i ) выполнено не всегда (и вообще может не быть измеримым например, N объединение множеств, состоящих из одного числа. Пример из задачи б) также доказывает отсутствие аддитивности меры µ. 2. Аналогично изложенному выше можно попытаться определить меру для некоторых подмножеств M плоскости. Пусть q R = S R πR 2 , где площадь (кстати, что такое площадь) множества M ∩ круг радиуса R с центром вначале координат. Если существует пре- Игры 345 дел Q = lim R→+∞ q R , то назовем Q мерой подмножества M , Q = µ(M В некотором смысле мера µ(M ) представляет собой вероятность того, что случайно выбранная точка плоскости будет точкой из множества . Легко заметить, что мера всей плоскости равна 1, мера ограниченного подмножества плоскости множества равна 0, мера внутренности угла величины равна α/360. (Покажите, что существуют неизмеримые подмножества изменится ли понятие измеримости и мера, если изменить начало координат, если C R — не круги, а, скажем, квадраты + |y| 6 R?) Как ив задаче 1, мера µ оказывается аддитивной, ноне является аддитивной. Подумайте, как получить из этих соображений другое решение задачи Игры (ДА. Пермяков, М. Б. Скопенков, А. В. Шаповалов 1. Симметрия, передача хода и дерево позиций (ДА. Пермяков, М. Б. Скопенков Целью данного цикла задач является знакомство с некоторыми красивыми идеями теории игр. Для решения задач данного раздела полезно знакомство с инвариантами, поскольку на них основаны многие стратегии в играх (пример инварианта — симметричность позиции. Поэтому может быть полезно прорешать сначала задачи раздела Инвариант Довольно часто в задачах элементарной теории игр встречаются следующие идеи. Проиллюстрируем их на конкретных примерах. Симметричная стратегия (а также ее обобщение — дополняющая стратегия. Двое по очереди выкладывают доминошки на доску × 9. Каждая доминошка покрывает ровно две клетки доски, каждая клетка может быть покрыта не более чем одной доминошкой. Проигрывает тот игрок, который не может положить очередную доминошку. Кто выигрывает при правильной игре Как он должен для этого играть. Передача хода. В двухходовых шахматах фигуры ходят по обычным правилам, только за каждый ход разрешается сделать ровно два хода одной фигурой. Цель игры — съесть короля соперника. Докажите, что белые в двухходовых шахматах могут играть так, что заведомо не проиграют (те. либо выиграют, либо сыграют вничью. Дерево позиций (ставь на минус. Ферзь стоит на Двое по очереди ходят им по направлению вверх, вправо или вправо- вверх. Выигрывает тот, кто поставит его на h8. Кто выигрывает при правильной игре и как он должен для этого играть Гл. 13. Алгоритмы, конструкции, инварианты В следующих задачах необходимо выяснить, кто из игроков может выиграть, как бы хорошо ни играл противник. В соседних углах доски 9 × 9 стоят черная и белая ладьи, остальные клетки заняты серыми пешками. Два игрока ходят по очереди, каждый своей ладьей, причем каждым ходом нужно съесть либо серую пешку, либо ладью противника. Проигрывает тот, кто не может сделать ход. На шахматной доске стоит король. Двое по очереди ходят им. Проигрывает игрок, после хода которого король оказывается в клетке, в которой побывал ранее. На одном столе лежит 34 камня, на другом — 42. Играют двое. За ход можно переложить со стола, на котором лежит n камней, на другой стол число камней, равное делителю числа n (возможно, все n камней. Проигрывает игрок, после хода которого будет расположение камней, уже встречавшееся в игре. Камни считаются одинаковыми, столы — разными. На бесконечной клетчатой бумаге двое по очереди закрашивают отрезки между соседними узлами сетки, каждый своим цветом. Цель первого — получить замкнутую ломаную своего цвета. Игра длится сколь угодно долго. Сможет ли второй помешать своему противнику. На доске написано число 2. Заход разрешается прибавить к числу на доске любой из его делителей, меньший самого числа. Выигрывает тот, кто первым получит число, большее 1 000 000. 6. На столе лежит две кучки спичек водной, в другой n спичек > 2n. Играют двое. Заход можно взять из одной кучки ненулевое число спичек, делящееся на число спичек во второй кучке. Выигрывает взявший последнюю спичку из какой-нибудь кучки. Город представляет собой прямоугольную сетку 10 × 12. Две компании по очереди ставят на неосвещенных перекрестках фонари. Каждый фонарь освещает в городе прямоугольник с вершиной в этом фонаре, являющийся северо-восточным углом города. Проигрывает компания, которая осветит последний перекресток. Два игрока играют на доске m × n в следующую игру. У них есть белый и черный король соответственно, стоящие в противоположных углах доски. Они передвигают своих королей (по правилам шахмат) поочередно так, чтобы расстояние между центрами клеток, на которых стоят короли, уменьшалось (королям разрешается занимать соседние клетки. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре Игры 347 Дополнительные задачи. В центре квадрата находится волка в углах — по собаке. Скорость собаки в 1, 5 раза больше скорости волка, но они могут перемещаться только по границе квадрата. Известно, что волк задирает собаку, а две собаки задирают волка. Сможет ли волк выбежать за пределы квадрата. Даны две кучки спичек. Водной, в другой 1998 спичек. Двое играют в следующую игру при своем ходе каждый выбрасывает одну из двух кучек, а другую делит на две необязательно равные кучки. Проигравшим считается тот, кто не может разделить кучку на две части. Может ли первый игрок выиграть при правильной игре второго? Как он должен для этого играть. Назовем натуральное число разрешенным, если оно имеет небо- лее 20 различных простых делителей. Вначале имеется кучка из камней. Двое по очереди берут из кучки по разрешенному количеству камней, выигрывает тот, кто возьмет последний камень. Кто выигрывает при правильной игре — тот, кто берет камни первым, или его соперник. На шахматной доске 1000 × 1000 стоит черный король и белых ладей. Докажите, что черный король независимо от игры белых может стать под удар белой ладьи. Есть чашечные весы и n гирь различного веса. Докажите, что можно выкладывать гири по одной навесы в таком порядке, чтобы порядок, в котором перевешивают левая и правая чаши был любым наперед заданным. Зачетные задачи 1, 3, 4, 5, 6, Контрольные вопросы. К какому результату приведет симметричная стратегия черных (зеркально-симметричное копирование ходов противника) в обычных шахматах при правильной игре белых? а) К ничьей; б) к выигрышу белых; в) к выигрышу черных. Правила шахмат без цугцванга отличаются отправил обычных шахмат только добавлением возможности пропустить свой ход для каждого из игроков. Могут ли черные выиграть при правильной игре белых? а) Могут; б) не могут. Кто выигрывает в игре из задачи III, если в начальный момент ферзь стоит на клетке а) Первый игрок; б) второй игрок Гл. 13. Алгоритмы, конструкции, инварианты Решения I. Ответ выигрывает первый игрок. Решение: первым ходом первый игрок кладет доминошку в центр доски (те. на две клетки, примыкающие к центру, а в дальнейшем симметрично копирует ходы второго игрока (используя центральную симметрию относительно центра доски. Предположим, что выигрышная стратегия в этой игре есть у черных. Тогда сделаем белыми первый ход Kb1-c3-b1 (два последовательных прыжка конем, после которых он возвращается на исходную клетку, ив дальнейшем будем играть, пользуясь этой выигрышной стратегией для черных. Ясно, что действуя таким образом, белые заведомо не проиграют. Полученное противоречие показывает, что у белых существует беспроигрышная стратегия. Замечание. Было бы неправильно говорить, что после хода Kb1-c3- b1 возникла начальная позиция, нос ходом черных. Дело в том, что позиция в шахматах определяется не только положением фигур на доске, но также и некоторой дополнительной информацией (ввиду правила оправе на рокировку, правила 3 ходов и правила 50 ходов. Тонкости данного доказательства можно найти в книге Карпов А. Е, Гик Е. Я. Шахматный калейдоскоп // Библиотечка Кванта. 1981. Вып. 13. См. также Ленинградские математические кружки пособие для внеклассной работы. — Киров АСА, Наша цель — поставить в каждую клетку доски 8 × 8 знак или знак «−», в зависимости оттого, какой игрок выигрывает при начальном положении ферзя на данной клетке. Будем заполнять клетки шахматной доски последовательно, начиная с й горизонтали, вертикали и диагонали a1-h8. Ясно, что в любой клетке й горизонтали, вертикали «h» и диагонали a1-h8 (кроме клетки h8) нужно поставить знак «+». Нетрудно усмотреть, что дальше клетки заполняются, исходя из следующих двух правил) если изданной клетки можно сделать допустимый ход в клетку, в которой стоит знак «−», тов данной клетке нужно поставить знак «+»; 2) если при любом допустимом ходе изданной клетки мы попадаем в клетку со знаком «+», тов данной клетке нужно поставить число знак «−». Пользуясь этими правилами, мы заполним все клетки шахматной доски. Знак, который окажется на клетке c1, покажет нам, кто выигрывает в рассматриваемой игре. 2) Cм. книгу Генкин С. А, Итенберг ИВ, Фомин Д. В Игры 349 Приведем результат заполнения клеток шахматной доски) Ставим «+» в клетках a8, b8, c8, d8, e8, f8, g8, h1, h2, h3, h4, h5, h6, h7, a1, b2, c3, d4, e5, f6, g7. 2) Ставим знак «−» в клетках f7 и g6. 3) Ставим знак «+» в клетках a7, b7, c7, d7, e7, a6, b6, c6, d6, e6, f1, f2, f3, f4, f5, g1, g2, g3, g4, g5, a2, b3, c4, d5, b1, c2, d3, e4. 4) Ставим знак «−» в клетках c5 и e3. 5) Ставим «+» в клетках a5, b5, a3, b4, c1, d2, e1. 6) Ставим знак «−» в клетках a4 и Итак, в клетке d1 стоит знак «−». Значит, в нашей игре выигрывает второй игрок. Его выигрышная стратегия такова после каждого хода первого игрока он должен вновь поставить ферзя на клетку, в которой стоит знак «−» (те. на одну из клеток e3, f7, g6). 2. Дополняющая стратегия. Докажем, что выигрывает первый игрок. Разобьем доску на «доминошки», те. пары соседних по стороне клеток. Каждым ходом первый игрок будет передвигать короля во вторую клетку той доминошки, где он перед этим ходом оказался. Тогда после каждого хода первого игрока король побывает для каждой доми- ношки либо в обеих ее клетках, либо нив одной из них. Значит, после хода второго он сможет сделать очередной ход по нашей стратегии. Передача хода. Первый игрок напишет число 3, второй — число Далее первый может написать число 6, а может написать число 5, и тогда второй напишет число 6. После написания числа 6 выигрышная стратегия есть либо уходящего, либо у его противника. Так как первый игрок после написания числа 6 может по своему желанию оказаться и ходящими противником ходящего, он может воспользоваться выигрышной стратегией. Таким образом, мы не показали, как именно должен играть первый игрок, но доказали, что у него есть выигрышная стратегия. Указание. Построение дерева позиций. Поставим в клетку с координатами) таблицы m × n знак «+», если при игре на доске x × y выигрывает первый игроки знак «−», если выигрывает второй игрок. Будем заполнять таблицу последовательно, начиная с клеток 2) и (2; 1). В этих клетках поставим знака в дальнейшем будем пользоваться следующими правилами) если изданной клетки можно сделать ход королем в клетку, в которой стоит знак «−», причем так, чтобы расстояние до центра клетки 1) уменьшилось, то ставим в данной клетке знак «+»; 2) если при любом ходе королем изданной клетки (таком, что расстояние до центра клетки (1; 1) уменьшается) мы попадаем в клетку со знаком «+», то ставим в данной клетке знак «−». Гл. 13. Алгоритмы, конструкции, инварианты Замечание. Нужно обратить внимание, что возможны ходы, при которых расстояние между центрами клеток, на которых стоят короли, уменьшается, но при этом разность координат этих центров по одной из осей увеличивается. Игры-шутки, играна опережение, накопление преимущества. А. В. Шаповалов Кроме игр, допускающих симметричную стратегию, передачу хода или построение полного дерева игры, бывают еще игры-шутки, игры на опережение, игры на накопление преимущества. Другие распространенные приемы, применяющиеся в теории игр (но которые в данной книге мы не рассматриваем) — жадный алгоритм и «заповедник». IV. Игры-шутки В таких играх побеждает всегда одна из сторон независимо от ее желания. а) На столе лежат 2007 кучек по одному ореху. За один ход разрешается объединить две кучки в одну. Двое играющих делают ходы по очереди, кто не сможет сделать ход — проигрывает. Кто выиграет? б) Тоже, но разрешается объединять кучки только с одинаковым числом орехов. Дана клетчатая полоса 1 × N. Двое играют в следующую игру. На очередном ходу первый игрок ставит в одну из свободных клеток крестика второй — нолик. Не разрешается ставить в соседние клетки два крестика или два нолика. Проигрывает тот, кто не может сделать ход. Кто из игроков может всегда выигрывать (как бы ни играл его соперник. Играна опережение Игра на опережение — распространенный прием в нематематических играх. Но ив математических играх бывает, что выигрыш достается тому, кто первый сумеет занять ключевое положение. После этого, как правило, работает дополняющая стратегия. Есть 9 запечатанных коробок соответственно с 1, 2, 3, . . . , 9 фишками. Двое играющих по очереди берут по одной фишке из любой коробки, распечатывая, если необходимо, коробку. Проигрывает тот, кто последним распечатает коробку. Кто из них может всегда выиграть независимо от игры противника. Водном из углов шахматной доски лежит плоский картонный квадрата в противоположном — квадрат 1 × 1. Двое играющих Игры 351 по очереди перекатывают каждый свой квадрат через сторону Боря большой квадрата Миша — маленький. Боря выигрывает, если не позднее го хода Мишин квадрат окажется на клетке, накрытой Бориным квадратом. Может ли Боря выиграть независимо от игры Миши, если а) первым ходит Боря; б) первым ходит Миша. Вначале есть 100 прямоугольников 2 × 1. Каждым ходом надо выбрать из имеющихся два прямоугольника с равной стороной и склеить их по этой стороне в один больший прямоугольник. Двое ходят по очереди, кто не может сделать ход — проиграл. Кто из игроков может выиграть независимо от игры противника. Накопление преимущества. Тоже весьма распространенный прием в нематематических играх. В математических играх накопление обычно связано с каким-нибудь полуинвариантом. При этом надо придумать алгоритм, ведущий к накоплению независимо от сопротивления соперника. Миша стоит в центре круглой лужайки радиуса 100 метров. Каждую минуту он делает шаг длиной 1 метр. Перед каждым шагом он объявляет направление, в котором хочет шагнуть. Катя имеет право заставить его сменить направление на противоположное. Может ли Миша действовать так, чтобы в какой-то момент обязательно выйти с лужайки, или Катя всегда сможет ему помешать. На клетчатой доске 1 × 100 000 (вначале пустой) двое ходят по очереди. Первый может заход выставить два крестика в любые два свободных поля доски. Второй может стереть любое количество крестиков, идущих подряд — без пустых клеток между ними. Если после хода первого образуется 13 или более крестиков подряд, он выиграл. Может ли первый выиграть при правильной игре обеих сторон. Двое играющих по очереди ломают палку первый на две части, затем второй ломает любой из кусков на две части, затем первый любой из кусков на две части, и т. д. Один из игроков выигрывает, если сможет после какого-то из своих ходов сложить из 6 кусков два равных треугольника. Может ли другой ему помешать? Решения 1. Указание. В обоих случаях общее число ходов не зависит отхода партии. Указание. После ответного хода на край победу второго никто не сможет предотвратить Гл. 13. Алгоритмы, конструкции, инварианты. Выигрывает второй. Первыми четырьмя ходами он должен распечатать коробки счетным числом фишек. Поскольку нечетных коробок больше, то по крайней мере одна коробка с нечетным числом фишек останется нераспечатанной. Следовательно, последней будет распечатана именно такая коробка. Нов остальных коробках в сумме — четное число фишек, поэтому они могут кончиться только после хода второго, т. е. последнюю коробку будет вынужден распечатать первый. а, б) Нет. Пусть 2 × 2 накрывает клетки a1 и b2, 1 × 1 — клетку h8. Назовем узлом A верхнюю правую вершину клетки f6, узлом B верхнюю правую вершину клетки d6. Миша должен двигать свой квадрат к соответствующему узлу (A в случаев случае б, и бегать вокруг него, уклоняясь от накрывания. Указание. Миша должен увеличивать расстояние до централу- жайки. 6. Указание. Вначале первый наращивает число групп из 13 полей с шестью дырками, затем — с пятью, и т. д. Ответ. Нет. Набросок решения. Первый ломает пополам, затем повторяет симметрично ходы второго, пока не образуется 5 пар равных кусков a > b > c > d > e. Если ни из какой тройки нельзя сложить треугольник, то первый отламывает от a кусок длины c. Второй обязан разломить c (иначе первый при своем ходе отломит кусок длины c от b и сможет сложить два равнобедренных треугольника либо со сторонами c, c, либо со сторонами c, c, e). Первый отламывает кусок длины c от другого, затем — по c отит. д, пока не станет возможным сложить треугольник из a − kc, b и Сложность суммирования 3) (9–11) Ю. Г. Кудряшов, А. Б. Скопенков 9–10 класс. Пусть имеется набор вещественных чисел x 1 , . . . , x 99 . Разрешается складывать два из уже имеющихся чисел и запоминать полученный результат. За какое наименьшее количество сложений можно найти суммы а) x 1 + . . . + Этот цикл задач предлагался на ЛКТГ в 2003 г. Благодарим И. Никокошева за полезные обсуждения Сложность суммирования 353 б) x 1 + . . . + и x 34 + . . . + Обозначим через множество {0, 1}. Введем на этом множестве операцию сложения (по модулю 2) формулами + 0 = 1 + 1 = 0, 1 + 0 = 0 + 1 = Далее будут рассматриваться только переменные из кроме задачи Пусть имеется набор переменных x 1 , . . . , x из Z 2 . Разрешается складывать (по модулю 2) два из уже имеющихся выражений и запоминать полученный результат. За какое наименьшее количество сложений можно найти суммы а) x 1 + . . . + б) x 1 + . . . + и x 34 + . . . + x 99 ? 3. Придумайте такой набор сумм, что число сложений, необходимое для его вычисления, если переменные действительные, больше, чем минимальное число сложений, необходимое для его вычисления, если переменные из Z 2 4. а) Докажите, что любую пару сумм x i 1 + . . . + x i p и x j 1 + . . . + x j q от переменных x 1 , . . . , x n , можно найти зане более чем n − 1 суммиро- вание. б) Докажите, что любую тройку сумм x i 1 + . . . + x i p , x j 1 + . . . + x j q и x k 1 + . . . + x k r от переменных x 1 , . . . , x n , можно найти зане более чем n + 1 суммирование. Докажите, что любой набор сумм вида x i 1 + . . . + x i p от переменных, можно найти зане более чем 2 n − (n + 1) суммирование. Пусть любой набор из m сумм от n переменных можно найти за l сложений. а) Докажите, что любой набор из km сумм от тех же n переменных можно найти зане более чем kl сложений. б) Докажите, что любой набор из m сумм от kn переменных x 1 , . . . , x kn можно найти зане более чем k(l + m) суммирований. 7. а) Докажите, что при достаточно больших m, n любой набор из m сумм от n переменных можно найти не более чем за mn 100 суммирований. б) Докажите, что любой набор из m сумм от n переменных можно найти зане более чем 2m l n [log 2 m] m суммирований. Здесь [x] — целая часть числа x, те. наибольшее целое число, не превосходящее x, ⌈x⌉ верхняя целая часть числа x, те. наименьшее целое число, не меньшее Гл. 13. Алгоритмы, конструкции, инварианты Зачетные задачи 1–6. 10–11 класс Последовательность суммирований можно представлять себе следующим образом. У насесть набор элементов (сумматоров) с двумя входами и одним выходом, равным сумме по модулю 2 входов (этот выход можно размножать, те. использовать несколько раз. Необходимо собрать схему из сумматоров, реализующую данный набор сумм. При этом количество суммирований равно числу использованных сумматоров. Это число называется сложностью схемы. Минимальная сложность схемы, реализующей данный набор сумм называется сложностью этого набора сумм и обозначается L(M В этих обозначениях в задаче 2 требовалось найти L({x 1 + . . . + и L({x 1 + . . . + x 66 , x 34 + . . . + Минимальное такое число l, что любой набор из m сумм от переменных можно найти за l суммирований называется сложностью упорядоченной пары (m, n) и обозначается L(m, В этих обозначениях задача 4 утверждает, что L(2, n) 6 n − и L(3, n) 6 n + 1, а задача б) утверждает, что, n) 6 2m Набор из m сумм от n переменных можно обозначать матрицей размера m × n, где на пересечении й строки иго столбца стоит если я переменная входит в ю сумму, ив противном случае. При этом я сумма будет записываться очень просто i = n X j=1 M ij В этих обозначениях наборы сумм из задачи 2 выглядят следующим образом. . . 1 , 1 . . . 1 1 . . . 1 0 . . . 0 0 . . . 0 1 . . . 1 1 . . . Рассмотрим набор из m сумм, составленных из переменных x 0 , . . . . . . , x 2 m −1 , в который все переменные входят «по-разному». Пусть соответствующая матрица. Столбцы этой матрицы — это двоичные представления целых чисел от 0 до 2 m − 1. Формально, обозначим j = b m−1,j 2 m−1 + . . . + b 0,j 2 двоичную запись числа j < 2 m . Тогда Сложность суммирования (b i,j ). Например 0 1 , B 2 = 0 0 1 1 0 1 0 1 , B 3 = 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 . 8. Докажите, что L(B m ) < 2 m+1 9. Докажите, что L(m, n) < n + 2 m+1 10. Докажите, что при достаточно больших n выполнено неравенство. Докажите, что а) существует не более чем (n + k) m+2k схем из k сумматоров с n входами и m выходами; б) если k = L(m, n), тов) при достаточно больших n верно неравенство L(n, n)> n 2 5 г) для любого ε > 0 при достаточно больших n выполнено неравенство) Для формулировки последующих результатов нам потребуются некоторые асимптотические обозначения. Говорят, что последовательность a n > 0 асимптотически не больше последовательности b n > 0, если для любого ε > 0 найдется лишь конечное множество таких индексов k, что a n > (1 + ε)b n . Обозначение. В этих обозначениях задача г) примет следующий вид, n) & n 2 4 Говорят, что последовательности a и b эквивалентны (a n ∼ b если a n /b n → 1 при n → Говорят, что последовательность {a n } есть малое от {b n } (a n ≪ b если a n /b n → 0 при n → ∞. 12. а) Докажите, что если a n b и b n c n , то a n c б) Докажите, что a n ∼ b тогда и только тогда, когда a n b и b n a n 13. Докажите, что если log 2 n ≪ f(n) ≪ 2 n , то nf (n) 2 log 2 (nf (n)) L(f (n), n). Гл. 13. Алгоритмы, конструкции, инварианты. Докажите, что при log 2 n ≪ f(n) ≪ 2 n L(f (n), n) . nf (n) log 2 f (n) 15. Докажите, что при log 2 n ≪ f(n) ≪ 2 n L(f (n), n) . nf (Из задачи следует, что при log 2 n ≪ f(n) ≪ 2 n выполнено асимптотическое неравенство nf (n) 2 log 2 (nf (n)) L(f (n), n) . nf (n) max (log 2 n, log 2 f (n)) 16. а) Рассмотрим матрицу A размера m × n, в которой нет нулевых строки нет нулевых столбцов. Верно ли, что L(A) + m = L(A t |