Имеются красные и синие бусинки.Составляется круговое ожерелье из 22 бусинок. Оно называется счастливым, если в нем нет двух красных бусинок, между которыми ровно одна (любая) бусинка. Какое наибольшее количество красных бусинок может быть в счастливом ожерелье?

Рассмотрим 11 бусинок на четных позициях, они образуют "разреженное" круговое ожерелье. Для них получается условие: нет двух соседних красных бусинок. Тогда среди них красных не более 5. Аналогично, среди бусинок на нечетных позициых не более 5 красных. Пример на 10 красных бусинок: ССККССККССККССККССККСС (по кругу). 

Катя выписывает k натуральных чисел, каждое из которых является делителем числа $6^4$. При каком наименьшем k среди этих делителей наверняка найдутся два числа, одно из которых делится на другое?

Каждый делитель имеет вид: произведение степени тройки $3^k$ (где k - одно из чисел 0, 1, 2, 3, 4) на степень двойки. Среди шести делителей найдутся два числа с одним и тем же k. Тогда одно из этих чисел делится на другое. С другой стороны, есть пример, показывающий, что k=5 не работает: $2^4$, $2^3\cdot 3$, $2^2\cdot 3^2$, $2\cdot 3^3$, $3^4$, 

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

Разобьем числа на 6 групп: имеющих последнюю цифру 0, последнюю цифру 1 или 9, последнюю цифру 2 или 8, последнюю цифру 3 или 7, последнюю цифру 4 или 6, последнюю цифру 5. Если чисел хотя бы 7, то какие-то два числа попадут в одну группу, а значит, их сумма или их разность имеет последнюю цифру 0, т.е. делится на 10. С другой стороны, есть пример, показывающий, что 6 чисел взять можно: 1, 2, 3, 4, 5, 10. 

На квадратном столе 1 м на 1 м разбрасывают 999 квадратных бумажных салфеток размером 10 см на 10 см. При каком наибольшем $k$ верно такое утверждение: всегда можно воткнуть в стол булавку, протыкающую не менее k салфеток? (Каждая салфетка полностью лежит на столе. Если булавку воткнуть в границу салфетки, то она не протыкает салфетку.)

Суммарная площадь салфеток больше 9S, где S - площадь стола, поэтому над какой-то точкой стола не менее 10 слоев салфеток - в эту точку и можно воткнуть булавку. С другой стороны, поверхность стола можно уложить 100 салфетками в один слой, и значит 1000 салфетками - в 10 слоев (одну из 1000 можно будет убрать). Этот пример показывает. что k>10 не всегда работает.

Группа из 9 друзей на завтраке сели за 2 стола. На обеде те же 9 друзей сели за 2 стола, в каком-то другом порядке. При каком наибольшем m точно найдутся m друзей, которые сидели за одним столом как на завтраке, так и на обеде?

За завтраком найдем 5 друзей, сидящих за одним столом. Будем следить за рассадкой этих 5 друзей за обедом: какие-то трое обязательно за одним столом. С другой стороны, рассмотрим такой пример: пусть друзья садились так (первая цифра - номер стола за завтраком, вторая цифра - за обедом): 11, 11, 12, 12, 21, 21, 22, 22, 22. В этом примере нет 4 друзей, которые бы сидели за одним столом как на завтраке, так и на обеде. 

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

Рассмотрим 11 бусинок на четных позициях. Для них получается условие: нет двух соседних красных бусинок. Тогда среди них красных не более 6. Аналогично, среди бусинок на нечетных позициях не более 6 красных. Пример на 12 красных бусинок: ККССККССККССККССККССККС.

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

Посмотрим на последние цифры чисел. Если чисел хотя бы 11, то у каких-то двух последние цифры совпадают, а значит их разность оканчивается на 0, т.е. делится на 10. С другой стороны, есть пример, показывающий, что 10 чисел взять можно: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 

Среди n+1 чисел есть два числа с одиаковым остатком при делеии на n

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

Пример на 9 суперкоролей можно получить, поставив их на горизонтали и вертикали, образующие сетку с промежутком в 2 клетки. С другой стороны, двумя горизонтальными и двумя вертикальными разрезами можно разбить доску на 9 областей (квадраты 3x3, 2x2 и прямоугольники 3x2). И в каждую из этих областей можно поставить не более одного суперкороля, значит, всего - не более девяти.

Игра в "Морской бой-light" происходит на поле 7x7. Ася ставит двухпалубный корабль (т.е. "доминошку" из двух клеток), а Боря стреляет по клеткам. Какое наименьшее количество выстрелов потребуется Боре, чтобы наверняка ранить Асин корабль (т.е. попасть выстрелом в одну из клеток корабля).

Пусть клетки покрашены в шахматном порядке так, чтобы угловые клетки были белые. Тогда Боря может выстрелить в 24 черные клетки. Ясно, что одна из клеток корабля Аси будет поражена. С другой стороны, 23 выстрела для гарантированной победы Боре не хватит: разобьем доску без угловой клетки на 24 доминошки. Каждая из этих доминошек может быть кораблем. 

Какое наибольшее количество пешек можно поставить на доске 7x7 так, чтобы никакие две пешки не оказались в соседних по стороне клетках?

Пример, в котором 25 пешек стоят на 25 клетках одного цвета шахматной раскраски, показывает, пешек может быть 25. С другой стороны, все клетки доски, кроме одной угловой, можно разбить на 24 доминошки. В каждой доминошке не более одной пешки, поэтому всего пешек не более 24+1=25.

Раскраска и разбиеие на доминошки

В круговом ожерелье из 27 бусинок некоторые бусинки красные, но нет двух соседних красных бусинок. Каково наибольшее возможное количество красных бусинок?

Пример СКСКСК...КС показывает, что красных бусинок может быть (27-1) : 2 = 13. С другой стороны можно взять одну не красную бусинку (она, очевидно, найдется, даже среди двух соседей), а остальные 26 бусинок разобьем на 13 пар соседей. В каждой такой паре не более одной красной бусинки, итого - не более 13. 

Идея разбиения на группы

В мешке лежат шарики двух разных цветов: красного и синего. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них наверняка оказались либо три красных шарика, либо пять синих? (И то и другое - тоже годится.)

Шести шариков не достаточно - можно достать 2 красных и 4 синих. Наоборот, если не выполнили условие, то достали не более 2 красных и 4 синих шаров, т.е. всего не более 6 шаров.

Саша выписывает k натуральных чисел, каждое из которых является делителем числа 1024. При каком наименьшем k среди этих делителей наверняка найдутся два числа, одно из которых делится на другое?

Ясно, что k=1 не достаточно. Далее заметим, что 1024 - это двойка в 10 степени, поэтому любой его делитель является степенью двойки. Значит, из любых двух делителей один делится на другой. Значит, k=2 работает. 

В мешке деда Мороза 100 конфет для 20 обидчивых детей. Ребенок обижается, если получает менее 7 конфет. Какое наименьшее количество детей могут остаться обиженными? 

Пусть не обиделись k детей. Тогда они получили вместе хотя бы 7k конфет. Так как 7k не более 100, k не превосходит 100/7, значит не превосходит 14. Тогда обиженных детей не менее 20-14 = 6. С другой стороны, если 14 детей взяли по 7 конфет, то в самом деле окажется ровно 6 обиженных.

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

10 карандашей - не всегда сработает: в них могут быть представлены все цвета по разу и все фирмы по разу. А среди 11 карандашей обязательно найдутся два карандаша одинакового цвета. 

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

Два числа - работает, например, 1 и 2. Три и более чисел - не работает: среди трех чисел найдутся два число одной четности, их сумма будет четной. 

Важно обратить внимание на ответ из двух частей. Пример и оценка.

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

Разобьем числа на 9 групп: 8 пар соседей и одну группу из одного числа. В одной группе не более одного четного числа, поэтому всего четных чисел не больше 9. Пример, когда возможно 9 четных чисел выглядит так: ЧНЧНЧНЧНЧНЧНЧНЧНЧ.

В игре на биляьрде в 6 луз забили 15 шаров. При каком наибольшем k верно утверждение: обязательно найдется луза, в которую забили не менее k шаров.

k=3 работает: в противном случае в каждую лузу забито не более двух шаров, и тогда шаров не более 12 - противоречие. Пример: 3,3,3,2,2,2 показывает, что k>3 уже работает не всегда. 

Играя в бильярд, в 6 луз забили 15 шаров. При каком наибольшем $k$ верно утверждение: обязательно найдется луза, в которую забили не менее $k$ шаров.

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

Четыре кубика может не хватить - все могут оказаться разных цветов. Наоборот, если мы еще не победили, то взято не более одного кубика каждого цвета - итого не более 4 кубиков.