WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 65 |

Предположим, что не все гири одинаковые. Вычтем из каждой гири вес наименьшей гири. В результате получим набор гирь, которые снова удовлетворяют условию задачи (по крайней мере одна из полученных гирь имеет нулевой вес). Все новые гири имеют чётный вес, строго меньший веса первоначальных гирь. Поделив вес каждой гири пополам (в том числе и гири 204 Глава 17. Принцип Дирихле. Правило крайнего с нулевым весом), мы снова получим набор гирь, удовлетворяющий условию задачи. Если при этом мы не получим гири нечётного веса, то снова поделим веса всех гирь пополам и т.д. В конце концов получим систему гирь, которая удовлетворяет условию задачи и в которой есть как гири чётного (нулевого) веса, так и гири нечётного веса. Но мы уже доказали, что такого быть не может.

17.18. а) Рассмотрим наибольшие нечётные делители выбранных чисел.

У чисел от 1 до 200 есть ровно 100 различных наибольших нечётных делителей (числа 1, 3,..., 199). Итак, два из выбранных чисел имеют одинаковые наибольшие нечётные делители. Это означает, что два выбранных числа отличаются только тем, что множитель 2 входит в них в разных степенях.

Большее из них делится на меньшее.

б) Предположим, что из чисел 1, 2, 3,..., 199, 200 мы выбрали 100 чисел так, что ни одно из них не делится на другое. Достаточно доказать, что среди выбранных чисел нет чисел, меньших 16. Рассмотрим наибольшие нечётные делители всех выбранных чисел. Если наибольшие нечётные делители двух чисел совпадают, то одно из них делится на другое. Поэтому наибольшие нечётные делители выбранных чисел это в точности все числа 1, 3, 5,..., 199. В частности, среди выбранных чисел есть числа с наибольшими нечётными делителями 1, 3, 9, 27 и 81. Ни одно из выбранных чисел не делится на другое, поэтому выбранное число с наибольшим нечётным делителем 27 делится на 2, с наибольшим нечётным делителем 9 делится на 22, с наибольшим нечётным делителем 3 делится на 23, с наибольшим нечётным делителем делится на 24. Следовательно, среди выбранных чисел нет чисел 1, 2, 3, 4, 6, 8, 9 и 12. Далее, рассматривая выбранные числа с наибольшими нечётными делителями 5, 15 и 45, убеждаемся, что среди выбранных чисел нет чисел 5, и 15; рассматривая выбранные числа с наибольшими нечётными делителями 7, 21 и 63, убеждаемся, что нет чисел 7 и 14; рассматривая выбранные числа с наибольшими нечётными делителями 11 и 33, убеждаемся, что нет числа 11;

рассматривая выбранные числа с наибольшими нечётными делителями 13 и 39, убеждаемся, что нет числа 13.

17.19. Пусть некая бактерия, из которой в конце получилось m бактерий, разделилась на две бактерии. Из этих двух сестёр в конце получилось m и m бактерий, причём m + m = m. Значит, одно из чисел m и m не меньше m/2. Будем каждый раз выбирать ту из бактерий, у которой не меньше потомков, чем у её сестры. В результате получим последовательность n = a1 > a2 >... > ak = 1, причём ai ai-1/2 (здесь ai количество потомков выбранной бактерии). Выберем номер i так, что ai 2a > ai+1.

Тогда ai+1 ai/2 a, а значит, a ai+1 2a - 1.

17.20. О т в е т: y = z = 0. Числа xn, yn, zn неотрицательны, поэтому числа x, y, z тоже неотрицательны. Если бы все числа x, y, z были положительны, то наибольшее из чисел x1, y1, z1 было бы строго меньше наибольшего из чисел x, y, z, а тогда и наибольшее из чисел xn, yn, zn было бы строго меньше наибольшего из чисел x, y, z. Поэтому среди чисел x, y, z есть 0. Аналогично Глава 17. Принцип Дирихле. Правило крайнего доказывается, что среди чисел x1, y1, z1 есть 0 (при n = 1 доказывать ничего не нужно, потому что тогда x1 = x, y1 = y, z1 = z). Это означает, что два из чисел x, y, z равны. В итоге получаем, что неупорядоченный набор чисел x, y, z может быть равен либо 0, 0, 1, либо 0, 1, 1. Легко проверить, что второй набор не обладает требуемым свойством.

17.21. Предположим, что не все числа x1, x2,..., xn равны. Пусть наибольшее из этих чисел равно N, причём оно встречается среди них ровно k раз. Тогда в новой последовательности нет чисел, превосходящих N, причём число N встречается не более k - 1 раз. Поэтому после нескольких операций наибольшее значение уменьшится. Ясно также, что наибольшее значение не может стать меньше наименьшего значения чисел исходной последовательности. Поэтому после конечного числа операций все числа становятся равными.

Пусть набор равных чисел получается из набора x1, x2,..., xn. Тогда x1 = x3, x2 = x4,..., xn-1 = x1, xn = x2. Если n нечётно, то все числа x1,..., xn равны. Если n чётно, то x1 = x3 =... = xn-1 = a и x2 = x4 =... = = xn = b. Остаётся проверить, что если a = b, то такой набор чисел x1, x2,..., xn нельзя получить ни из какого набора y1, y2,..., yn. Действительно, y1 + y2 y3 + y4 yn-1 + yn y2 + y3 y4 + yпусть = =... = = a и = =... = 2 2 2 2 yn + y= = b. Тогда y1 + y2 +... + yn = 2na и y2 + y3 +... + yn + y1 = 2nb.

Поэтому a = b.

Глава 18.

Инварианты и полуинварианты 18.1. Остатки от деления 18.1. На 44 деревьях, посаженных по окружности, сидели 44 чижа (на каждом дереве по одному). Время от времени какие-то два чижа одновременно перелетают на соседние деревья в противоположных направлениях (один по часовой стрелке, другой против). Смогут ли чижи когда-нибудь собраться на одном дереве 18.2. С тройкой чисел (a, b, c) разрешается проделать следующую операцию: одно число увеличить на 2, а два других одновременно с этим уменьшить на 1. Можно ли с помощью таких операций из тройки (13, 15, 17) получить тройку с двумя нулями 18.3. В последовательности 1, 0, 1, 0, 1, 0,... каждый член начиная с седьмого равен последней цифре шести предыдущих. Докажите, что в этой последовательности никогда не встретятся подряд шесть чисел 0, 1, 0, 1, 0, 1.

18.2. Полуинварианты 18.4. Пусть a1 a2... an, b1 b2... bn и (1),..., (n) произвольная перестановка чисел 1,..., n. Докажите, что aibn-i aib(i) aibi.

Глава 18. Инварианты и полуинварианты 18.5. N солдат выстроены в одну шеренгу (плечом к плечу). По команде налево все одновременно повернулись на 90, но некоторые повернулись налево, а другие направо. Ровно через секунду каждый, кто оказался теперь лицом к лицу со своим соседом, поворачивается кругом на 180. Ещё через секунду каждый, кто оказался теперь лицом к лицу со своим соседом, поворачивается на 180, и т.д.

а) Докажите, что каждый солдат повернётся кругом не более N -раз.

б) Докажите, что движение в строю не может продолжаться более N - 1 секунд.

18.6. Целые числа x1, x2, x3, x4, x5, сумма которых положительна, расставлены по окружности. Если xi < 0, то числа xi-1, xi, xi+1 разрешается заменить на xi-1 + xi, -xi, xi+1 + xi (подразумевается, что xi+5 = xi). Докажите, что после конечного числа таких операций все числа станут неотрицательными.

18.3. Чётность перестановки Здесь мы рассматриваем понятие чётности перестановки чисел и доказываем, что это понятие определено корректно (задача 18.7). Понятие чётности перестановки применяется к анализу игры 15 (задача 18.8).

Затем мы доказываем, что любая перестановка является композицией транспозиций (задача 18.9) и приводим другие подходы к доказательству корректности определения чётности перестановки (задачи 18.и 18.11).

Транспозицией называют перестановку двух каких-то чисел в последовательности a1,..., an, т.е. при транспозиции последовательность a1,..., ai,..., aj,..., an заменяется на a1,..., aj,..., ai,..., an.

18.7. Пусть (1), (2),..., (n) некоторая перестановка чисел 1, 2,..., n. Предположим, что эта перестановка двумя разными способами получена посредством нескольких транспозиций: один раз m1 транспозициями, другой раз m2 транспозициями. Докажите, что m1 и mчисла одной чётности, т.е. число m1 - m2 делится на 2.

18.8. Игра 15 заключается в следующем. В квадрате со стороной 4 расположено 15 фишек квадратов со стороной 1. На фишках напи208 Глава 18. Инварианты и полуинварианты 1 2 3 5 6 7 саны числа от 1 до 15:. Любую фишку, граничащую 9 10 11 13 14 (по стороне) со свободной клеткой, разрешается переместить на свободную клетку (освободив тем самым другую клетку). Можно ли поменять местами фишки 14 и 15, причём так, чтобы свободная клетка осталась на прежнем месте 18.9. Докажите, что любую перестановку чисел 1,..., n можно получить из набора 1,..., n, сделав несколько транспозиций.

Перестановку чисел 1,..., n называют чётной, если её можно получить, сделав чётное число транспозиций; в противном случае её называют нечётной. Задача 18.7 показывает, что это определение корректно.

18.10. Пусть некоторая перестановка чисел 1,..., n. Назовём инверсией любую пару чисел i < j, для которой (i) > (j). Докажите, что чётность перестановки совпадает с чётностью числа всех инверсий.

Каждую перестановку чисел 1,..., n можно представить в виде произведения циклов следующим образом. Пусть (a1) = a2, (a2) = = a3,..., (ak) = a1 и числа a1, a2,..., ak попарно различны. Тогда числа a1, a2,..., ak переставляются по циклу, и мы обозначим этот цикл (a1, a2,..., ak). Отметим, что (a2, a3,..., ak, a1) тот же самый цикл.

Если (a1) = a1, то соответствующий цикл обозначаем (a1). Выберем теперь произвольное число от 1 до n, не вошедшее в первый цикл, и аналогично построим цикл, включающий это число. Продолжая действовать таким образом, мы сопоставим перестановке набор непересекающихся циклов. Например, перестановке (1) = 2, (2) = 1, (3) = 4, (4) = 3 соответствует произведение циклов (12)(34).

18.11. а) Пусть перестановка чисел 1,..., n представляет собой произведение m циклов. Сделаем после этой перестановки транспозицию каких-либо двух чисел. Докажите, что в результате получится перестановка, которая представляет собой произведение m ± 1 циклов.

б) Докажите, что перестановка чётна тогда и только тогда, когда число n - m чётно.

Решения 18.1. О т в е т: не смогут. Занумеруем деревья по часовой стрелке. Пусть в какой-то момент времени на k-м дереве сидит nk чижей. Рассмотрим сумму n1 + 2n2 +... + 44n44. Если один чиж перелетает на соседнее дерево по Глава 18. Инварианты и полуинварианты часовой стрелке, то эта сумма либо увеличивается на 1, либо уменьшается на 43, а если против часовой стрелки, то либо уменьшается на 1, либо увеличивается на 43. Поэтому при одновременных перелётах чижей остаток от деления рассматриваемой суммы на 44 не изменяется. Сначала сумма равна 44 · 1 + 2 +... + 44 = = 990; остаток от деления на 44 равен 22. А если бы чижи собрались на одном дереве, то сумма делилась бы на 44. Поэтому чижи не смогут собраться на одном дереве.

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

18.2. О т в е т: нельзя. При указанной операции первые два числа (a, b) заменяются либо на (a - 1, b - 1), либо на (a + 2, b - 1), либо на (a - 1, b + 2). Во всех трёх случаях остаток от деления числа a - b на 3 не изменяется. Числа 13 и 15 дают разные остатки при делении на 3. Поэтому из тройки (13, 15, 17) нельзя получить тройку, состоящую из двух нулей и числа 45 = 13 + 15 + 17.

18.3. Будем заменять шестёрку чисел (x1,..., x6) на шестёрку чисел (x2, x3,..., x6, x7), где x7 последняя цифра числа x1+...+x6. Покажем, что при такой операции последняя цифра числа S(x1,..., x6) = 2(x1 + 2x2 + 3x3 + +4x4+5x5+6x6) не изменяется. Действительно, S(x2,..., x7)-S(x1,..., x6) = = 12x7 - 2(x1 +... + x6) 2 x7 - (x1 +... + x6) 0 (mod 10).

Последние цифры у чисел S(1, 0, 1, 0, 1, 0) = 18 и S(0, 1, 0, 1, 0, 1) = разные, поэтому в рассматриваемой последовательности не могут встретиться подряд шесть чисел 0, 1, 0, 1, 0, 1.

18.4. Предположим сначала, что и две перестановки чисел 1,..., n, для которых (k) = (k+1), (k+1) = (k) и (i) = (i) при i = k, k+1. Тогда если (k + 1) > (k), то aib(i) - aib (i) = (ak+1 - ak)(b(k+1) - b(k)) 0.

Возьмём произвольную перестановку. Если (k + 1) > (k), то поменяем местами числа (k + 1) и (k). В результате получим новую перестановку.

Применим к ней ту же самую операцию и т.д. После нескольких таких операций получим перестановку n, n - 1,..., 1. Это доказывает неравенство aibn-i aib(i). Если же мы будем менять местами (k + 1) и (k) в том случае, когда (k + 1) < (k), то после нескольких таких операций получим перестановку 1, 2,..., n. Это доказывает неравенство aib(i) aibi.

18.5. а) Пусть m количество всех солдат, повернувшихся лицом к данному солдату. Тогда этот солдат повернётся кругом не более m раз. Действительно, в те моменты, когда солдат не поворачивается, число m не изменяется, а в те моменты, когда солдат поворачивается, число m уменьшается на 1. Остаётся заметить, что m N - 1.

б) Применим индукцию по N. При N = 1 требуемое утверждение верно.

Пусть N 2. Рассмотрим двух крайних справа солдат самого крайнего и его соседа. Если крайний справа солдат смотрит направо, то он никогда 210 Глава 18. Инварианты и полуинварианты поворачиваться не будет, и он и его сосед никогда не будут стоять лицом друг к другу. В этом случае оценка времени движения строя такая же, как в случае строя из N -1 солдат. Если крайний справа солдат смотрит налево, а его сосед стоит лицом к нему, то оба эти солдата должны повернуться кругом. После этого крайний справа солдат будет смотреть направо. В этом случае к оценке времени движения строя из N - 1 солдат добавляется одна секунда. Остаётся разобрать случай, когда оба крайних справа солдата смотрят налево.

Будем считать, что солдаты, стоящие лицом друг к другу, не поворачиваются, а меняются местами (каждый делает шаг вперёд); время движения строя от этого не изменится. Теперь оба крайних солдата будут либо стоять неподвижно, либо шагать вперёд (по направлению к левому краю шеренги).

При этом движение предпоследнего солдата (т.е. того, который первоначально был предпоследним справа) не зависит от движения последнего солдата. Кроме того, последний солдат отстаёт от предпоследнего не более, чем на 2 шага (т.е. между ними не может быть более одного солдата).

Время движения предпоследнего солдата такое же, как время его движения в случае строя из N - 1 солдат. После того как предпоследний солдат остановится, последний солдат может сделать один шаг. А уже после этого никакого движения не будет: все солдаты позади предпоследнего смотрят направо, а впереди налево.

18.6. Прежде всего заметим, что при указанных операциях сумма чисел не изменяется. Для каждого набора X = (x1, x2, x3, x4, x5) положим F (x) = = (xi - xi+2)2. Пусть xi < 0 и Y = (xi-2, xi-1 + xi, -xi, xi+1 + xi, xi+2).

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 65 |



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

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