Найдите задачу для урока, кружка или самостоятельной работы.
Клетки доски размером 5×5 раскрашены в шахматном порядке (угловые клетки – чёрные). По чёрным клеткам этой доски двигается фигура – мини-слон, оставляя след на каждой клетке, где он побывал, и больше в эту клетку не возвращаясь. Мини-слон может ходить либо в свободные от следов соседние (по диагонали) клетки, либо прыгать (также по диагонали) через одну клетку, в которой оставлен след, на свободную клетку за ней. Какое наибольшее количество клеток сможет посетить мини-слон?
В каждой клетке таблицы, состоящей из 10 столбцов и n строк, записана цифра. Известно, что для каждой строки A и любых двух столбцов найдётся строка, отличающаяся от A ровно в этих двух столбцах. Докажите, что n ≥ 512.
На некоторых клетках доски 10×10 сидит по блохе. Раз в минуту блохи одновременно прыгают, причём каждая – в соседнюю клетку (по стороне). Блоха прыгает строго в одном из четырёх направлений, параллельных сторонам доски, сохраняет направление, пока это возможно, иначе меняет его на противоположное. Пес Барбос наблюдал за блохами в течение часа и ни разу не видел, чтобы две из них сидели на одной клетке. Какое наибольшее количество блох могло прыгать по доске?
На плоскости дана незамкнутая несамопересекающаяся ломаная, в которой 31 звено (соседние звенья не лежат на одной прямой). Через каждое звено провели прямую, содержащую это звено. Получили 31 прямую, некоторые, возможно, совпали. Какое наименьшее число различных прямых могло получиться?
В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.
На новом сайте зарегистрировалось 2000 человек. Каждый пригласил к себе в друзья по 1000 человек. Два человека объявляются друзьями тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?
На доске выписано (n – 1)n выражений: x1 – x2, x1 – x3, ..., x1 – xn, x2 – x1, x2 – x3, ..., x2 – xn, ..., xn – xn–1, где n ≥ 3. Лёша записал в тетрадь все эти выражения, их суммы по два различных, по три различных и т. д. вплоть до суммы всех выражений. При этом Лёша во всех выписываемых суммах приводил подобные слагаемые (например, вместо (x1 – x2) + (x2 – x3) Лёша запишет x1 – x3, а вместо (x1 – x2) + (x2 – x1) он запишет 0). Сколько выражений Лёша записал в тетрадь ровно по одному разу?
Дана незамкнутая несамопересекающаяся ломаная из 37 звеньев. Через каждое звено провели прямую. Какое наименьшее число различных прямых могло получиться?
На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка. Докажите, что у семи из них есть общий дедушка.
В стране некоторые пары городов соединены дорогами, которые не пересекаются вне городов. В каждом городе установлена табличка, на которой указана минимальная длина маршрута, выходящего из этого города и проходящего по всем остальным городам страны (маршрут может проходить по некоторым городам больше одного раза и не обязан возвращаться в исходный город). Докажите, что любые два числа на табличках отличаются не более чем в полтора раза.
В компании из семи человек любые шесть могут сесть за круглый стол так, что каждые два соседа окажутся знакомыми. Докажите, что и всю компанию можно усадить за круглый стол так, что каждые два соседа окажутся знакомыми.
Назовём лестницей высоты n фигуру, состоящую из всех клеток квадрата n×n, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты n на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?
Докажите, что при любых натуральных 0
Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.
Дана таблица n×n, столбцы которой пронумерованы числами от 1 до n. В клетки таблицы расставляются числа 1, ..., n так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку хорошей, если число в ней больше номера столбца, в котором она находится. При каких n существует расстановка, в которой во всех строках одинаковое количество хороших клеток?
300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.
В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает её вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.
В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?
Барон Мюнхгаузен рассказывал, что у него есть карта страны Оз с пятью городами. Каждые два города соединены дорогой, не проходящей через другие города. Каждая дорога пересекает на карте не более одной другой дороги (и не более одного раза). Дороги обозначены жёлтым или красным (по цвету кирпича, которым вымощены), и при обходе вокруг каждого города (по периметру) цвета выходящих из него дорог чередуются. Могут ли слова барона быть правдой?
Турнир, в котором участвовало 20 спортсменов, судили 10 арбитров. Каждый сыграл с каждым один раз, и каждую встречу судил ровно один арбитр. После окончания каждой игры оба участника фотографировались с арбитром. Через год после турнира была найдена стопка из всех этих фотографий. Оказалось, что не про каждого можно определить, кем он является – спортсменом или арбитром. Сколько могло быть таких людей?
Клетчатая прямоугольная сетка m×n связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?
Каждая деталь конструктора "Юный паяльщик" – это скобка в виде буквы П, состоящая из трёх единичных отрезков. Можно ли из деталей этого конструктора спаять полный проволочный каркас куба 2×2×2, разбитого на кубики 1×1×1? (Каркас состоит из 27 точек, соединённых единичными отрезками; любые две соседние точки должны быть соединены ровно одним проволочным отрезком.)
Назовём раскраску доски 8×8 в три цвета хорошей, если в любом уголке из пяти клеток присутствуют клетки всех трёх цветов. (Уголок из пяти клеток – это фигура, получающаяся из квадрата 3×3 вырезанием квадрата 2×2.) Докажите, что количество хороших раскрасок не меньше чем 68.
На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся к моменту их ухода. Какое наибольшее число людей могло остаться в конце?
В наборе из 17 внешне одинаковых монет две фальшивых, отличающихся от остальных по весу. Известно, что суммарный вес двух фальшивых монет вдвое больше веса настоящей. Всегда ли можно ли определить пару фальшивых монет, совершив пять взвешиваний на чашечных весах без гирь? (Определять, какая из фальшивых монет тяжелее, не требуется.)