Классическая комбинаторика

См. также задачи 1, 32, 63, 69, 121, 220, 6К3, 6К4, 6Ч1, 6Ч3, 6Ч5, 7Т1, 7К2, 7К4, 8К1-3, 8К5, 9КГ1.

115. Набор из трёх палочек назовем хорошим, если из них можно сложить треугольник (то есть, сумма длин двух коротких больше длинной палочки).

а) (7-8) Есть 2007 палочек длин 1, 2, 3, ..., 2007. Каких наборов из них можно составить больше: хороших или не хороших?

б) (8) Найдутся ли не более 6000 палочек разной длины, из которых можно выбрать хороший набор ровно 2007 способами?

в) (9) Найдутся ли 25 палочек разной длины, из которых можно выбрать хороший набор ровно 2007 способами? (А. Шаповалов)

116. (8-9) Дан куб со стороной n > 1, где n – натуральное число. Сколькими способами его можно разбить на бруски размером 1×1×n? (Куб неподвижен, то есть различные способы, которые при повороте куба совпадают, считаются различными.) (В. Брагин)

117. (8-9) На клетчатой доске n×n выделены поля большой диагонали из верхнего левого угла в правый нижний. За одну операцию разрешается выбрать любую клетку на диагонали, поставить по шашке на все пустые клетки слева от нее и снять все шашки с клеток под ней. Какое количество различных расположений шашек можно получить такими операциями из пустой доски? (Пустая доска тоже считается за одно расположение.) (П. Грозман)

 

Дискретная непрерывность

См. также задачу 133.

118. (6) На каждом листе тетради из 96 листов Дима нарисовал страшную рожу. Рисунок был либо с одной стороны листа, либо с другой, причем если Дима положит тетрадь на стол, то некоторые рожи будут «смотреть» вверх (на Диму), а остальные – вниз (в стол). Верно ли, что можно раскрыть тетрадь в таком месте (или вообще ее не открывать), чтобы вверх и вниз «смотрело» одинаковое количество рож? (И. Акулич)

 

Индукция

См. также задачи 117, 184, 216, 8Г1, 8К5, 8М5, 9П5.

119. Из колоды отложили часть карт. Докажите, что оставшиеся можно разделить между двумя игроками так, чтобы у них общее число карт, число карт каждой масти и число карт каждого достоинства отличалось не более, чем на 1. (А. Шаповалов)

 

Примеры и оценки

См. также задачи 2, 3, 6, 8, 10, 16, 18в, 19, 20, 22, 24, 28, 29, 30, 31, 36, 39, 46, 56, 57, 58, 64, 106, 144, 145, 150, 151, 152, 156, 157, 158, 161, 162, 163, 167, 168, 172, 174, 175, 184, 186, 191, 196, 198, 199, 203, 204, 206, 218, 219, 220, 221, 222, 6Ц3-4, 6К1, 6К5, 6Ч2, 7А1, 7А4, 7Т2-3, 7Т5, 7К5, 7П3, 7П5, 8Ал2-3, 8Г1, 8Ар5, 8К4, 8М1-5, 9П1-2, 9КГ2, 9КГ4-5,9Т2, 9Т4-5.

120. (7-9) Кузнец Емельян сделал набор из четырёх железных и одной золотой гирьки, где золотая по весу не меньше каждой из железных. Известно, что любой целый вес от 1 г до 10 г можно набрать одной или несколькими гирьками набора. Какое наименьшее количество золота мог потратить кузнец? (А.Шаповалов)

121. (7-9) а) Девять гномов трижды становились по одному в клетки квадрата 3×3, и каждый раз гномы, оказавшиеся в соседних по стороне клетках, здоровались. Докажите, что какие-то два гнома так и не поздоровались.

б) Сколько раз можно расставить числа от 1 до 9 в клетки квадрата 3×3 так, чтобы каждые два числа оказывались в соседних по сторонам клетках не более одного раза? (А. Грибалко)

122. (7-9) На числовой прямой отмечены все целые точки. Точки x и y соединяются дугой, если |x – y| – простое число. В какое наименьшее количество цветов можно покрасить все целые точки, так чтобы каждые две соединенные точки были разного цвета? (Фольклор)

123. (7-8) Каждый из членов Мирового Правительства знает по два языка и может общаться без переводчика со всеми своими коллегами, кроме одного. Сколько членов может насчитывать Правительство? (С. Токарев)

124. (7-8) а) Есть две кубические коробочки (без крышек), которые плотно вкладываются друг друга, как бы мы их не повернули. На всех 12 ребрах каждой из этих коробочек расставлены стрелки. Может ли оказаться, что при любом вложении одной коробочки в другую на примыкающих ребрах совпадут направления ровно 6 стрелок?

б) То же, но коробочек три.

в) Куб плотно лежит в коробке без крышки. На всех рёбрах куба и всех рёбрах коробки нарисованы стрелки. Известно, что как ни положить куб в коробку, на примыкающих ребрах совпадут направления ровно n стрелок. Чему может быть равно n? (А. Блинков, И. Раскина)

125. (8) В одном из судиславских городских автобусов недавно была введена новая форма оплаты проезда. Пассажиры приобретают талон, имеющий форму круга, разбитого на 13 равных секторов. Одна сторона талона покрашена в синий цвет, а другая – в жёлтый. При входе в автобус они вставляют талон в электронный компостер синей стороной вверх, и компостер пробивает несколько секторов, предварительно проверяя, что эти секторы не были пробиты ранее. Какое наименьшее количество секторов должен пробивать компостер, чтобы один и тот же талон нельзя было использовать дважды? (А. Акопян)

 

Алгоритмы

См. также задачи 53, 54, 57, 62, 115, 122, 139, 149, 151, 154, 155, 157, 158, 164, 165, 166, 177, 178, 210.

126. (6-7) Три человека со стиральной машиной хотят переправиться через реку. Катер вмещает либо двух человек и стиральную машину, либо трёх человек. Беда в том, что стиральная машина тяжёлая, поэтому погрузить ее в катер или вытащить из него можно только втроем. Смогут ли они переправиться? (Д. Шаповалов)

127. (7-8) Три жулика, каждый с двумя чемоданами, хотят переправиться через реку. Есть трёхместная лодка, каждое место в которой может быть занято человеком или чемоданом. Никто из жуликов не доверит свой чемодан спутникам в свое отсутствие, но готов оставить чемоданы на безлюдном берегу. Смогут ли они переправиться? (Лодку, приставшую к берегу, считаем частью берега.) (А. Шаповалов)

128. Большая свеча сгорает за час и стоит 60 рублей, а маленькая сгорает за 11 минут и стоит 11 рублей. Можно ли отмерить минуту, затратив не более, чем

а) 200 рублей; б) 150 рублей? (А. Шаповалов, Л. Медников)

129. На Мишином плеере при нажатии кнопки «вперёд» номер текущей песни увеличивается, но не более, чем на 2, а при нажатии кнопки «назад» – уменьшается не более, чем на 2. Переходы на каждую из возможных песен происходят с ненулевой вероятностью (если достаточно много раз нажать на кнопку, начав с одной и той же песни, то каждый переход случится хотя бы один раз). Миша нажал кнопку «вперёд», и песня сменилась. Как ему узнать, на сколько увеличился номер песни? Разрешается сколько угодно жать на кнопки, но нельзя просто дослушать песню и подождать, что будет дальше. (Известно, что песни, о которых идет речь, расположены «достаточно далеко» от концов ленты.) (М. Артемьев)

130. Есть m тортов, каждый из которых имеет вес 1. Мы хотим разделить их поровну между n школьниками (m < n). Докажите, что это всегда можно сделать так, чтобы каждый кусок, получившийся при дележе, весил не меньше m/3n. (К. Кноп, И. Богданов)

 

Взвешивания

131. (6-7) Есть 12 внешне одинаковых монет двух сортов, по 6 каждого сорта, За одно взвешивание про любую группу можно узнать, сколько в ней монет первого сорта. Как за два взвешивания найти пару монет разного сорта? (Какая из них какого сорта выяснять не надо.) (А. Шаповалов)

132. (6-7) В наборе 7 гирь. Арбуз можно уравновесить тремя гирями, можно четырьмя, а можно и пятью. Докажите, что одну из гирь набора можно уравновесить несколькими другими. (А.Шаповалов)

133. (8-9) В ряд лежат 300 апельсинов, веса соседних отличаются не более чем на 10 г. Докажите, что их можно разложить в пакеты по 3 штуки и положить пакеты в ряд так, чтобы веса любых двух соседних пакетов отличались не более чем на 10 г. (А. Шаповалов)

134. (8-9) Есть 10 яблок, каждое из которых весит не более 100 г, и две одинаковые тарелки. Докажите, что

а) можно выбрать какое-то количество яблок и положить их в одну или обе тарелки так, чтобы веса в тарелках отличались меньше, чем на 1 г.

б) можно положить в тарелки по одинаковому количеству яблок так, чтобы веса в тарелках отличались меньше, чем на 2 г. (А. Шаповалов)

135. (6-8) В ряд лежат 5 монет. Известно, что две из них фальшивые (одного веса и легче настоящих). Как за два взвешивания на чашечных весах без гирь определить, сколько настоящих монет лежит между фальшивыми? (А. Шаповалов)

136. (7-8) Есть 10 внешне одинаковых монет. Суд знает, что их веса 1 г, 2 г, ..., 10 г. Эксперт знает точный вес каждой монеты. У него есть весы с двумя чашками, которые показывают равновесие (загорается лампочка) или неравновесие, но не показывают, какая чаша тяжелее. Может ли эксперт провести три взвешивания так, чтобы по их результатам суд мог однозначно определить вес каждой монеты? (А. Шаповалов)

137. (7-8) На столе в ряд лежат шесть монет. Среди первых четырёх есть ровно одна фальшивая монета, среди последних двух – тоже одна фальшивая. Настоящие монеты весят одинаково, фальшивые тоже весят одинаково и легче настоящих.

а) Можно ли за два взвешивания на чашечных весах без гирь определить обе фальшивые монеты?

б) Импортные чашечные весы сообщают результат взвешивания на следующий день. Можно ли сегодня провести такие два взвешивания, чтобы завтра по полученным результатам наверняка определить обе фальшивые монеты? (В. Трушков)

138. а) (7-8) Гирьки весом 1, 2, 3, ..., 40 граммов разложили на две чашки весов так, что есть равновесие. Докажите, что можно убрать с чаш три гирьки так, чтобы равновесие не нарушилось. (А. Шаповалов)

б) (8-9) То же для гирек от 1 до n граммов, где n > 4.

139. (7-8) Ире принесли семь драгоценных камней разного веса. Прибор «РИВ-6» умеет за одно испытание из шести камней выбрать два средних по весу.

а) Как за пять испытаний Ира сможет найти самый средний по весу камень из семи?

б) За какое минимальное число применений прибора она гарантированно сможет найти средний по весу камень? (В. Трушков, И. Руденко)

 

Клетчатые задачи

См. также задачи 121, 7К4, 9КГ1, 9КГ3, 9Т2, 9Т4-5.

142. (7-8) Из шахматной доски 8×8 вырезали центральный квадрат 2×2 (поля d4, e4, d5, e5). Можно ли оставшуюся часть разрезать на фигурки в виде буквы Г (состоящие из четырёх квадратиков)? Фигурки разрешается поворачивать и переворачивать. (В. Шарич)

143. (7-8) При каких n квадрат n×n можно разбить на трёхклеточные уголки и правильно их раскрасить в два цвета? (Раскраска называется правильной, если уголки, имеющие общую границу ненулевой длины, раскрашены в разные цвета.) (М. Артемьев)

144. (7) Есть клетчатая рамка 10×10 толщиной в одну клетку (см. рис.). Ее разрезали по границам клеток на различные части и сложили из них квадрат 6×6. Каково наибольшее число частей? (А. Шаповалов)

145. (7) Галя вышивает крестиком узор на квадрате 10×10. Она считает узор красивым, если он центрально-симметричен и при этом каждые два крестика одного цвета соединены цепочкой крестиков того же цвета с общими сторонами. Какое наибольшее число цветов сможет использовать Галя? (И. Раскина, А. Артемьев)

1147. (6-7) Карандаш раскрасил деревянный кубик в соответствии с развёрткой (на рисунке в центре цифры означают цвета). Самоделкин распилил его на 8 кубиков, у каждого получились три грани окрашены, а три – нет. Он составил кубики обратно в виде куба, вся поверхность которого окрашена. Гурвинек смотрит на кубик и видит, конечно, не все грани, а только три, повёрнутые к нему (рис. справа). Но он утверждает, что знает, какой кубик лежит в дальнем от него углу. Какой? (Кукинская, 2011)

148. (6-7) Можно ли в таблице 3×3 расставить числа от 1 до 9 так, чтобы сумма чисел в каждых трёх клетках, никакие две из которых не лежат на одной вертикали или горизонтали, равнялась 15? (Д. Калинин)

149. (7-9) а) Можно ли в клетках таблицы 12×12 расставить натуральные числа от 1 до 144 так, чтобы суммы чисел во всех вертикалях, всех горизонталях и обеих диагоналях были нечётными?

б) То же для таблицы 100×100 и чисел от 1 до 10000. (В. Берник, И. Акулич)

150. а) (6) Есть лист клетчатой бумаги и карандаши шести цветов. Какое наименьшее число клеток надо закрасить так, чтобы для любых двух разных цветов нашлась закрашенная в них пара клеток с общей стороной?

б) (7) То же для карандашей 10 цветов.

в) (8-9) То же для карандашей 7 цветов. (С. Токарев)

151. (6-8) а) На шахматную доску по одной выставляются чёрные и белые ладьи в любом порядке. В момент выставления ладья должна побить поровну белых и чёрных ладей (например, не бить никого). Какое наибольшее количество ладей может быть выставлено? (Ладьи бьют друг друга, если стоят на одной вертикали или горизонтали, и между ними нет других ладей.)

б) То же, но ладьи выставляются только на край шахматной доски. (А. Шаповалов)

152. (7-8) Могут ли 7 слонов побить все клетки доски 4×10? (А. Шаповалов)

153. (7-8) Можно ли кубик Рубика 8×8×8 оклеить без щелей и перекрытий прямоугольниками 1×2 так, чтобы каждый прямоугольник заклеивал ровно две клетки и у всех было

а) ровно 6 соседей?

б) одинаковое четное число соседей?

(Соседи имеют общую границу ненулевой длины. Перегнутый прямоугольник может закрывать две клетки на соседних гранях.) (А. Шаповалов)

154. (7-8) В прямоугольной таблице клетки нумеруются по порядку: сначала первая строка слева направо, затем вторая строка слева направо и т. д. Барон Мюнхгаузен готов для каждого nпредъявить такую таблицу, разрезанную на n многоугольных частей с равными суммами номеров в каждой части. Не хвастает ли барон? (А. Шаповалов)

155. (8-9) Клетки доски m×n раскрашены в шахматном порядке в чёрный и белый цвет. Разрешается выбрать любые две соседние по стороне клетки и перекрасить их: белые клетки – в чёрный цвет, чёрные – в красный, а красные – в белый. При каких m и n можно добиться того, чтобы все белые клетки доски были покрашены в чёрный цвет, а чёрные – в белый? (М.Ахмеджанова, К. Кохась)

156. (7-8) В левом нижнем углу шахматной доски стоит шашка. Ее можно передвигать на одну клетку вверх, либо на одну клетку вправо, либо на одну клетку по диагонали вниз-влево. Можно ли, двигая шашку таким образом, обойти все клетки доски, побывав на каждой из них один раз? (Фольклор)

157. (7-9) а) Художник-абстракционист хочет раскрасить клетки доски 8×8 в три цвета так, чтобы выполнялось условие: если у клетки k есть два соседа p и q одного цвета, то у k есть ещё два соседа одинакового цвета, но не такого, как у p. Сможет ли он это сделать? (Соседями считаем клетки с общей стороной.)

б) При каких m художник сможет так раскрасить доску в m цветов? (Е. Барабанов, И. Акулич)

158. (7-8) Петя по одной выставляет ладьи на пустые клетки доски 5×5. За каждую ладью, которая в момент выставления может побить ладей не меньше, чем пустых полей, Петя получает рубль. Какое наибольшее количество рублей сможет заработать Петя? (Ладья бьет другую ладью или клетку, если между ними нет других ладей.) (А. Шаповалов)

159. (6-7) На шахматную доску поставили три коня и три ладьи так, чтобы каждая фигура била ровно одну другую и была побита ровно одной другой. Докажите, что кони друг друга не бьют. (А. Шаповалов)

160. (7-8) На доске 10×10 стоят 20 фишек с номерами 1, 1, 2, 2, …, 10, 10. На каждую вертикаль и на каждую горизонталь попали по две фишки. Может ли для каждой пары фишек с одинаковыми номерами кратчайший путь ладьи между ними быть равен их номеру? (Сторона клетки равна 1). (А. Грибалко)

161. (7-9) Есть обычный комплект домино из 28 доминошек. Каждая доминошка в точности накрывает две клетки шахматной доски. Можно ли уложить весь комплект так, чтобы в каждой паре клеток с общей стороной, накрытых разными доминошками, были одинаковые цифры? (Комплект домино – это набор из 28 прямоугольников 1×2, в каждой клетке которых написана одна из цифр от 0 до 6, причём каждая пара цифр встречается ровно на одной доминошке. При выкладывании комплекта 8 клеток останутся не накрыты.) (А. Шаповалов)

162. (7-8) В угловой клетке шахматной доски 100×100 стоит фишка. За один ход разрешается передвинуть ее на соседнюю клетку по горизонтали, вертикали или диагонали так, чтобы при этом расстояние от центра начальной клетки до центра той, в которой находится фишка, постоянно увеличивалось. Какое наибольшее число ходов можно сделать, соблюдая это условие? (А.Грибалко)

163. (7-9) Муравей стартовал из угла шахматной доски. Ему разрешено пересекать каждую клетку по диагонали, запрещено бывать внутри одной клетки дважды, запрещено выходить за пределы доски и ползать вдоль границ клеток. Внутри какого наибольшего числа клеток он может побывать? (А. Шаповалов)

164. (7-9) Куб n×n×n состоит из n³ кубических клеток. Хромая ладья одним ходом передвигается на одну клетку в любом параллельном ребрам куба направлении, причем никакие два шага подряд она не делает в одном направлении. Замкнутый маршрут хромой ладьи прошел через все клетки по разу.

а) Возможно ли это при n = 4?

б) При каких n > 1 это возможно? (А. Шаповалов, О. Крижановский)

165. (8-9) Трёхмерная доска 18×18×18 состоит из кубических клеток. Параллельные граням слои считаются плоскими досками 18×18. Шахматный слон ходит по диагонали в любой из этих плоских досок. Докажите, что если слон может попасть из клетки A в клетку B, то он может сделать это не более чем за 3 хода. (М. Артемьев, К. Кноп, А. Шаповалов)

 

Турниры

В шахматных турнирах дается 1 очко за победу, ½ – за ничью, 0 – за поражение. В футбольных турнирах дается 3 очка за победу, 1 – за ничью, 0 – за поражение. В однокруговом турнире каждый участник играет с каждым другим ровно один раз.

См. также задачи 7Т1-5.

166. (6-7) В турнире участвуют 64 боксера разной силы. Можно ли за 70 боёв выявить двух сильнейших?

167. (7-8) После окончания чемпионата мира по футболу для каждой команды посчитали отношение числа голов, забитых ею с пенальти, к числу пробивавшихся ею пенальти и отношение числа голов, пропущенных с пенальти, к числу пенальти, пробитых в ее ворота. Может ли у всех команд первый показатель быть меньше второго? (А. Заславский)

168. (7-9) В однокруговом футбольном турнире участвовало 20 команд. Оказалось, что если какие-то две команды сыграли между собой вничью, то хотя бы одна из них завершила вничью не больше трёх игр. Каково наибольшее возможное число ничьих в таком турнире? (И. Акулич)

169. (6-7) Групповой турнир ЧЕ по футболу был проведен для четырёх команд в один круг. В итоговой таблице команды расположились так, что у каждой, начиная со второй, ровно на 1 очко меньше, чем у предыдущей. Восстановите исходы всех матчей. (А. Блинков)

170. (6-7) В Лиге Чемпионов стран Балтии участвуют шесть футбольных команд (по две от каждой страны – Латвии, Литвы и Эстонии). Они должны провести турнир в один круг (причем все три матча каждого тура проходят одновременно). Можно ли так составить расписание туров, чтобы для обслуживания каждого тура приглашать ровно по одной судейской бригаде из каждой страны? (Например, бригада из Латвии может судить либо матч двух латвийских команд, либо матч, в котором латвийские команды не играют). (А. Блинков)

171. (6-7) В однокруговом шахматном турнире у каждого из игроков чего-нибудь было столько, сколько у остальных вместе, в частности у Оси – очков, у Нины – ничьих (в одной был пат), у Проши – проигрышей, а у Зины – забавных ходов. Восстановите результаты всех партий. (А. Шаповалов)

172. (6-7) В однокруговом турнире по футболу все команды набрали разное число очков.

а) Могло ли случиться, что разность забитых и пропущенных мячей у каждой команды тем больше, чем меньше сумма очков?

б) При каком наименьшем числе ничьих такое могло случиться?

в) При каком наименьшем числе команд такое могло случиться? (А. Заславский, А. Шаповалов, Б. Френкин)

173. (8-9) После нескольких игровых дней однокругового турнира выяснилось, что любые пять команд можно так расположить по кругу, чтобы каждая сыграла со стоящими справа и слева. Докажите, что чемпионат можно завершить в три дня (в один день команда может сыграть не более одной игры). (C. Волчёнков)

174. (7-8) В однокруговом турнире по футболу принимали участие 6 команд. По итогам турнира каждая команда, начиная со второй, набрала на 2 очка меньше, чем предыдущая. Как сыграли между собой команды, занявшие третье и последнее место? (А. Грибалко)

175. (7-8) От футбольного турнира 18 команд в один круг осталась только таблица с общим количеством забитых и пропущенных мячей: 18 – 18, 17 – 1, 16 – 2, 15 – 3, ...,
1 – 17. Докажите, что была хотя бы одна ничья. (А. Шаповалов)

176. (6-7) В однокруговом чемпионате по матбоям участвовали 16 команд из 16 разных школ. Каждый бой проходил в одной из школ-участниц. В газете написали, что каждая команда сыграла во всех школах, кроме своей. Докажите, что журналисты ошиблись. (Ю. Лифшиц, Уральский турнир)

 

 

Процессы

См. также задачи 7П1-5, 8Г1.

177. (6-7) В водоеме плавало 2007 щук и 2007 акул. Акула может съесть щуку, если та до этого съела чётное число акул. Щука может съесть акулу, если та до этого съела нечётное число щук. (Съеденное мгновенно переваривается.) Акулы не едят акул, а щуки – щук. Могло ли так случиться, что в водоеме осталась только одна рыба? Какая? (И. Богданов)

179. (6-9) а) Колонна солдат-новобранцев выстроилась несколькими одинаковыми шеренгами, составляющими прямоугольник. По команде «смирно» некоторые из них с перепугу сделали поворот направо, другие – налево, третьи – кругом, а кое-кто вообще остолбенел и остался неподвижен. Далее через каждую секунду происходит следующее: в каждой паре, оказавшейся лицом к лицу, один из солдат делает поворот направо. Верно ли, что повороты рано или поздно прекратятся?

б) Докажите, что если в каждой паре, оказавшейся лицом к лицу, делают поворот направо оба солдата, то со временем повороты прекратятся. (И. Акулич)

180. (7-8) В ряд записаны несколько различных натуральных чисел. Назовем пару рядом стоящих чисел плохой, если они одной чётности и левое больше правого, либо они разной чётности и левое меньше правого. Каждую минуту числа какой-нибудь из плохих пар меняются местами. Докажите, что рано или поздно такие перестановки прекратятся. (А. Шаповалов)

181. (7-8)Откопавкладиз100алмазов,каждыйизсемигномовсхватилалмазов,сколькоуспел.Когдауодногоизгномовалмазовменьше,чемукаждого из остальных,онобижается,ивсеостальные,подревнемуобычаю,должныотдатьемупоодномуалмазу.Этотпроцесснадоповторять,покакто-либоизгномовобижается.Докажите,чтопеределсобственностираноилипозднозакончится.(А. Артемьев, И. Раскина)

б) То же для клада из 2012 золотых монет.

182. (8-9) На доске записаны числа 1, 2, 4, 8, ..., 512. Разрешается стереть любые два числа и записать вместо них частное от деления их произведения на их сумму. Докажите, что число на доске после девяти операций не зависит от порядка выбора чисел, и найдите это число. (А. Шаповалов)

183. (8-9) Саша разрезал головку сыра на 10 кусков и съел самый маленький кусок. Потом он разрезал один из кусков на два и съел самый маленький кусок из десяти. Эту операцию (разрезание и съедение) он сделал еще один раз. Какую наибольшую долю головки мог съесть Саша? (А. Шаповалов)

184. (7-9) За одну операцию разрешается в треугольнике изменить длину одной из сторон (но так, чтобы он остался треугольником). (А. Шаповалов)

а) Докажите, что за 3 операции треугольник можно превратить в любой другой треугольник того же периметра.

б) Докажите, что за 12 операций можно из правильного треугольника со стороной 1 сделать правильный треугольник со стороной 40.

в) За какое наименьшее число операций можно из правильного треугольника со стороной 100 сделать правильный треугольник со стороной 1? (А. Шаповалов)

 

Игры

См. также задачу 200.

185. а) (6) На длинном столе в ряд лежат 100 кучек по одному ореху. Первый и второй ходят по очереди. За ход нужно найти какие-нибудь две соседние кучки (то есть без кучек между ними), где правая не меньше левой, и объединить их в одну. Тот, кто делает последний ход, выигрывает. Кто из играющих сможет выиграть, как бы ни играл противник?

б) (7) На длинном столе в ряд лежат 2007 кучек по одному ореху. Первый и второй ходят по очереди. За ход нужно найти какие-нибудь две соседние кучки, где правая не меньше левой, и объединить их в одну. Тот, кто делает последний ход, выигрывает, и получает последнюю созданную им кучку. Какое наибольшее число орехов может гарантированно получить победитель? (С. Усов)

186. (6-7) На некоторых клетках прямоугольной клетчатой доски лежит по одному бобу, причём на каждой горизонтали и на каждой вертикали число бобов одно и то же (больше одного). Гарик и Вера ходят по очереди, начинает Гарик. За ход можно снять с доски любой боб. Если образуется пустая вертикаль, выигрывает Вера, если горизонталь – Гарик, а если горизонталь и вертикаль одновременно, то ничья. Докажите, что Вера всегда сможет выиграть. (В. Гурвич)

187. (6-8) Есть три кучки из 2005, 2006 и 2007 камней. Петя и Вася ходят по очереди, начинает Петя. За один ход можно взять два камня, по одному из каких-нибудь двух кучек. Кто не может сделать ход – проиграл. Кто из ребят может выиграть, как бы ни играл соперник? (Д. Калинин)

188. (6-8) Перед Петей и Васей лежат кучки по 100 монет. Ребята ходят по очереди, начинает Петя. За один ход можно взять из чужой кучки одну или несколько монет и переложить в свою кучку. Каждым ходом надо перекладывать новое число монет. Кто не может сделать ход – проиграл. Кто из них может выиграть, как бы ни играл соперник?
(А. Шаповалов)

189. (6-7) На доске написаны натуральные числа от 1 до 27. Двое игроков по очереди вычеркивают по одному числу, пока не останется два числа. Если их сумма кратна 5, то выигрывает первый игрок, иначе – второй. Кто из игроков может выиграть, как бы ни играл соперник? (Фольклор)

190. (7-8) а) На всех полях доски 1×2011, кроме крайних, стоит по шашке. Петя и Вася ходят по очереди, начинает Петя. Ход – это прыжок шашки ровно через одну шашку на одно из свободных полей, перепрыгнутая шашка снимается. Центральная шашка отмечена. Выигрывает тот, кто снимет отмеченную шашку. Кто из игроков может выиграть, как бы не играл соперник? (Отмеченная шашка тоже может ходить.)

б) Игровое поле – бесконечная полоска шириной в одну клетку. На 100 клетках подряд стоит по шашке. Петя и Вася ходят по очереди, начинает Петя. Ход – это прыжок шашки ровно через одну шашку на одно из свободных полей, перепрыгнутая шашка снимается. Одна из двух центральных шашек отмечена. Выигрывает тот, кто снимет отмеченную шашку. Кто из игроков может выиграть, как бы не играл соперник? (Отмеченная шашка тоже может ходить.) (А. Шаповалов)

191. (7-9) Фома и Ерёма делят клад из 100 золотых и 100 серебряных монет. Сначала Фома раскладывает монеты в ряд в каком хочет порядке. Затем Ерема начинает делёжку. Он берёт первую монету из ряда и либо забирает ее себе, либо отдаёт Фоме. Затем Фома берет вторую монету из ряда и тоже либо забирает ее себе, либо отдаёт Ерёме. Так, чередуясь, они распределяют по порядку монеты. Как только у кого-то из них накапливается 100 монет, другой забирает все оставшиеся монеты. Какое наибольшее число золотых может гарантировать себе Фома? (А.Шаповалов)

192. (7-9) а) См. п. б, когда вначале было три куска сыра.

б) Фома и Ерёма делят несколько кусков сыра. Сначала Фома, если хочет, выбирает один кусок и режет его на два. Затем он раскладывает все имеющиеся куски на две тарелки (не обязательно поровну). После этого Ерёма выбирает одну тарелку, и они делят сыр на ней, беря себе по очереди по куску, первый Ерёма. Точно так же они делят и сыр со второй тарелки, только первым выбирает Фома. Докажите, что Фома всегда может действовать так, чтобы получить не менее половины сыра (по весу). (А. Шаповалов)

193. (8-9) Имеется куча из 2006! камней. Петя и Вася ходят поочередно, начинает Петя. За один ход из кучи разрешается взять не менее одного камня, но не более, чем ¹/₂₀₀₆ часть оставшихся в куче камней. Проигрывает тот, кто не может сделать ход. Кто из них может выиграть, как бы не играл соперник? (А. Гусаков)

194. (7-9) Есть 720 спичек, разложенных в 100 кучек. Петя и Вася ходят по очереди. Каждым ходом выбирается кучка, делится на две меньшие части, и эти части сливаются с двумя из оставшихся кучек. Игрок победит, если после его хода во всех кучках станет поровну спичек. Если же после его хода остались всего две кучки, и они не равны, игрок проиграл. Кто может выиграть, как бы не играл соперник? (А. Шаповалов)

 

Графы

См. также задачи 173, 221, 8К2.

196. (7-8) В некоторой компании каждые два человека с общим знакомым имеют разное количество знакомых. Доказать, что в этой компании есть человек, у которого только один знакомый. (Все знакомства симметричны, у каждого человека есть хотя бы один знакомый.) (С.Конягин)

197. (7-9) Про каждую пару депутатов думы известно, могут ли они работать вместе либо только дискутировать (при этом есть депутат, который с кем-то работает, а с кем-то дискутирует). Думу удалось разбить на две группы, где в одной все пары рабочие, а в другой – все дискуссионные. Оказалось, что при переходе любого депутата в другую группу свойство однотипности всех пар в группе нарушается. Докажите, что по-другому разбить думу на две такие группы («рабочую» и «дискуссионную») нельзя. (В. Гурвич)

198. (9) 15 аэропортов связаны авиалиниями в единую сеть, то есть из любого аэропорта можно перелететь в любой другой (возможно, с пересадками). Из этих аэропортов не менее 5 – ключевые: при закрытии любого из них единая сеть распадается. Каково наибольшее число авиалиний в такой сети? (Авиалинии двусторонние, беспересадочные, и между каждой парой городов есть не более одной авиалинии.) (В. Гурвич)

199. (7-8) В Тридевятом царстве имеется 2012 городов. Царь Горох хочет открыть некоторое количество двусторонних авиалиний между городами так, чтобы из каждого города выходило не более 11 линий и от каждого города можно было добраться до любого другого, сделав не более шести пересадок. Каким наименьшим количеством авиалиний можно обойтись?

200. (8-9) Дано конечное дерево с неокрашенными вершинами и ребрами. Петя и Вася играют, ходя по очереди, начинает Петя. Кто не может сделать ход – проиграл. Оба всегда играют наилучшим образом.

В первой игре они красили по одной неокрашенной вершине за ход, каждый в свой цвет. Первую вершину каждый выбирал произвольно, затем выбирал вершину, связанную ребром с вершиной своего цвета. Победил Вася.

Во второй игре они красят по одному неокрашенному ребру за ход, каждый в свой цвет. Первое ребро каждый выбирает произвольно, затем надо выбирать ребро, имеющее общий конец с окрашенным ребром своего цвета. Кто победит на этот раз? (Б. Френкин)

 

Чётность

См. задачи 5, 20, 22, 25, 26, 27, 30, 36, 49, 56, 59, 61, 72, 74, 97, 123, 142, 149, 153, 160, 163, 164, 176, 177, 180, 185, 187, 208, 6Ц3, 6Ц5, 6Ч4, 7А3, 7П1, 8Ар3, 9Т1.

 

Геометрия

Разрезания и клетки

См. также задачи 9Т1, 9Т3.

201. (6-7). Можно ли разрезать квадрат со стороной 1 на пять прямоугольников (не обязательно одинаковых) с периметром 2? (А. Шаповалов)

202. (6-7) а) Барон Мюнхгаузен разрезал квадрат на квадратики двух размеров и провел в каждом по одной диагонали. Он утверждает, что общая длина диагоналей маленьких квадратиков равна общей длине диагоналей больших. Могут ли слова барона быть правдой?

б) Домино – это прямоугольник, у которого одна сторона вдвое больше другой. Барон Мюнхгаузен разрезал квадрат на домино двух размеров и провел в каждом по одной диагонали. Он утверждает, что общая длина диагоналей маленьких домино в полтора раза больше общей длины диагоналей больших. Могут ли слова барона быть правдой?
(А. Шаповалов)

203. (6-7) Квадратный торт массой 900 г разрезали двумя прямолинейными разрезами, параллельными одной паре сторон, и двумя прямолинейными разрезами, параллельными другой паре сторон. Докажите, что Паша сможет выбрать из девяти получившихся кусков три, не имеющие общих сторон, суммарная масса которых не меньше 300 г. (Фольклор)

204. (7). Петя разрезал шахматную доску по границам клеток на части одинакового периметра. Оказалось, что не все части равны. Каково наибольшее возможное число частей? (А.Шаповалов)

205. (7-8) Нарисуйте фигуру, которую можно разрезать как на три равных треугольника, так и на четыре равных (совпадающих при наложении) четырёхугольника. (А. Шаповалов)

206. (7-8) Квадратное поле разбили на прямоугольные участки, проведя 66 прямых параллельно сторонам квадрата. Назовем участок завидным, если его площадь больше площади любого соседнего с ним по стороне участка. Каково наибольшее возможное число завидных участков? (В. Брагин)

208. (7-8) Из клетчатой бумаги по линиям сетки вырезали многоугольник. Всегда ли можно вырезать (тоже по линиям сетки) содержащий его прямоугольник того же периметра? (В.Сендеров)

209. (7-8) На клетчатой доске размера а) 3×10; б) 3×12 отметили 8 клеток так, что их центры являются вершинами двух прямоугольников со сторонами, параллельными краям доски. Докажите, что среди отрезков, соединяющих центры отмеченных клеток, найдутся три одинаковых. (А. Грибалко)

210. (7-9) Можно ли разрезать квадратный лист бумаги со стороной 1 м на 30 квадратов так, чтобы хотя бы один из квадратов имел сторону меньше 1 мм?

211. (8-9) Назовем треугольники сходными, если у них равны как минимум две из трёх сторон. Докажите, что найдется квадрат, который можно разбить на треугольники, сходные данному остроугольному треугольнику. (А. Шаповалов)

212. (8-9) Квадрат разрезан на равные треугольники. Обязательно ли у каждых двух треугольников найдутся параллельные стороны? (А. Шаповалов)

213. (8-9) Для каких натуральных N можно любой треугольник разбить на N треугольников, имеющих по равной медиане? (А. Шаповалов)