Олимпиадные задачи по теме «Комбинаторика» для 7 класса - сложность 3 с решениями
Клетки доски размером 5×5 раскрашены в шахматном порядке (угловые клетки – чёрные). По чёрным клеткам этой доски двигается фигура – мини-слон, оставляя след на каждой клетке, где он побывал, и больше в эту клетку не возвращаясь. Мини-слон может ходить либо в свободные от следов соседние (по диагонали) клетки, либо прыгать (также по диагонали) через одну клетку, в которой оставлен след, на свободную клетку за ней. Какое наибольшее количество клеток сможет посетить мини-слон?
Дана незамкнутая несамопересекающаяся ломаная из 37 звеньев. Через каждое звено провели прямую.
Какое наименьшее число различных прямых могло получиться?
На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.
Докажите, что у семи из них есть общий дедушка.
Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка <i>A</i> на плане) до своего отеля (точка <i>B</i>). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. <div align="center"><img align="absmiddle" src="/storage/problem-media/111897/problem_111897_img_2.gif"></div>
Каждая деталь конструктора "Юный паяльщик" – это скобка в виде буквы П, состоящая из трёх единичных отрезков. Можно ли из деталей этого конструктора спаять полный проволочный каркас куба 2×2×2, разбитого на кубики 1×1×1? (Каркас состоит из 27 точек, соединённых единичными отрезками; любые две соседние точки должны быть соединены ровно одним проволочным отрезком.)
На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся к моменту их ухода.
Какое наибольшее число людей могло остаться в конце?
Проведено три семейства параллельных прямых, по 10 прямых в каждом. Какое наибольшее число треугольников они могут вырезать из плоскости?
В некотором городе на каждом перекрёстке сходятся ровно три улицы. Улицы раскрашены в три цвета так, что на каждом перекрёстке сходятся улицы трёх разных цветов. Из города выходят три дороги. Докажите, что они имеют разные цвета.
В компании из 2<i>n</i> + 1 человека для любых <i>n</i> человек найдётся отличный от них человек, знакомый с каждым из них.
Докажите, что в этой компании есть человек, знающий всех.
Правильный треугольник разбит на правильные треугольники со стороной 1 линиями, параллельными его сторонам и делящими каждую сторону на <i>n</i> частей (на рисунке <i>n</i> = 5). <div align="center"><img src="/storage/problem-media/109703/problem_109703_img_2.gif"></div>Какое наибольшее число отрезков длины 1 с концами в вершинах этих треугольников можно отметить так, чтобы не нашлось треугольника, все стороны которого состоят из отмеченных отрезков?
В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из <i>N</i> авиакомпаний, причём из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из каждого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт <i>N</i> – 1 рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из каждого города можно долететь до любого другого.
Можно ли покрасить 15 отрезков, изображённых на рисунке, в три цвета так, чтобы никакие два отрезка одного цвета не имели общего конца? <div align="center"><img src="/storage/problem-media/109490/problem_109490_img_2.gif"> </div>
Кощей Бессмертный похитил у царя трёх дочерей. Отправился Иван-царевич их выручать. Приходит он к Кощею, а тот ему и говорит: "Завтра поутру увидишь пять заколдованных девушек. Три из них – царёвы дочери, а ещё две – мои. Для тебя они будут неотличимы, а сами друг дружку различать смогут. Я подойду к одной из них и стану у неё спрашивать про каждую из пятерых: "Это царевна?". Она может отвечать и правду, и неправду, но ей дозволено назвать царевнами ровно двоих (себя тоже можно называть). Потом я так же опрошу каждую из остальных девушек, и они тоже должны будут назвать царевнами ровно двоих. Если после этого угадаешь, кто из них и вправду царевны, отпущу тебя восвояси невредимым. А если ещё и догадаешься, которая царевна старшая, которая средняя, а которая младшая, то и их...
На окружной железной дороге <i>n</i> станций. Иногда дежурные по станциям связываются друг с другом по радио. В каждый момент времени сеанс связи ведут только два человека. За сутки между каждыми двумя станциями произошёл ровно один радиосеанс. Для каждой станции (если учесть только её сеансы) оказалось, что она общалась с другими станциями по очереди в порядке их расположения на железной дороге (по или против часовой стрелки, у разных станций эти направления могут быть разными), начиная с одной из соседних и заканчивая другой. Чему может равняться <i>n</i>?
Выбежав после уроков на двор, каждый школьник кинул снежком ровно в одного другого школьника.
Докажите, что всех учащихся можно разбить на три команды так, что члены одной команды друг в друга снежками не кидали.
У Пети всего 28 одноклассников. У каждых двух из 28 различное число друзей в этом классе. Сколько друзей у Пети?
За круглым столом сидят несколько гостей. Некоторые из них знакомы между собой; знакомство взаимно. Все знакомые каждого гостя (считая его самого) сидят вокруг стола через равные промежутки. (Для другого человека эти промежутки могут быть другими.) Известно, что каждые двое имеют хотя бы одного общего знакомого. Докажите, что все гости знакомы друг с другом.
a) Восемь школьников решали восемь задач. Оказалось, что каждую задачу решили пять школьников. Докажите, что найдутся такие два школьника, что каждую задачу решил хотя бы один из них.
б) Если каждую задачу решили четыре ученика, то может оказаться, что таких двоих не найдётся.
Двое игроков по очереди выставляют на доску 65×65 по одной шашке. При этом ни в одной линии (горизонтали или вертикали) не должно быть больше двух шашек. Кто не может сделать ход – проиграл. Кто выигрывает при правильной игре?
Какое наибольшее число коней можно расставить на доске 5×5 клеток так, чтобы каждый из них бил ровно двух других?
Хозяйка сделала расстегай и хочет заранее разрезать его на такие (не обязательно равные) части, чтобы пирог можно было разделить поровну и на пятерых, и на семерых. Каким минимальным числом кусков она сможет обойтись?
На столе лежат несколько тонких спичек одинаковой длины. Всегда ли можно раскрасить их концы а) в 2, б) в 3 цвета так, чтобы два конца каждой спички были разных цветов, а каждые два касающихся конца (разных спичек) – одного и того же цвета?
За круглым столом были приготовлены 12 мест для жюри с указанием имени на каждом месте. Николай Николаевич, пришедший первым, по рассеянности сел не на своё, а на следующее по часовой стрелке место. Каждый член жюри, подходивший к столу после этого, занимал своё место или, если оно уже было занято, шёл вокруг стола по часовой стрелке и садился на первое свободное место. Возникшее расположение членов жюри зависит от того, в каком порядке они подходили к столу. Сколько может возникнуть различных способов рассадки жюри?
Квадрат разбит прямыми на 25 квадратиков-клеток. В некоторых клетках нарисована одна из диагоналей так, что никакие две диагонали не имеют общей точки (даже общего конца). Каково наибольшее возможное число нарисованных диагоналей?
В компанию из <i>n</i> человек пришёл журналист. Ему известно, что в этой компании есть человек <i>Z</i>, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?"
а) Может ли журналист установить, кто из компании есть <i>Z</i>, задав менее <i>n</i> вопросов?
б) Найдите наименьшее количество вопросов, достаточное для того, чтобы наверняка найти <i>Z</i>, и докажите, что меньшим числом вопросов обойтись нельзя.
(Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько вопросов.)