Найдите задачу для урока, кружка или самостоятельной работы.
Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества {1, 2, 3, ..., 2k}, а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.
По шоссе в одном направлении едут 10 автомобилей. Шоссе проходит через несколько населённых пунктов. Каждый из автомобилей едет с некоторой постоянной скоростью в населённых пунктах и с некоторой другой постоянной скоростью вне населённых пунктов. Для разных автомобилей эти скорости могут отличаться. Вдоль шоссе расположено 2011 флажков. Известно, что каждый автомобиль проехал мимо каждого флажка, причём около флажков обгонов не происходило. Докажите, что мимо каких-то двух флажков автомобили проехали в одном и том же порядке.
100 красных точек разделили синюю окружность на 100 дуг, длины которых являются всеми натуральными числами от 1 до 100 в произвольном порядке. Докажите, что существуют две перпендикулярные хорды с красными концами.
Две команды шахматистов одинаковой численности сыграли матч: каждый сыграл по одному разу с каждым из другой команды. В каждой партии давали 1 очко за победу, ½ – за ничью и 0 – за поражение. В итоге команды набрали поровну очков. Докажите, что какие-то два участника матча тоже набрали поровну очков, если в обеих командах было: а) по 5 шахматистов; б) произвольное равное число шахматистов.
Среди натуральных чисел от 1 до 1200 выбрали 372 различных числа так, что никакие два из них не различаются на 4, 5 или 9. Докажите, что число 600 является одним из выбранных.
Какое минимальное количество клеток можно закрасить черным в белом квадрате 300×300, чтобы никакие три черные клетки не образовывали уголок, а после закрашивания любой белой клетки это условие нарушалось?
Даны натуральные числа p
На плоскости отмечено N 3различных точек. Известно, что среди попарных расстояний между отмеченными точками встречаются не более n различных расстояний. Докажите, что N (n+1)2 .
Можно ли расположить в пространстве 12 прямоугольных параллелепипедов P1 , P2 , P12, ребра которых параллельны координатным осям Ox , Oy , Oz так, чтобы P2 пересекался (т.е. имел хотя бы одну общую точку) с каждым из оставшихся, кроме P1 и P3 , P3 пересекался с каждым из оставшихся, кроме P2 и P4 , и т.д., P12пересекался с каждым из оставшихся, кроме P11и P1 , P1 пересекался с каждым из оставшихся, кроме P12и P2 ? (Поверхность параллелепипеда принадлежит ему.)
В стране 1001 город, каждые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из каждого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.
Найдите наибольшее натуральное число N, для которого при произвольной расстановке различных натуральных чисел от 1 до 400 в клетках квадратной таблицы 20×20 найдутся два числа, стоящих в одной строке или одном столбце, разность которых будет не меньше N.
Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета. Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
В квадрате n×n клеток бесконечной шахматной доски расположены n2 фишек, по одной фишке в каждой клетке. Ходом называется перепрыгивание любой фишкой через соседнюю по стороне фишку, непосредственно за которой следует свободная клетка. При этом фишка, через которую перепрыгнули, с доски снимается. Докажите, что позиция, в которой дальнейшие ходы невозможны, возникнет не ранее, чем через[]ходов.
В клетках таблицы 10×10 расставлены числа 1, 2, 3, ..., 100 так, что сумма любых двух соседних чисел не превосходит S. Найдите наименьшее возможное значение S. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону.)
В однокруговом футбольном турнире играли  n > 4 команд. За победу давалось 3 очка, за ничью 1, за проигрыш 0. Оказалось, что все команды набрали поровну очков. а) Докажите, что найдутся четыре команды, имеющие поровну побед, поровну ничьих и поровну поражений. б) При каком наименьшем n могут не найтись пять таких команд?
У ведущего есть колода из 52 карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя сверху вниз или снизу вверх). Разрешается задавать ведущему вопросы вида "Сколько карт лежит между такой-то и такой-то картами?". Один из зрителей подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на эти вопросы могли узнать порядок карт в колоде?
Для каждой пары действительных чиселaиbрассмотрим последовательность чиселpn= [2{an+b}]. Любыеkподряд идущих членов этой последовательности назовем словом. Верно ли, что любой упорядоченный набор из нулей и единиц длиныkбудет словом последовательности, заданной некоторымиaиbприk= 4; приk= 5? Примечание: [c] - целая часть, {c} - дробная часть числа c.
На пол положили правильный треугольникABC, выпиленный из фанеры. В пол вбили три гвоздя (по одному вплотную к каждой стороне треугольника) так, что треугольник невозможно повернуть, не отрывая от пола. Первый гвоздь делит сторонуABв отношении 1 : 3, считая от вершиныA, второй делит сторонуBCв отношении 2 : 1, считая от вершиныB. В каком отношении делит сторонуACтретий гвоздь?
На плоскости дано конечное число полос, сумма ширин которых равна 100, и круг радиуса 1. Докажите, что каждую из полос можно параллельно перенести так, чтобы все они вместе покрыли круг.
В таблице 2n×n были выписаны всевозможные строки длины n из чисел 1 и –1. Затем часть чисел заменили нулями. Докажите, что можно выбрать несколько строк, сумма которых есть строка из нулей. (Суммой строк называется строка, элементы которой являются суммами соответствующих элементов слагаемых.)
Из выпуклого многогранника с 9 вершинами, одна из которыхA, параллельными переносами, переводящимиAв каждую из остальных вершин, образуется 8 равных ему многогранников. Докажите, что хотя бы два из этих 8 многогранников пересекаются (по внутренним точкам).
Петя разрезал прямоугольный лист бумаги по прямой. Затем он разрезал по прямой один из получившихся кусков. Затем он проделал то же самое с одним из трёх получившихся кусков и т.д. Докажите, что после достаточного количества разрезаний можно будет выбрать среди получившихся кусков 100 многоугольников с одинаковым числом вершин (например, 100 треугольников или 100 четырёхугольников и т.д.).
Докажите, что первые цифры чисел вида 22n образуют непериодическую последовательность.
Дима придумал секретный шифр: каждая буква заменяется на слово длиной не больше 10 букв. Шифр называется хорошим, если всякое зашифрованное слово расшифровывается однозначно. Серёжа убедился (с помощью компьютера), что если зашифровать слово длиной не больше 10000 букв, то результат расшифровывается однозначно. Следует ли из этого, что шифр хороший? (В алфавите 33 буквы, под "словом" мы понимаем любую последовательность букв, независимо от того, имеет ли она смысл.)
В таблице из n столбцов и 2n строк, в которых выписаны все возможные различные наборы из n чисел 1 и –1, некоторые числа заменены нулями. Докажите, что можно выбрать некоторое непустое подмножество строк так, что: а) сумма всех чисел в выбранных строках равна 0; б) сумма всех выбранных строк есть нулевая строка. (Строки складываются покоординатно как векторы.)