Олимпиадные задачи по теме «Комбинаторика» для 7-8 класса - сложность 2-4 с решениями

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

Для игры в шляпу Надя хочет разрезать лист бумаги на 48 одинаковых прямоугольников. Какое наименьшее количество разрезов ей придется сделать, если любые куски бумаги можно перекладывать, но нельзя сгибать, а Надя способна резать одновременно сколько угодно слоёв бумаги? (Каждый разрез – прямая линия от края до края куска.)

На рисунке приведены три примера показаний исправных электронных часов. Сколько палочек могут перестать работать, чтобы время всегда можно было определить однозначно? <div align="center"><img src="/storage/problem-media/117005/problem_117005_img_2.gif"></div>

Вася выписал все слова (не обязательно осмысленные), которые получаются вычеркиванием ровно двух букв из слова <i>ИНТЕГРИРОВАНИЕ</i>, а Маша сделала то же самое со словом <i>СУПЕРКОМПЬЮТЕР</i>. У кого получилось больше слов?

Десять футбольных команд сыграли каждая с каждой по одному разу. В результате у каждой команды оказалось ровно по <i>х</i> очков.

Каково наибольшее возможное значение <i>х</i>? (Победа – 3 очка, ничья – 1 очко, поражение – 0.)

В круговом шахматном турнире участвует 9 мальчиков и 3 девочки (каждый играет с каждым один раз, победа – 1 очко; ничья – 0,5; поражение – 0). Может ли в итоге оказаться, что сумма очков, набранных всеми мальчиками, будет равна сумме очков, набранных всеми девочками?

<img align="right" src="/storage/problem-media/116673/problem_116673_img_2.gif">Кузнечик умеет прыгать только ровно на 50 см. Он хочет обойти 8 точек, отмеченных на рисунке (сторона клетки равна 10 см). Какое наименьшее количество прыжков ему придётся сделать? (Разрешается посещать и другие точки плоскости, в том числе не узлы сетки. Начинать и заканчивать можно в любых точках.)

Клетки доски размером 5×5 раскрашены в шахматном порядке (угловые клетки – чёрные). По чёрным клеткам этой доски двигается фигура – мини-слон, оставляя след на каждой клетке, где он побывал, и больше в эту клетку не возвращаясь. Мини-слон может ходить либо в свободные от следов соседние (по диагонали) клетки, либо прыгать (также по диагонали) через одну клетку, в которой оставлен след, на свободную клетку за ней. Какое наибольшее количество клеток сможет посетить мини-слон?

Клетчатый квадрат 2010×2010 разрезан на трёхклеточные уголки. Докажите, что можно в каждом уголке отметить по клетке так, чтобы в каждой вертикали и в каждой горизонтали было поровну отмеченных клеток.

Назовём компанию <i>k-неразбиваемой</i>, если при любом разбиении её на <i>k</i> групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.

В каждой клетке таблицы, состоящей из 10 столбцов и <i>n</i> строк, записана цифра. Известно, что для каждой строки <i>A</i> и любых двух столбцов найдётся строка, отличающаяся от <i>A</i> ровно в этих двух столбцах. Докажите, что  <i>n</i> ≥ 512.

Для некоторых 2011 натуральных чисел выписали на доску все их 2011·1005 попарных сумм.

Могло ли оказаться, что ровно треть выписанных сумм делится на 3, и ещё ровно треть из них дают остаток 1 при делении на 3?

В волейбольном турнире с участием 73 команд каждая команда сыграла с каждой по одному разу. В конце турнира все команды разделили на две непустые группы так, что каждая команда первой группы одержала ровно <i>n</i> побед, а каждая команда второй группы – ровно <i>m</i> побед. Могло ли оказаться, что  <i>m</i> ≠ <i>n</i>?

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

На некоторых клетках доски 10×10 сидит по блохе. Раз в минуту блохи одновременно прыгают, причём каждая – в соседнюю клетку (по стороне). Блоха прыгает строго в одном из четырёх направлений, параллельных сторонам доски, сохраняет направление, пока это возможно, иначе меняет его на противоположное. Пес Барбос наблюдал за блохами в течение часа и ни разу не видел, чтобы две из них сидели на одной клетке. Какое наибольшее количество блох могло прыгать по доске?

На плоскости дана незамкнутая несамопересекающаяся ломаная, в которой 31 звено (соседние звенья не лежат на одной прямой). Через каждое звено провели прямую, содержащую это звено. Получили 31 прямую, некоторые, возможно, совпали. Какое наименьшее число различных прямых могло получиться?

Сумма цифр натурального числа <i>n</i> равна 100. Может ли сумма цифр числа <i>n</i>³ равняться 1000000?

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

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.

Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

У Миши есть 1000 одинаковых кубиков, у каждого из которых одна пара противоположных граней белая, вторая – синяя, третья – красная. Он собрал из них большой куб 10×10×10, прикладывая кубики друг к другу одноцветными гранями. Докажите, что у большого куба есть одноцветная грань.

На новом сайте зарегистрировалось 2000 человек. Каждый пригласил к себе в друзья по 1000 человек. Два человека <i>объявляются</i> друзьями тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?

Семизначный код, состоящий из семи различных цифр, назовем <i>хорошим</i>. Паролем сейфа является хороший код. Известно, что сейф откроется, если введён хороший код и на каком-нибудь месте цифра кода совпала с соответствующей цифрой пароля. Можно ли гарантированно открыть сейф быстрее, чем за семь попыток?

На доске выписано  (<i>n</i> – 1)<i>n</i>  выражений:   <i>x</i>₁ – <i>x</i>₂,  <i>x</i>₁ – <i>x</i>₃,  ...,  <i>x</i>₁ – <i>x_n</i>,  <i>x</i>₂ – <i>x</i>₁,  <i>x</i>₂ – <i>x</i>₃,  ...,  <i>x</i>₂ – <i>x_n</i>,  ...,  <i>x_n</i> – <i>x</i>_<i>n</i>–1,   где  <i>n</i&...

Какое наибольшее количество точек самопересечения может иметь замкнутая ломаная, в которой 7 звеньев?