Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
18.2. Полуинварианты 18.4. Пусть a 1 6 a 2 6 . . . 6 a n , b 1 6 b 2 6 . . . 6 и s (1), . . . . . . , s (n) — произвольная перестановка чисел 1, . . . , n. Докажите, что. N солдат выстроены в одну шеренгу (плечом к плечу. По команде налево все одновременно повернулись на 90 ◦ , но некоторые повернулись налево, а другие направо. Ровно через секунду каждый, кто оказался теперь лицом к лицу со своим соседом, поворачивается кругом на 180 ◦ . Ещё через секунду каждый, кто оказался теперь лицом к лицу со своим соседом, поворачивается на и т. да) Докажите, что каждый солдат повернётся кругом не более N − 1 раз. б) Докажите, что движение встрою не может продолжаться более N − 1 секунд. Целые числа x 1 , x 2 , x 3 , x 4 , x 5 , сумма которых положительна, расставлены по окружности. Если x i < 0, то числа x i −1 , x i , разрешается заменить на x i −1 + x i , −x i , x i+1 + подразумевается, что x i+5 = x i ). Докажите, что после конечного числа таких операций все числа станут неотрицательными. Чётность перестановки Здесь мы рассматриваем понятие чётности перестановки чисел и доказываем, что это понятие определено корректно задача. Понятие чётности перестановки применяется к анализу игры «15» (задача 18.8). Затем мы доказываем, что любая перестановка является композицией транспозиций (задача 18.9), Глава 18. Инварианты и полуинварианты и приводим другие подходы к доказательству корректности определения чётности перестановки (задачи 18.10 и Транспозицией называют перестановку двух каких-то чисел в последовательности a 1 , . . . , a n , те. при транспозиции последовательность, заменяется на a 1 , . . . , a j , . . . , a i , . . . , a n 18.7. Пусть s (1), s (2), . . . , s (n) — некоторая перестановка чисел 1, 2, . . ., n. Предположим, что эта перестановка двумя разными способами получена посредством нескольких транспозиций: один раз m 1 транспозициями, другой раз m 2 транспозициями. Докажите, что и m 2 — числа одной чётности, те. число m 1 − делится на Игра «15» заключается в следующем. В квадрате со стороной 4 расположено 15 фишек — квадратов со стороной. На фишках написаны числа от 1 до 15: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Любую фишку, граничащую (по стороне) со свободной клеткой, разрешается переместить на свободную клетку (освободив тем самым другую клетку. Можно ли поменять местами фишки 14 и 15, причём так, чтобы свободная клетка осталась на прежнем месте. Докажите, что любую перестановку чисел 1, . . ., можно получить из набора 1, . . ., n, сделав несколько транс- позиций. Перестановку чисел 1, . . . , n называют чётной, если её можно получить, сделав чётное число транспозиций; в противном случае её называют нечётной. Задача 18.7 показывает, что это определение корректно Решения задач. Пусть s — некоторая перестановка чисел 1, . . ., n. Назовём инверсией любую пару чисел i < j, для которой s (i) > s (j). Докажите, что чётность перестановки совпадает сч тностью числа всех инверсий. Каждую перестановку чисел 1, . . . , n можно представить в виде произведения циклов следующим образом. Пусть s (a 1 ) = a 2 , s (a 2 ) = a 3 , . . . , s (a k ) = и числа a 1 , a 2 , . . . , попарно различны. Тогда числа a 1 , a 2 , . . . , переставляются по циклу, и мы обозначим этот цикл (a 1 , a 2 , . . . , a k ). Отметим, что, a 3 , . . . , a k , a 1 ) — тот же самый цикл. Если s (a 1 ) = a 1 , то соответствующий цикл обозначаем (a 1 ). Выберем теперь произвольное число от 1 доне вошедшее в первый цикли аналогично построим цикл, включающий это число. Продолжая действовать таким образом, мы сопоставим перестановке набор непересекающихся циклов. Например, перестановке s (1) = 2, s (2) = 1, s (3) = 4, s (4) = 3 соответствует произведение циклов. а) Пусть перестановка чисел 1, . . . , n представляет собой произведение m циклов. Сделаем после этой перестановки транспозицию каких-либо двух чисел. Докажите, что в результате получится перестановка, которая представляет собой произведение m ± 1 циклов. б) Докажите, что перестановка чётна тогда и только тогда, когда число n − m чётно. Решения 18.1. О т в е т: не смогут. Занумеруем деревья почасовой стрелке. Пусть в какой-то момент времени нам дереве сидит n k чижей. Рассмотрим сумму n 1 + 2n 2 + . . . + 44n 44 . Если один чиж перелетает на соседнее дерево почасовой стрелке, то эта сумма либо увеличивается на 1, либо уменьшается на 43, а если против часовой стрелки, то либо уменьшается на 1, либо увеличивается на 43. Поэтому при одновременных перелётах чижей остаток отделения рассматриваемой суммы на 44 не изменяется. Сначала сумма равна 1 + 2 + . . . + 44 = 44 · 45 2 = 990; остаток отделения на равен 22. А если бы чижи собрались на одном дереве, то сумма делилась бы на 44. Поэтому чижи не смогут собраться на одном дереве Глава 18. Инварианты и полуинварианты З а меча ни е. Тоже самое решение годится для произвольного чётного числа деревьев и чижей. Для нечётного числа легко строится пример, показывающий, что чижи могут собраться на одном дереве. Ответ нельзя. При указанной операции первые два числа (a, b) заменяются либо на (a−1, b−1), либо на (a+2, либо на (a − 1, b + 2). Во всех трёх случаях остаток отделения числа a −b на 3 не изменяется. Числа 13 и 15 дают разные остатки при делении на 3. Поэтому из тройки (13, 15, 17) нельзя получить тройку, состоящую из двух нулей и числа 45 = 13 + 15 + 17. 18.3. Будем заменять шестёрку чисел (x 1 , . . . , x 6 ) нашест р- ку чисел (x 2 , x 3 , . . . , x 6 , x 7 ), где x 7 — последняя цифра числа+ . . . + x 6 . Покажем, что при такой операции последняя цифра числа S(x 1 , . . . , x 6 ) = 2(x 1 + 2x 2 + 3x 3 + 4x 4 + 5x 5 + 6x 6 ) не изменяется. Действительно, S(x 2 , . . . , x 7 ) − S(x 1 , . . . , x 6 ) = 12x 7 − − 2(x 1 + . . . + x 6 ) ≡ 2(x 7 − (x 1 + . . . + x 6 )) ≡ 0 (mod У чисел S(1, 0, 1, 0, 1, 0) = 18 и S(0, 1, 0, 1, 0, 1) = 24 последние цифры разные, поэтому в рассматриваемой последовательности не могут встретиться подряд шесть чисел 0, 1, 0, 1, 0, 1. 18.4. Предположим сначала, что и t — две перестановки чисел 1, . . . , n, для которых s (k) = t (k + 1), s (k + 1) и s (i) = t (i) при i 6= k, k + 1. Тогда если s (k + 1) > s (k), то (a k +1 − a k )(b s (k +1) − b s (k) ) > 0. Возьмём произвольную перестановку s . Если s (k + 1) то поменяем местами числа s (k + 1) и s (k). В результате получим новую перестановку. Применим к ней туже самую операцию и т. д. После нескольких таких операций получим перестановку. Это доказывает неравенство 6 P a i b s (i) . Если же мы будем менять местами s (k +1) ив том случае, когда s (k + 1) < s (k), то после нескольких таких операций получим перестановку 1, 2, . . . , n. Это доказывает неравенство. а) Пусть m — количество всех солдат, повернувшихся лицом к данному солдату. Тогда этот солдат повернётся кругом не более m раз. Действительно, в те моменты, когда солдатне поворачивается, число m не изменяется, а в те моменты, когда солдат поворачивается, число m уменьшается на 1. Остаётся заметить, что m 6 N − б) Применим индукцию по N. При N=1 требуемое утверждение верно. Пусть N > 2. Рассмотрим двух крайних справа солдат — самого крайнего и его соседа. Если крайний справа солдат смотрит направо, то он никогда поворачиваться не будет, ион и его сосед Решения задач 233 никогда не будут стоять лицом друг к другу. В этом случае оценка времени движения строя такая же, как в случае строя из N − солдат. Если крайний справа солдат смотрит налево, а его сосед стоит лицом к нему, то оба эти солдата должны повернуться кругом. После этого крайний справа солдат будет смотреть направо. В этом случае к оценке времени движения строя из N − 1 солдат добавляется одна секунда. Остаётся разобрать случай, когда оба крайних справа солдата смотрят налево. Будем считать, что солдаты, стоящие лицом друг к другу, не поворачиваются, а меняются местами (каждый делает шаг впер д) время движения строя от этого не изменится. Теперь оба крайних солдата будут либо стоять неподвижно, либо шагать впер д (по направлению клевому краю шеренги. При этом движение «предпоследнего» солдата (те. того, который первоначально был предпоследним справа) не зависит от движения последнего солдата. Кроме того, последний солдат отстаёт от «предпоследнего» не более чем на 2 шага (те. между ними не может быть более одного солдата. Время движения предпоследнего солдата такое же, как время его движения в случае строя из N − 1 солдат. После того как предпоследний солдат остановится, последний солдат может сделать один шаг. А уже после этого никакого движения не будет все солдаты позади предпоследнего смотрят направо, а впереди — налево. Прежде всего заметим, что при указанных операциях сумма чисел не изменяется. Для каждого набора X=(x 1 , x 2 , x 3 , x 4 , положим F(x) = 5 P i =1 (x i − x i +2 ) 2 . Пусть x i < 0 и Y = (x i −2 , x i −1 + x i , −x i , x i +1 + x i , x i +2 ). Несложные вычисления показывают, что F(Y) = −2x i (x 1 + x 2 + x 3 + x 4 + x 5 ) > те. Это означает, что после каждой операции целое неотрицательное число F(X) строго уменьшается. Такой процесс не может продолжаться бесконечно долго. Возьмём произвольные попарно различные числа x 1 , . . . . . . , и рассмотрим число x j x s (i) − x s (j) = ±1. Покажем, что если это число равно 1, то числа и m 2 чётные, а если оно равно то числа и m 2 нечётные. Предположим сначала, что s — транспозиция, те и s (k) = k при k 6= i, j. Пусть для определённости i < Тогда в рассматриваемое произведение входит дробь x j x j − x i = −1. Глава 18. Инварианты и полуинварианты Легко также проверить, что для каждого k 6= i, j произведение соответствующих дробей для пар чисел (k, i) и (k, j) равно 1. Действительно, если k < i < j, то получаем произведение x k x j − x k · x j − x k x i − если i < k < j, получаем x i x k − x j · x j − x k x i − x k ; если i < j < k, получаем x i x k − x j · x k − x j x k − x i . Ясно также, что все остальные дроби равны Таким образом, для одной транспозиции получаем число Если после транспозиции мы сделаем ещё транспозицию то для полученной в результате перестановки рассматриваемое число равно 1, поскольку x j x t ( s (i)) − x t ( s (j)) = x i − x j x s (i) − x s (j) · ±(x s (i) − x s (j) ) ±(x t ( s (i)) − те. рассматриваемые числа для и для перемножаются. Аналогично доказывается, что после каждой транспозиции рассматриваемое число меняет знак. Ответ нет, нельзя. Сопоставим свободной клетке номер. Тогда после каждого хода получается некоторая перестановка чисел 1, . . . , 16. При этом каждый ход представляет собой транспозицию. Мы хотим в итоге получить транспозицию 14 Покажем, что свободная клетка может вернуться на исходное место только после чётного числа ходов, теч тного числа транс- позиций. Согласно задаче 18.7 из этого следует, что так нельзя получить транспозицию. Чтобы вернуться на исходное место, свободная клетка должна сделать вверх столько же ходов, сколько вниз, и влево столько же, сколько вправо. Поэтому общее число ходов должно быть чётно. 18.9. Достаточно доказать, что из любой перестановки s (1), . . . . . . , s (n) можно получить набор 1, . . . , n, сделав несколько транспо- зиций (эти транспозиции можно будет сделать в обратном порядке. Если s (1) 6= 1, то поменяем местами 1 и s (1). Затем в новом наборе чисел поменяем местами 2 и s (2), если s (2) 6= 2, и т. д. Достаточно доказать, что после каждой транспозиции изменяется чётность числа всех инверсий. Пусть при транспозиции меняются местами числа s (i) и s (j). Тогда инверсия может появиться или исчезнуть только для пари. Легко видеть, что появление или исчезновение инверсии может произойти только в том случае, когда k заключено между i и j, а заключено между s (i) и s (j). Нов этом случае обе инверсии одновременно либо появляются, либо исчезают Решения задача) Пусть при транспозиции переставляются числа a и Рассмотрим два случая. Числа a и b входят в один цикл (a, a 1 , . . . , a p , b, b 1 , . . . , Тогда после транспозиции из этого цикла получаются два цикла) и (b, b 1 , . . . , b q ), поскольку a → a 1 , a 2 → a 3 , . . . . . . , a p → b → a и b → b 1 , . . . , b q → a → b. Остальные циклы не меняются. Числа a и b входят в разные циклы (a, a 1 , . . . , a p ) и (b, b 1 , . . . . . . , b q ). Тогда после транспозиции из этих двух циклов получится один цикл (a, a 1 , . . . , a p , b, b 1 , . . . , b q ), поскольку a → a 1 , . . . . . . , a p → a → b, b → b 1 , . . . , b q → b → б) Разобьём все перестановки на два класса те, для которых число n − m чётно, и те, для которых число n − m нечётно. Первый класс содержит тождественную перестановку 1, 2, . . . , n для неё n − m = 0). Второй класс содержит все транспозиции (для них m = 1). Согласно задаче а) применение транспозиции изменяет класс. Поэтому перестановки, которые получаются из тождественной чётным числом транспозиций, лежат в первом классе, а перестановки, которые получаются из тождественной нечётным числом транспозиций, лежат во втором классе ГЛАВА ЛОГИКА. Логические задачи. В трёх ящиках лежат шары — чёрный, белый и зе- лёный (в каждом ящике по одному шару. На первом ящике написано белый, на втором — «чёрный», на третьем белый или зелёный». Известно, что ни одна надпись не соответствует действительности. Выясните, где какие шары лежат. Путешественник попал на остров, часть обитателей которого всегда говорит правду, а остальные всегда лгут. Какой вопрос должен задать путешественник обитателю острова, чтобы выяснить, всегда ли он говорит правду или всегда лжёт? 19.3. Один человек всегда говорит правду, а другой человек всегда лжёт. Какой вопрос нужно им задать, чтобы они ответили на него одинаково. Некто всегда говорит правду. Какой вопрос нужно ему задать дважды, чтобы он дал на него разные ответы. Дано 8 предметов, один из которых выделен. Требуется задать 3 вопроса, на которые даются только ответы «да» и нет, и узнать, какой предмет выделен. В институте работают правдолюбы, которые всегда говорят правду, и лжецы, которые всегда лгут. Однажды каждый из сотрудников сделал два заявления) В институте нет и десяти человек, которые работают больше меня Условия задач 2) В институте по крайней мере уста человек зарплата больше, чему меня. Известно, что нагрузка у всех сотрудников разная, и зарплата тоже. Сколько человек работает в институте. Три мудреца сидят на стульях в затылок друг другу так, что сидящий впереди не видит тех, кто сидит сзади. Они знают, что есть 3 белых и 2 чёрных шляпы. Мудрецы зажмуривают глаза и им на головы надевают шляпы, после чего оставшиеся шляпы убирают. Мудрецы открывают глаза, и сидящий сзади всех говорит, что он не знает, какого цвета на нём шляпа. После этого сидящий посредине говорит, что он тоже не знает, какого цвета на нём шляпа. Знает ли теперь сидящий впереди, какого цвета на нём шляпа. В вагоне поезда едут несколько мудрецов. Когда поезд проехал туннель, в окна попала пыль. Вошёл проводники сказал У некоторых из вас испачкались лица. К сожалению, в поезде нет воды. Но сейчас будут большие остановки, поэтому можно будет выйти из поезда и умыться На n-й остановке испачкавшиеся мудрецы вышли из поезда, чтобы умыться. Сколько мудрецов испачкалось (Мудрец идёт умываться тогда и только тогда, когда он точно знает, что испачкался. Логические парадоксы П ара док с лжеца. Некто произносит фразу Высказывание, которое я сейчас произношу, ложно. Ложно само это высказывание или нет? Если допустить, что это высказывание истинно, то оно должно быть ложным, а если допустить, что это высказывание ложно, то оно должно быть истинным. П ара док с парикмахера. Деревенский парикмахер бреет тех и только тех жителей своей деревни, которые не бреют себя сами. Бреет ли он себя Глава 19. Логика Если допустить, что он не бреет себя, то он должен себя брить, а если допустить, что он бреет себя, то он не должен себя брить. П ара док с Р и шар а. Рассмотрим множество всех натуральных чисел, каждое из которых может быть однозначно определено посредством осмысленного текста, содержащего не более тысячи слогов. Это множество конечно, поскольку таких текстов конечное число. Рассмотрим наименьшее натуральное число, не входящее в указанное множество. Выделенный курсивом текст содержит менее тысячи слогов, поэтому он определяет число из рассматриваемого множества. С другой стороны, он определяет число, не входящее в это множество. Логика высказываний Пусть p и q — некоторые высказывания, каждое из которых может быть либо истинным (И, либо ложным (Л. Из них можно составить следующие составные высказывания — отрицание «p неверно & q — конъюнкция верны p и q»; p ∨ q — дизъюнкция верно p или q»; p → q — импликация «p влечёт q», те верно, если p верно q — эквивалентность «p эквивалентно Эти составные высказывания имеют следующие таблицы истинности & q p ∨ q p → q p ↔ И И Л И И И И И Л Л Л И Л Л Л И И Л И И Л Л Л И Л Л И И Для конъюнкции часто используется также обозначение а для эквивалентности — обозначение ≡. |