Олимпиадные задачи по математике начального уровня..
65
тель – с
(1)n −
человеком, то есть общие хоть в чем-то вкусы не бо-
лее, чем с
3( 1) 3 3nn−= −
людьми, а групп
(3 2)n
. Следовательно,
всегда существует группа, в которой нет людей, вкусы которых пе-
ресекаются со вкусами этого человека, и куда его можно поместить,
не нарушая требований условия задачи. Таким образом, мы можем
разместить всех участников по
(3 2)n −
группам в соответствии с
требованиями задачи.
3.
Решение: а) если все прямые параллельны друг другу, то они
делят плоскость на
(1)n
областей. При этом все области не могут
быть окрашены, тем самым число окрашенных областей не превос-
ходит
n
. Утверждение верно, так как
2
121
333
nn n
nnn
+++
⋅≥⋅=
;
б) пусть теперь не все прямые параллельны друг другу. Граница ка-
ждой области состоит из нескольких отрезков и лучей, принадле-
жащих разным прямым. Эти отрезки и лучи назовем сторонами об-
ласти. Каждая область имеет не менее двух сторон. Через
2
m
обозначим число окрашенных областей, имеющих две стороны, че-
рез
3
m
обозначим число окрашенных областей, имеющих три сто-
роны, и так далее. Наконец, через
k
m
обозначим число окрашенных
областей, имеющих максимальное число сторон. Покажем, что
k
mn≤
. Граница любой области с двумя сторонами состоит из двух
лучей, причем каждый луч может лежать на границе только одной
из окрашенных областей. Число всех таких областей не превосходит
2n
, не более двух на каждой прямой. Следовательно, общее число
сторон окрашенных областей с двумя сторонами не превосходит
2n
или
2
mn≤
. Каждая из
n
прямых разбивается остальными не более,
чем на
n
частей, отрезков или лучей. Поэтому общее число всех
частей не превосходит
2
n
. Каждая из частей является стороной не
более одной из окрашенных областей. Следовательно, общее число
сторон таких областей не превосходит
22
23
2 3 ...
k
nmm kmn⇒+++≤
.
Число окрашенных областей равно
23
...
k
mm m+++
. Используя до-
казанные выше неравенства, находим, что
22
223
23
2 3 ...
...
33333
k
k
mmm kmnnnn
mm m
+++ +
+++≤ + ≤+=
.
4.
Решение. Утверждение задачи следует из двух замечаний.
Учебное пособие
66
1. Если внутренний узел квадрата переходит в граничный узел
прямоугольника, то его четыре соседа (по горизонтали и вертикали)
также переходят в граничные узлы прямоугольника, причем на той
же стороне (исходный узел не мог перейти в угол). Это сразу следу-
ет из того, что взятый узел и его соседи – это центр и
вершины
квадрата со стороной
2
и площадью 2.
2. Если
ab
, то у квадрата внутренних узлов больше, чем у
прямоугольника. Действительно, у квадрата их
2
(2)n −
, у прямо-
угольника
2
( 2)( 2) ( 2) ( 2)( 2) 2( 2 ),ab n ab abn−−⇒−−−−=+−
2ab n+>
, так как при постоянном произведении
2
ab n=
сумма
минимальна, когда сомножители равны. Итак, если
ab≠
, то суще-
ствует внутренний узел квадрата, которому соответствует гранич-
ный узел прямоугольника, а тогда, применяя много раз случай 1),
получим, что все узлы квадрата перешли в узлы одной стороны
прямоугольника, что невозможно. Поэтому,
ab
.
5.
Решение. Легко проверить, что множество
1,2,3,5,10,20,25,
50,100
из 9 элементов удовлетворяет условию задачи. Покажем,
что меньшим числом элементов обойтись нельзя. Расположим эле-
менты произвольного множества, удовлетворяющего условиям за-
дачи, в монотонном порядке:
12
1 ... 100
n
aa a
<<<=
. По условию
при любом
1k >
справедливо равенство
;
kpq
aaa
+
,
qk<⇒
1
2
kk
aa
⇒≤
. Но для всех значений
k
равенства
1
2
kk
aa
−
не могут
быть выполнены, так как 100 не является степенью двойки. Таким
образом, хотя бы для одного
kn
выполнены неравенства
12 2
3
kk k k
aa a a
−−
+≤
. Теперь запишем
2
12
100 2 2 ...
nn n
aa a
−−
≤≤⋅≤
1
23
232 32 ..
nk nk nk
kk k
aa a
−− −+
−−
≤⋅≤⋅⋅≤⋅ ⋅≤
3
1
32
n
a
−
⋅⋅⇒
3
2
n−
≥
6
100
(2 64) 3 6 9
3
nn≥=⇒−≥⇒≥. Существует много других
примеров нужных множеств. Таковыми являются, например, мно-
жества
1,2,4,6,10,20,30,50,100 ;
1,2,4,8,16,32,64,100
.