Основные задачи
Логические задачи
1;–;9, а также;6Л1, 6Л2, 6Л3, 6Л4, 73
1.;(6);Мальчик по четвергам и пятницам всегда говорит правду, а по вторникам всегда лжет. Однажды его 7 дней подряд спрашивали, как его зовут. Шесть первых дней он давал такие ответы: Андрей, Борис, Андрей, Борис, Виктор, Борис. Какой ответ он дал на седьмой день? (И. Рубанов, Уральский турнир)
2.;(6);«В этой фразе доля цифр;X;составляет …/…, доля цифр;Y;– …/…, а на долю остальных использованных цифр остается …/… .». Вставьте разные цифры вместо;X;и;Y;и числа вместо многоточий так, чтобы утверждение было верным. (А. Шаповалов)
3.;(7-8);На острове живут рыцари и лжецы, всего 100 человек. Каждого из них спросили: «Сколько рыцарей среди твоих друзей на этом острове?» Среди ответов каждое число от 0 до 99 встретилось ровно по одному разу. Сколько на этом острове рыцарей? (Рыцари всегда говорят правду, а лжецы всегда лгут). (А. Шаповалов)
4.;(6-8) По кругу стоят лжецы и рыцари, всего 100 человек. В первый раз каждого спросили: «Верно ли, что твой сосед справа – лжец?». Двое ответили: «Да», остальные – «Нет». Во второй раз каждого спросили: «Верно ли, что твой сосед слева через одного – лжец?». И снова двое ответили: «Да», остальные – «Нет». В третий раз спросили: «Верно ли, что стоящий напротив тебя – лжец?». Сколько человек на этот раз ответят «да»? (А. Шаповалов)
5.;(6-7);За круглым столом сидят 30 учеников, некоторые из которых всегда говорят правду, а остальные всегда лгут. Известно, что среди двух соседей каждого лжеца есть ровно один лжец. При опросе 12 учеников сказали, что ровно один из их соседей – лжец, а остальные сказали, что оба их соседа – лжецы. Сколько лжецов сидит за столом? (9-й Уральский турнир)
6.;(6-7);В классе учатся рыцари и лжецы, всего 25 учеников. Первый сказал: «Среди моих друзей-одноклассников рыцарей на 1 больше, чем лжецов». «Второй сказал: «Среди моих друзей-одноклассников рыцарей на 2 больше, чем лжецов». И так далее, вплоть до двадцать пятого ученика, который сказал: «Среди;моих друзей-одноклассников рыцарей на 25 больше, чем лжецов». Сколько лжецов учится в этом классе? (А. Шаповалов)
7.;(6-7);По кругу стоят 2011 аборигенов;–;рыцари и лжецы (обязательно есть и те, и другие). Каждого из них спросили: «Верно ли, что среди двух твоих соседей четное количество лжецов?». Могло ли так случиться, что каждый из них ответил: «Да»? (Фольклор)
8.;(6-7) Пять мудрецов играют в мафию. Среди них два мафиози, два мирных жителя и комиссар. Мафиози знают друг друга, комиссар знает всё, мирные жители изначально ничего про других игроков не знают. Мафиози могут говорить что угодно. Остальные говорят только то, в чем сами уверены. Состоялся разговор:
А:;«Д – мирный житель».
Б:;«Нет, Д – мафиози».
В:;«Д не знает, кто я».
Г:;«Д знает, кто я».
Д:;«Б – мафиози».
Определите роли всех тех игроков, для кого это возможно. (И. Раскина)
9.;(6-8);Трем математикам нарисовали на лбу по прямоугольнику (с указанием размеров) и сообщили, что из этих трех прямоугольников можно сложить квадрат. Каждый математик не видит, что;нарисовано;у него на лбу, но видит;лбы;двух других. Первый сказал, что не может;определить;размеры прямоугольника у;себя;на лбу. Затем то же самое сказал второй математик. Найдите отношение сторон прямоугольника на лбу третьего математика. (А. Шаповалов)
;
Комбинаторные задачи
Классическая комбинаторика
10, а также;6K1, 7К3, 7КГ1, 8Ар1, 8К1, 8К2, 8К4.
10.;(7-9);В клетчатом квадрате;n×n;стерли все клетки выше главной диагонали, идущей из левого верхнего в правый нижний угол. В каждую клетку оставшейся «лесенки» записывают 0 или 1, при этом, если в какой-то клетке написана единица, то и в соседних с ней по стороне слева и сверху также должна стоять единица. Сколькими способами это можно сделать? (Е. Горская)
Дискретная непрерывность
11;–;12
11.;(7-8);В строке шестизначных чисел первое число 123456, последнее 654321. Соседние числа отличаются на 1 или на 1000. Ни одно число не делится на 1000. Докажите, что хотя бы одно число делится на 13. (А. Шаповалов)
12.;а) (6-7);Натуральные числа от 1 до 2011 покрашены в два цвета. Числа 1 и 2011 – красные, 11 и 20 – синие. Докажите, что можно выбрать пару красных и пару синих чисел с одинаковыми суммами.;(Фольклор)
б) (6-8);Натуральные числа от 1 до 2011 покрашены в красный и синий цвета. Есть пара красных и пара синих чисел с одинаковыми произведениями. Докажите, что можно выбрать пару красных и пару синих чисел с одинаковыми суммами. (А. Шаповалов)
Подсчет двумя способами
13;–;17
13.;(6-7) 2010 шариков раскрасили в 7 цветов радуги. На каждом шаре написали общее количество шаров такого же цвета, как и этот. Чему может быть равна сумма чисел, обратных написанным? (Г. Гальперин)
14.;(6-7);Для каждого натурального числа, начиная с 1, подсчитали количество жителей Судиславля, возраст которых не меньше этого числа. Полученные результаты сложили. Докажите, что итог равен сумме возрастов жителей Судиславля. (Фольклор)
15.;(7-8) Всех участников турнира два раза разбивали на команды: первый раз для игры в «Абаку», второй – в «Завалинку». Размеры команд в каждой игре не обязательно одинаковы, но в каждой команде есть хотя бы один участник. Оказалось, что каждый участник играл в «Завалинку» в не меньшей по численности команде, чем в «Абаку». Докажите, что в «Абаку» играло не меньше команд, чем в «Завалинку». (Фольклор)
16.;(8);В классе 32 человека. Каждый из них назвал два числа: количество его одноклассников с таким же ростом, но другим весом и количество его одноклассников с таким же весом, но другим ростом. Среди названных чисел встретились все числа от 0 до 10. Докажите, что в этом классе можно выбрать двух человек с одинаковым ростом и одинаковым весом. (К. Матвеев, А. Шаповалов)
17.;(7-8);В квадрат размером 4´4 положили одинаковые фигурки пентамино (см. рис.). Может ли каждая клетка квадрата быть покрыта одно и то же количество раз? (М. Артемьев)
Примеры и оценки
18;–;36, а также;6Д2, 6Д3, 6Д4,;6К2, 6К4, 7К1, 7К4, 7К5, 7Ц2, 7КГ3, 7КГ5, 8Ар5, 8К3,;8Т1,;8Т3, 8Т5,;45, 46, 47, 48, 55, 56,;86, 88, 101, 130, 132, 141, 144, 145, 155, 156.
18.;(6-7);17 школьников сдавали тест. Каждый из них набрал целое число баллов, у всех разное. Каждый школьник набрал меньше, чем любые два в сумме. Могло ли случиться так, что Петя набрал 15 баллов? (Б. Френкин)
19.;(6-8);Барон Мюнхгаузен утверждает: он, мол, может для некоторого;N;так переставить числа 1, 2, …,;N;в другом порядке и затем выписать их все подряд без пробелов, что в результате получится многозначное число-палиндром (оно читается одинаково слева направо и справа налево). Не хвастает ли барон? (А. Шаповалов)
20.;(6-7);Кубик Яндекса – куб 2×2×2 – висит на ветке около домика 10 в Берендеевых Полянах. На каждом квадратике поселилось по одному пауку. Каждый паук либо всегда правдив, либо постоянно лжет. При этом каждый возмутился: «У меня есть сосед-лжец!» Соседями считаются пауки, живущие в клетках, имеющих общую сторону. Какое наибольшее число пауков-лгунов могло жить на Кубике Яндекса? (Д. Калинин)
21.;(6-8);Назовем набор шариков;радующим глаз, если в нем есть шарики трех;или более;цветов. Имеется 100 шариков. Известно, что как ни раскладывай их на 25 наборов по 4 шарика, хотя бы один из наборов будет радовать глаз. Каково наименьшее количество цветов у этих 100 шариков? (Н. Чернятьев)
22.;(7-8) У Саши есть 27 кусков сыра;весом;100, 200, 300, …, 2700 граммов. Он очень хочет разложить весь сыр на кучки так, чтобы в каждой кучке был кусок, весящий столько же, сколько и все остальные куски в этой кучке вместе. Сколько кучек у него может получиться? (А. Грибалко)
23.;(6-7);В игре «Что? Где? Когда?» участвовали 20 команд. Каждая письменно ответила на несколько вопросов. Ответ на каждый вопрос сдавался на отдельной карточке. Ровно 10 команд сдали верные ответы не более чем на 5 вопросов, при этом их карточки с верными ответами составили более 30% от всех карточек с верными ответами. Можно ли утверждать, что найдутся три команды, которые дали поровну верных ответов? (Д. Калинин)
24.;(6-8);Клетки квадрата 6×6 раскрасили в 9 цветов. Каждым цветом окрашены;четыре;клетки, центры которых являются вершинами прямоугольника со сторонами, параллельными краям квадрата. Могут ли периметры всех этих прямоугольников быть различными? (А. Грибалко)
25.;(6-8) В летней школе мальчики и девочки живут в 2- и 3-местных номерах (как мальчики, так и девочки занимают много и 2-, и 3-местных номеров). Свободных мест нет. Посреди смены уехал один мальчик, живший в 3-местном номере, а приехала новая девочка. Какое наименьшее количество школьников придется переселить, чтобы поселить девочку в 2-местный номер? (В. Гуровиц)
26.;(6-8);На какое наибольшее число кучек можно разложить гири весами 1, 2, 3, …,; 16 г так, чтобы кучки нельзя было разделить на две группы равного веса? (А. Шаповалов)
27.;(6-7);В первый раз на танцевальный кружок пришли 14 мальчиков и 14 девочек. Их разбили на пары по росту: самый высокий мальчик с самой высокой девочкой, второй по росту – со второй по росту и так далее. В каждой паре девочка оказалась выше мальчика. В следующий раз добавились одна девочка и один мальчик. Когда их всех опять разбили на пары по росту, в каждой паре мальчик оказался выше девочки. Для шуточного танца самого высокого мальчика поставили в пару с самой низкой девочкой, второго по росту – с предпоследней по росту и так далее. В скольких парах теперь мальчик выше девочки? (А. Шаповалов)
28.;(7-8) На шахматной доске отметили 12 клеток. Докажите, что среди отрезков, соединяющих центры отмеченных клеток, найдутся три одинаковых. (А. Грибалко)
29.;а);(6-7);Из 40 спичек выложена доска 4×4 так, что каждую клетку ограничивают четыре спички. Как убрать 11 спичек так, чтобы оставшиеся не ограничивали никакого прямоугольника?
б);(7-8);Из спичек выложена доска 8×8 так, что каждую клетку ограничивают четыре спички. Какое наименьшее число спичек можно убрать, чтобы после этого не осталось ни одного контура прямоугольника? (Д. Калинин)
30.;(7-8);В клетках таблицы 11´11 написаны все натуральные числа от 1 до 121, причем 1 стоит в левом нижнем углу, а число 121 – в правом верхнем. Оказалось, что любые два числа, отличающиеся на 1, стоят в соседних по стороне клетках. Какова наибольшая возможная разность между числами в соседних клетках? (Б. Френкин)
31.;(6-7);Какое наибольшее количество натуральных чисел от 1 до 100 можно взять, чтобы произведение любых 11 из них было кратно 6? (Д. Калинин)
32.;(6-7);На свободные поля шахматной доски по одной выставляются ладьи. Выставляемая ладья должна побить четное число пустых клеток в момент выставления на доску. Каково наибольшее возможное число ладей?;(А. Шаповалов)
33.;(7-8);На шахматную доску по одному выставляются слоны. Первого можно выставить произвольно, а каждый следующий должен в момент выставления побить нечетное число слонов. Какое наибольшее количество слонов может быть выставлено? (Слоны бьют друг друга, если они стоят на одной диагонали и между ними нет других слонов). (А. Шаповалов)
34.;а);(6-7);Клетчатую квадратную рамку 17×17 (с дыркой 15×15) разрезали по границам клеток на несколько частей и сложили из них квадрат 8×8. Каково наименьшее количество частей?
б) (7-8);Клетчатый квадрат 2k´2k;разрезали по границам клеток на несколько частей и сложили из них квадратную рамку толщиной в одну клетку. Каково наименьшее число частей?;(А. Шаповалов)
35.;(7-9) Есть 2n;человек:;n;болеют за «Спартак» и;n;– за «Динамо». Разрешается спросить у любых двоих, болеют ли они за разные команды, и они честно ответят «Да» или «Нет». Требуется посадить болельщиков в два автобуса так, чтобы в каждом были болельщики только одной команды. За какое минимальное количество вопросов это наверняка можно сделать? (И. Раскина)
36.;(8) На столе лежат 10 кусков сыра. Петя съедает самый маленький (по весу) кусок. Затем он режет один из оставшихся на столе кусков на две части и снова съедает самый маленький из получившихся 10 кусков. Эти действия – разрезание и съедение куска – Петя повторяет, пока не съест 9 кусков. Докажите, что Петя съест не более половины сыра (по весу). (А. Шаповалов)
Взвешивания
37;–;41
37.;(6-7);Есть 100 гирек массами 1 г, 2 г, ..., 100 г. Заяц положил на одну чашу весов две гирьки. Волк хотел двумя другими гирьками уравновесить их, но не смог. Какие гирьки мог взять Заяц? (А.Шаповалов)
38.;(6-7) Есть одна золотая, 3 серебряных и 5 бронзовых медалей. Известно, что одна из них фальшивая: легче настоящей. Настоящие медали из одного металла весят одинаково (а из разных – не одинаково). Как за два взвешивания на чашечных весах без гирь найти фальшивую медаль? (А. Шаповалов)
39.;(6-8) Есть 63 одинаковых с виду монеты, из них одна фальшивая, легче настоящей. Есть чашечные весы без гирь, у которых правая чаша вымазана краской. Как за 5 взвешиваний выявить фальшивую монету, если монеты, побывавшие на правой чаше, нельзя после этого класть на левую? (А. Шаповалов)
40.;(6-8);Было восемь гирек с весами 1 г, 2 г, ..., 8 г. Одна из них потерялась, а остальные выложили в ряд по возрастанию веса. Есть электронные весы с лампочкой, которые проверяют только, есть равновесие на двух чашах весов или его нет. Как за три взвешивания определить, какая именно гирька потерялась? (А. Шаповалов, по мотивам)
41.;(6-9);В кассе купца Калашникова впервые за долгое время появились деньги – 27 монет: 9 копеек, 9 «двушек» и 9 «пятаков». Стало известно, что одна из них – фальшивая, легче настоящей (а настоящие весят соответственно 1, 2, и 5 г). Разгневанные работники требуют немедленной выдачи зарплаты, причем настоящими монетами. У приказчика есть чашечные весы без гирь. Как только становится ясно, что какие-либо монеты – настоящие, они выплачиваются работникам и, естественно, в дальнейших взвешиваниях не участвуют. Сможет ли приказчик наверняка выявить фальшивую монету за три взвешивания? (А. Шаповалов)
Турниры
42;–;48, а также;8Т1, 8Т2, 8Т3, 8Т4, 8Т5
42.;(6-8);а);В групповом турнире чемпионата по футболу участвовали 4 команды. «Чистое» второе место заняла команда, набравшая 3 очка. Восстановите результаты всех матчей.
б);В однокруговом футбольном турнире участвовало;n;команд. При каких;n;«чистое» второе место могла занять команда, набравшая;n;– 1 очко?
(«Чистое» второе место означает, что больше нет команд, набравших столько же очков,;и есть ровно одна команда, набравшая больше очков; выигрыш – 3 очка, ничья – 1 очко, поражение – 0.) (А. Блинков)
43.;(6-8);В однокруговом волейбольном турнире участвовали 14 команд.;Интересной;назовем команду, выигравшую нечетное число матчей, а;особенной;– команду, выигравшую нечетное число матчей у интересных. Докажите, что число особенных команд четно. (С. Токарев)
44.;(6-7);Несколько футбольных команд сыграли турнир в один круг. За победу команда получала 3 очка, за ничью – 1, за проигрыш – 0. После окончания турнира одну из команд дисквалифицировали, а все очки, набранные в матчах с ней, аннулировали. Могла ли команда, сначала занимавшая чистое первое место, стать абсолютно последней? (А. Заславский)
45.;(6-8);Петя составил расписание шахматного турнира для восьми человек (каждый играет с каждым, в каждом туре одновременно играются 4 партии). У какого наибольшего количества игроков цвета фигур от тура к туру могут строго чередоваться? (А. Шаповалов)
46.;(6-8) В однокруговом турнире участвовали 12 шахматистов. Какое наименьшее количество дней может длиться этот турнир, если каждый его участник играет не более одной партии в день, и никакие две партии подряд не играет черными фигурами? (А. Грибалко, С. Токарев)
47.;(7-8);Команды провели турнир по футболу в один круг (каждая сыграла с каждой один раз, победа – 3 очка, ничья – 1, поражение – 0). Оказалось, что у единоличного победителя количество побед меньше, чем количество поражений. Какое наименьшее количество команд могло участвовать в турнире? (А. Блинков, А. Заславский)
48.;(6–8);В круговом футбольном турнире за победу команда получала 2 очка, за ничейный результат – 1 очко, за поражение – 0 очков. Количество очков, набранных в итоге командами, попарно различно. Какой наименьший разрыв мог получиться между первой и последней командами? В турнире участвовало
а);10 команд
б);n;команд. (А. Блинков)
Процессы
49;–;63, а также;7К2, 7Ц4,;39,;112
49.;(6);На классной доске написали два числа: с левой стороны – 2011, а с правой – 1000. За один ход можно прибавить к числу, написанному с левой стороны, некоторое натуральное число, а число, написанное с правой стороны, умножить на то же самое число. Можно ли уравнять числа на разных сторонах доски, сделав не более 1000 ходов? (Олимпиада Кукина, 2011)
50.;(6-7);Десять гномов вместе выпивают ведро молока за минуту. Каждый гном пьет молоко с некоторой постоянной скоростью, но скорости у разных гномов могут быть разные. Докажите, что если разлить молоко поровну в 10 бутылок, то гномы тоже смогут управиться с ним за минуту. (Из каждой бутылки в каждый момент может пить только один гном, но разрешается любое число раз обмениваться бутылками, обмен происходит мгновенно). (И. Рубанов, Уральский турнир)
51.;(6-7);В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Можно ли собрать всю воду в одном ведре? (26-й;Уральский турнир)
52.;(8-9);100 монет достоинствами в 1, 2, 3, ..., 100 пиастра разложили в 76 кошельков (в каждом что-то есть). Разрешается объединять все деньги из любых двух кошельков в один. Докажите, что такими объединениями можно оставить только два непустых кошелька с равными суммами денег.;(А. Шаповалов)
53.;(6-7);На доске в ряд выписаны 10 натуральных чисел. За одну операцию разрешается увеличить на 1 любые три рядом стоящих числа. Всегда ли можно за несколько операций добиться, чтобы все числа делились на 4? (Колумбия-2004)
54.;(6-8);В языке КОКОКОЛО 3 буквы: К, Л и О. Если в любом месте любого слова этого языка вставить или вычеркнуть любое из буквосочетаний ККО, ООЛ или ЛЛК, то смысл слова от этого не изменится. Одинаковы ли по смыслу слова КЛОК и КОЛОКОЛ? (А. Шаповалов)
55.;(6-8);По кругу расположены 30 монет, чередуясь: три подряд орлом вверх, три подряд – решкой, три – орлом, три – решкой и т.;д. Если у монеты две соседних лежат по-разному, ее можно перевернуть. Какое наибольшее число монет можно положить орлом вверх с помощью таких операций? (А. Шаповалов, Кубок Колмогорова)
56.;(6-7);В каждую клетку клетчатого квадрата 5´5 вписан 0. За одну операцию можно выбрать любую клетку, посчитать количество различных чисел в соседних с ней по стороне клетках и заменить число в клетке на полученный результат. Какое наибольшее число четверок одновременно можно получить такими операциями? (М. Лимонов,;А. Шаповалов)
57.;(6-7);Куб 10×10×10 составлен из черных кубиков 1×1×1. Сережа красит всю поверхность куба в красный цвет. Затем Ваня забирает себе сколько хочет кубиков, у каждого из которых ровно три грани оказались красными. После этого Сережа снова красит всю поверхность в красный цвет, а Ваня затем забирает такие же кубики по тому же правилу, и т.д. Может ли Ваня в итоге забрать себе все кубики? (Д. Калинин, Э. Акопян)
58.;(6-8);В кинотеатре 20 рядов по 25 мест в каждом,;и все места заняты. Если зритель чихнет во время сеанса, то он должен отдать каждому из своих соседей по рублю. В;начале у всех было одинаковое количество денег. Дима чихнул и расплатился. Какое наименьшее число раз должны еще чихнуть зрители, чтобы у всех снова стало поровну денег? (Соседями считаются сидящие спереди, сзади, слева и справа, у каждого зрителя может быть от двух до четырех соседей). (Д. Калинин)
59.;(7);В каждой клетке таблицы 10×10 находится указатель, который может быть направлен вверх, вправо, вниз или влево. В начальной позиции один из них указывает вниз, а остальные – вверх. Разрешается одновременно поворачивать на 90°;по часовой стрелке два указателя, находящиеся в соседних по стороне клетках. Докажите, что не удастся направить все указатели в одну сторону. (А. Грибалко)
60.;(6-7);У пяти пиратов 200 золотых монет – у всех разное количество. Двое пиратов, если у них разное число монет, могут провести обмен: сложить в кучку все имеющиеся у них монеты и поделить её пополам между собой, если это возможно. Капитан утверждает, что пиратам удалось распределить монеты поровну между собой ровно за три обмена. Прав ли он? (Г.;Кузнецов)
61.;(6-8);Круг разбит на 25 секторов, пронумерованными в произвольном порядке числами от 1 до 25. В одном из секторов сидит кузнечик. Он прыгает по кругу, каждым своим прыжком перемещаясь по часовой стрелке на количество секторов, равное номеру текущего сектора. Докажите, что в некотором секторе кузнечик не побывает никогда. (А. Грибалко)
62.;(6-8);а);В 10 кошельках лежали монеты. В каждом кошельке достоинства любых двух монет из этого кошелька отличались не более чем на 1 берендейку. Монеты смешали и положили в непрозрачный мешок. Саша про монеты заранее ничего не знает. Он вынимает по одной монете из мешка, смотрит на нее, кладет в одну из 19 имеющихся коробок,;и потом эту монету уже не перекладывает. Докажите, что Саша может действовать так, чтобы в каждой коробке достоинства любых двух монет отличались не более чем на 1 берендейку.
б) (7-8) В 10 кошельках лежали монеты так, что веса;любых двух монет из одного кошелька отличались не более чем на 1 г (веса монет могут быть нецелыми). Монеты смешали и положили в непрозрачный мешок. Саша про веса монет заранее ничего не знает. Он вынимает одну монету из мешка, взвешивает, затем кладет монету в одну из имеющихся 20 коробок, вынимает следующую монету и т.д. (Положив монету в коробку, потом ее уже нельзя переложить.) Докажите, что Саша может действовать так, чтобы в каждой коробке веса любых двух монет отличались не более чем на 1 г.
в) Как (б), но коробок 19. (А.Шаповалов)
63*.;(7-8);В ряд стоят несколько стаканов – вниз или вверх дном. За одну операцию разрешается выбрать стакан вверх дном и перевернуть его соседей (двух – если стакан не крайний, одного – если крайний; выбранный стакан не переворачивается). Докажите, что такими операциями можно из любого расположения стаканов получить симметричное ему (то есть такое же, но справа налево). (А. Лебедев, А. Шаповалов)
Игры
64;–;74, а также;87, 123, 125
64.;(6-7);Коля и Толя по очереди закрашивают по две клетки на полоске 1×2010. Коля хочет, чтобы расстояния между двумя отмеченными им за один ход клетками не повторялись. Сможет ли Толя ему помешать? (Н. Чернятьев)
65.;(8-9);Петя и Вася;по очереди ломают палку:;сначала Петя;– на две части (возможно,;неравные),;затем Вася;– одну из получившихся частей на две,;Петя;– одну из трех частей на две, и так далее. Выигрывает тот, кто сможет после своего;хода;выбрать из всех имеющихся частей;четыре;палки, длины которых образуют арифметическую прогрессию. Как закончится игра при наилучших действиях сторон? (А. Шаповалов)
66. (6-7);Имеется клетчатая доска 9×9 и фишка. Двое играют в следующую игру: первый своим ходом ставит фишку в произвольное место доски, а потом передвигает её в одну из соседних по стороне клеток. Далее они по очереди передвигают фишку на одну из соседних клеток, при этом нельзя ставить фишку туда, где она уже была. Проигрывает тот, кто не может сделать ход. Кто из игроков – первый или второй – может выиграть, как бы не играл противник? (Д. Калинин)
67.;(7-8);Дан клетчатый квадрат размером 8´8.;Петя и Вася;ходят по очереди. Первым ходом;Петя;разрезает;квадрат по прямой линии сетки на два меньших прямоугольника. Каждый последующий ход аналогичен: выбирается один из уже имеющихся прямоугольников и разрезается по прямой линии сетки на два меньших прямоугольника. Выигрывает тот, кто после своего хода сможет сложить из всех частей прямоугольник размером 2´32. Кто из игроков может выиграть, как бы ни играл соперник? (А. Шаповалов)
68. (6-8);Бесконечная клетчатая доска – плоскость, разбитая на треугольники, как это показано на рисунке. Двое играют в «крестики-нолики». Выигрывает тот, кто поставит четыре своих знака в ряд (см. рисунок). Если игра не заканчивается в течение 2011 ходов, объявляется ничья.
а);Может ли игрок, сделавший первый ход, выиграть при любой игре соперника?
б) Каков результат при наилучшей игре сторон?;(А. Банникова, Е. Пономарева)
69.;а);(6-7);На доске написаны числа от 1 до 30. Миша и Ваня ходят по очереди, начинает Миша. За один ход нужно заменить любые два числа на их произведение. Если одно из двух последних оставшихся на доске чисел делится на второе, то выигрывает Ваня, иначе – Миша. Кто из них может выиграть, как бы ни играл соперник?
б);(6-8);На доске написаны;числа от 1 до 102.;Миша и Ваня ходят по очереди, начинает Миша. За один ход нужно заменить любые два числа на их сумму. Если одно из двух последних оставшихся на доске чисел делится на второе, то выигрывает Ваня, иначе – Миша. Кто из них может выиграть, как бы ни играл соперник?;(Н. Чернятьев)
70.;(7-9);На доске написаны числа 1, 2, 3, …, 1001. Петя и Вася по очереди стирают по одному числу, пока на доске не останется только два числа;(начинает Петя). Если одно из них делится на второе, побеждает Петя, если нет – Вася. Кто из;них;может выиграть, как бы не играл соперник? (А. Шаповалов)
71.;(8) На доске записаны числа от 1 до 2011.;Петя и Вася;по очереди стирают по одному числу, пока не останутся два числа:;p;и;q.;Первым стирает Петя.;Если хотя бы;у;одного;из уравнений;x2;+;px;+;q;= 0; или;;x2;+;qx;+;p;= 0;;есть;целый корень, то;Петя;выигрывает. Сможет ли;Вася;ему помешать? (А. Шаповалов)
72.;(6-8);Есть 11 запечатанных коробок карандашей, в которых 10, 11, 12, ..., 20 карандашей (на каждой написано, сколько в ней).;Петя и Вася;берут себе по очереди по карандашу, пока не разберут все; начинает Петя. Каждый игрок в любой момент имеет право распечатать коробку, заплатив за это рубль сопернику. Кто и сколько рублей выиграет при наилучшей игре сторон? (А. Шаповалов)
73.;(6-8);а);На доску выписаны через запятую числа 1, 2, 3, …, 100.;Петя и Вася;по очереди заменяют какую-нибудь запятую на + или;´;(знак;умножения).;Первым;это делает;Петя.;Если после замены всех запятых результат будет чётным, выигрывает;Петя,;иначе;–;Вася. Кто из;них;может выигрывать, как бы не играл соперник?
б) То же для чисел 1, 2, 3, …, 2009. (А. Шаповалов)
74.;(7-9);Петя и Вася играют на шахматной доске в следующую игру. Каждым ходом игрок выбирает некоторую свободную клетку и проводит в ней обе диагонали – одну красным цветом, другую синим. Запрещается проводить диагональ так, чтобы она имела общий конец с уже проведенной диагональю такого же цвета. Проигрывает тот, кто не может сделать ход. Первым ходит Петя. Кто из них может выигрывать, как бы не играл;соперник? (А. Шаповалов)
75.;(6-8);Двум мудрецам – Петру и Василию – показали набор из 10 карточек с числами 1, 2, ..., 10, и выдали по карточке из набора с числами;a;(Петру) и;b;(Василию). Каждый знает только свое число. Мудрецы играют, по очереди называя;вслух натуральные числа, при этом каждое должно быть больше предыдущего и заведомо (для называющего) делить НОК(a,;b). Кто не может сделать ход, должен сдаться. Есть ли такая карточка, получив которую,;Петр (он ходит первым) может быть уверен в выигрыше?
Пояснение.;НОК(a,;b) игрокам изначально неизвестен. Однако они понимают, в частности, что;каждый;делитель числа на их карточке делит и НОК. В дальнейшем они могут делать выводы из того, что назвал соперник. (А. Шаповалов)
76*.;(7-9);В системе коридоров, показанной на рисунке, расстояние между каждыми двумя соседними развилками одно и то же. По коридорам бегает мышка, максимальная скорость которой – 7;м/c. За мышкой согласованно охотятся две кошки, могущие развивать скорость до;v;м/c. Все животные в каждый момент знают месторасположение друг друга. При каком наименьшем значении;v;кошки могут (независимо от начальных положений) гарантированно поймать мышку? (С. Токарев)
Графы
77;–;78, а также;3, 35, 58
77.;(7-8);Каждая дорога сети связывает два города (не заходя в другие), число дорог конечно, между каждыми двумя городами есть ровно один путь по дорогам (возможно, проходящий через другие города). Имеется ровно 20 тупиков (городов, из которых выходит ровно одна дорога). Маршрут автобуса проходит по кратчайшему пути между какими-то двумя городами, автобус ходит туда и обратно. Известно, что из любого города в любой другой можно доехать автобусами не более чем с одной пересадкой. Каково наименьшее число маршрутов (для любой такой сети)? (Б. Френкин)
78.;(7-8);В стране 6 городов. Каждые два города соединены авиалинией одной из двух авиакомпаний. Обязательно ли существует замкнутый маршрут из четырех авиалиний одной авиакомпании? (В. Трушков)
Обратный ход
7А1, 7А2, 60
Непрерывная комбинаторика
В этих задачах возникают комбинации из;конечного;числа объектов, но сами объекты выбираются из;бесконечного;набора, заданного;непрерывным параметром;или параметрами.
7К4,;36, 62, 65,;76,;119, 120, 127
Принцип крайнего
8К5,;27, 37,;116, 117
Арифметика и алгебра
Ребусы
79 – 81, а также 2
79. (6-7); КОЕ – ЧТО = 857.; На сколько; КТО – ТО; больше, чем; КОЕ – КТО?; (А. Хачатурян)
80.;(6-7);Решите ребус:; КВАНТ + КВАНТ = ТУРНИР.; (Э. Акопян)
81.;(6-7);У;Артура есть двое часов, идущих неправильно. Каждые показывают время четырьмя цифрами: часы (от 00 до 23) и минуты (от 00 до 59). В некоторый момент Артур обнаружил, что на часах горят 8 различных цифр. Какой может быть наибольшая сумма этих восьми цифр? (В. Гуровиц)