Олимпиадные задачи по математике для 5-8 класса - сложность 2-5 с решениями
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на <i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
В стране несколько городов, некоторые пары городов соединены дорогами. При этом из каждого города выходит хотя бы три дороги.
Докажите, что существует циклический маршрут, длина которого не делится на 3.
В микросхеме 2000 контактов, первоначально любые два контакта соединены отдельным проводом. Хулиганы Вася и Петя по очереди перерезают провода, причем Вася (он начинает) за ход режет один провод, а Петя – либо один, либо три провода. Хулиган, отрезающий последний провод от какого-либо контакта, проигрывает. Кто из них выигрывает при правильной игре?
В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из <i>N</i> авиакомпаний, причём из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из каждого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт <i>N</i> – 1 рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из каждого города можно долететь до любого другого.
В микросхеме 2000 контактов, первоначально любые два контакта соединены отдельным проводом. Хулиганы Вася и Петя по очереди перерезают провода, причем Вася (он начинает) за ход режет один провод, а Петя – либо два, либо три провода. Хулиган, отрезающий последний провод от какого-либо контакта, проигрывает. Кто из них выигрывает при правильной игре?
В клетках таблицы 2000×2000 записаны числа 1 и –1. Известно, что сумма всех чисел в таблице неотрицательна. Докажите, что найдутся 1000 строк и 1000 столбцов таблицы, для которых сумма чисел, записанных в клетках, находящихся на их пересечении, не меньше 1000.
Натуральные числа от 1 до 1000 по одному выписали на карточки, а затем накрыли этими карточками какие-то 1000 клеток прямоугольника1<i>x </i>1994. Если соседняя справа от карточки с числом<i> n </i>клетка свободна, то за один ход ее разрешается накрыть карточкой с числом<i> n+</i>1. Докажите, что нельзя сделать более полумиллиона таких ходов.
В колоде<i> n </i>карт. Часть из них лежит рубашками вверх, остальные – рубашками вниз. За один ход разрешается взять несколько карт сверху, перевернуть полученную стопку и снова положить ее сверху колоды. За какое наименьшее число ходов при любом начальном расположении карт можно добиться того, чтобы все карты лежали рубашками вниз?