Олимпиадные задачи по теме «Принцип крайнего» для 8 класса - сложность 4 с решениями

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

За круглым столом заседают <i>N</i> рыцарей. Каждое утро чародей Мерлин сажает их в другом порядке. Начиная со второго дня Мерлин разрешил рыцарям делать в течение дня сколько угодно пересадок такого вида: два сидящих рядом рыцаря меняются местами, если только они не были соседями в первый день. Рыцари стараются сесть в том же порядке, что и в какой-нибудь из предыдущих дней: тогда заседания прекратятся. Какое наибольшее число дней Мерлин гарантированно может проводить заседания?

(Рассадки, получающиеся друг из друга поворотом, считаются одинаковыми. Мерлин за столом не сидит.)

В треугольнике провели серединные перпендикуляры к его сторонам и измерили их отрезки, лежащие внутри треугольника.

  а) Все три отрезка оказались равны. Верно ли, что треугольник равносторонний?

  б) Два отрезка оказались равны. Верно ли, что треугольник равнобедренный?

  в) Могут ли длины отрезков равняться 4, 4 и 3?

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

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

а) В 99 ящиках лежат яблоки и апельсины.

Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов. б) В 100 ящиках лежат яблоки и апельсины.

Докажите, что можно так выбрать 34 ящика, что в них окажется не менее трети всех яблок и не менее трети всех апельсинов.

Имеется 8 монет, 7 из которых – настоящие, которые весят одинаково, и одна фальшивая, отличающаяся по весу от остальных. Чашечные весы без гирь таковы, что если положить на их чашки равные грузы, то любая из чашек может перевесить, если же грузы различны по массе, то обязательно перетягивает чашка с более тяжелым грузом. Как за четыре взвешивания наверняка определить фальшивую монету и установить, легче она или тяжелее остальных?

Натуральные числа от 1 до 100 расставлены по кругу в таком порядке, что каждое число либо больше обоих соседей, либо меньше обоих соседей. Пара соседних чисел называется <i>хорошей</i>, если при выкидывании этой пары вышеописанное свойство сохраняется. Какое минимальное количество хороших пар может быть?

В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырёх цветов. Известно, что провода всех четырёх цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?

Треугольник<i> T </i>содержится внутри выпуклого центрально-симметричного многоугольника<i> M </i>. Треугольник<i> T' </i>получается из треугольника<i> T </i>центральной симметрией относительно некоторой точки<i> P </i>, лежащей внутри треугольника<i> T </i>. Докажите, что хотя бы одна из вершин треугольника<i> T' </i>лежит внутри или на границе многоугольника<i> M </i>.

В прямоугольной таблице 9 строк и 2004 столбца. В её клетках расставлены числа от 1 до 2004, каждое – по 9 раз. При этом в каждом столбце числа различаются не более чем на 3. Найдите минимальную возможную сумму чисел в первой строке.

На плоскости взято конечное число красных и синих прямых, среди которых нет параллельных, так, что через каждую точку пересечения одноцветных прямых проходит прямая другого цвета. Докажите, что все прямые проходят через одну точку.

В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.

Найдите все такие нечётные натуральные  <i>n</i> > 1,  что для любых взаимно простых делителей <i>a</i> и <i>b</i> числа <i>n</i> число  <i>a + b</i> – 1  также является делителем <i>n</i>.

Найдите все такие натуральные числа <i>n</i>, что для любых двух его взаимно простых делителей <i>a</i> и <i>b</i> число  <i>a + b</i> – 1  также является делителем <i>n</i>.

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

На прямоугольном столе лежат равные картонные квадраты<i> n </i>различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые<i> n </i>квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу2<i>n-</i>2гвоздями.

На координатной плоскости дан выпуклый пятиугольник<i> ABCDE </i>с вершинами в целых точках. Докажите, что внутри или на границе пятиугольника<i> A₁B₁C₁D₁E₁ </i><i> (см. рис.) </i>есть хотя бы одна целая точка. <center><i> <img src="/storage/problem-media/109709/problem_109709_img_2.gif"> </i></center>

В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.

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

В клетках таблицы 10×10 расставлены числа 1, 2, 3, ..., 100 так, что сумма любых двух соседних чисел не превосходит <i>S</i>.

Найдите наименьшее возможное значение <i>S</i>. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону.)

В однокруговом футбольном турнире играли &nbsp<i>n</i> > 4  команд. За победу давалось 3 очка, за ничью 1, за проигрыш 0. Оказалось, что все команды набрали поровну очков.

  а) Докажите, что найдутся четыре команды, имеющие поровну побед, поровну ничьих и поровну поражений.

  б) При каком наименьшем <i>n</i> могут не найтись пять таких команд?

а) Наконец, у Снежной Королевы появились все квадраты с целыми сторонами, но каждый в единственном экземпляре. Королева пообещала Каю, что он станет мудрым, если сможет из каких-то имеющихся квадратов сложить прямоугольник. Сможет ли он это сделать? б) Отдыхая, Кай стал заполнять стеклянный аквариум ледяными кубиками, которые лежали рядом. Кубики были самых разных размеров, но среди них не было двух одинаковых. Сможет ли Кай заполнить аквариум кубиками целиком?

За круглым столом сидят десять человек, перед каждым – несколько орехов. Всего орехов – сто. По общему сигналу каждый передаёт часть своих орехов соседу справа: половину, если у него (у того, кто передаёт) было чётное число, или один орех плюс половину остатка – если нечётное число. Такая операция проделывается второй раз, затем третий и так далее, до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.

Дима придумал секретный шифр: каждая буква заменяется на слово длиной не больше 10 букв. Шифр называется <i>хорошим</i>, если всякое зашифрованное слово расшифровывается однозначно. Серёжа убедился (с помощью компьютера), что если зашифровать слово длиной не больше 10000 букв, то результат расшифровывается однозначно. Следует ли из этого, что шифр хороший? (В алфавите 33 буквы, под "словом" мы понимаем любую последовательность букв, независимо от того, имеет ли она смысл.)