Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/spring06/zhest/z-13-shnu.ps Дата изменения: Wed Apr 12 23:26:00 2006 Дата индексирования: Sun Dec 23 01:26:56 2007 Кодировка: koi8-r

Конструктив.13.04.06.Жесть
1)Дан правильный треугольник ABC со стороной 3. Треугольник
называется "большим", если все его стороны больше 1.
а)Доказать, что из треугольника ABC можно вырезать 100 больших
треугольников.
б)Треугольник ABC можно целиком разрезать на не менее чем 100
больших треугольников.
2) Докажите, что существует такая бесконечная ограниченная после-
довательность x n , что для любых различных m и k выполнено неравен-
ство
|x m - x k ||m - k| >= 1
3) На плоскости задано несколько непересекающихся отрезков, ника-
кие два из которых не лежат на одной прямой. Мы хотим провести еще
несколько отрезков, соединяющих концы данных отрезков так, чтобы
все отрезки вместе образовали одну несамопересекающуюся ломаную.
Всегда ли это можно сделать?
4) Множество A состоит из целых чисел, его наименьший элемент ра-
вен 1, а наибольший равен 100. Каждый элемент A, кроме 1, равен сумме
двух (возможно равных) чисел, принадлежащих A. Укажите среди всех
множеств A, удовлетворяющих этим условиям, множество с минималь-
ным числом элементов.
5) В правильном n-угольнике требуется покрасить каждую сторону
и каждую диагональ каким-либо цветом так, чтобы любые два из этих
отрезков, имеющие общую точку, были окрашены различно. Какое наи-
меньшее количество цветов для этого необходимо?
6) На бесконечном клетчатом листе со стороной клетки 1 разреша-
ется делать разрезы только по линиям сетки. Докажите, что при любом
целом m > 12 можно вырезать прямоугольник площади, большей m, из
которого нельзя вырезать прямоугольник площади m.
7) Можно ли разместить 2006 точек в квадрате со стороной 1 так,
чтобы любой прямоугольник площади 0.005 со сторонами, параллель-
ными сторонам квадрата, содержал внутри хотя бы 1 из этих точек?
1

Инварианты.13.04.06.Жесть
8) В клетки таблицы m в n вписаны числа. Разрешается одновре-
менно менять знак у всех чисел некоторого столбца или некоторой строки.
Докажите, что многократным повторением этой операции можно пре-
вратить данную таблицу в такую, у которой суммы чисел, стоящих в
любой строке и в любом столбце, неотрицательны.
9) На доске написано несколько нулей, единиц и двоек. Разрешается
стереть две неравные цифры и вписать вместо них цифру, отличную
от стертых. Докажите, что если в результате таких операций на доске
останется одно число, то оно не зависит от порядка, в котором произ-
водились стирания.
10) Дан произвольный набор из чисел. Из него получается новый
набор из циклических полусумм чисел старого набора. Из этого набора
- следующий по тому же правилу и т.д. Докажите, что если все получа-
ющиеся числа целые, то первоначальные числа равны.
11) Возьмем любое 2006-значное число, делящееся на 9. Сумму его
цифр обозначим за a, сумму цифр числа a через b, сумму цифр b - через
c. Чему равно c?
12) По кругу выписаны несколько чисел. Если для некоторых четы-
рех идущих подряд чисел a; b; c; d оказывается, что (a - d)(b - c) < 0, то
числа b и c можно поменять местами. Докажите, что такую операцию
можно проделать лишь конечное число раз.
13) Задано несколько красных и несколько синих точек. Некоторые
из них соединены отрезками. Назовем точку "особой", если более по-
ловины из соединенных с ней точек имеют цвет, отличный от ее цвета.
Особые точки разрешается перекрашивать: на каждом шагу выбира-
ется любая особая точка и перекрашивается в другой цвет. Докажите,
что через несколько шагов не останется ни одной особой точки.
14) В парламенте у каждого его члена не более трех врагов. Дока-
жите, что парламент можно разбить на две платы так, что у каждого
парламентария в одной с ним палате будет не более одного врага.
15) На прямой по порядку расположены точки A 1 ; A 2 ; :::; A n так, что
длины отрезков A 1
A 2
; A 2
A 3
; :::; A n-1 A n не превосходят 1. Требуется от-
метить k - 1 из точек A 2 ; :::; A n-1 красным цветом так, чтобы длины
любых двух из k частей, на которые отрезок A 1 A n разбивается крас-
ными точками, отличались не более чем на 1. Докажите, что это всегда
можно сделать: а) для k=3;
б) для каждого натурального k < n - 1.
2