Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/02/20.pdf Дата изменения: Fri Dec 23 19:25:05 2005 Дата индексирования: Tue Oct 2 00:11:53 2012 Кодировка: Windows-1251 Поисковые слова: stonehenge

неверно. Покажем, что тогда существует такое заполнение клеток прямоугольника числами, при котором сумма всех чисел положительна, а сумма чисел в клетках, закрываемых фигурой при любом ее положении, неположительна. Введем обозначения: индексом j, j = 1, ..., m Ч n, будем нумеровать клетки прямоугольника, индексом i, i = 1, ... ..., k, положения фигуры Ф на прямоугольнике. Положим Pij = 1, если j-я клетка закрыта фигурой Фi , Pij = 0, если не закрыта. Тогда набору чисел di соответствует заполнение клеток прямоугольника числаdi Pij , характеризующими уклонение ми j = 1

объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из любого незакрытого города в любой другой, не делая пересадок в закрытых городах. Рассмотрим граф, вершинами которого являются города, ребрами авиалинии. По условию получится связный граф, степени вершин которого равны трем. Предположим, что в графе есть два пересекающихся (по вершине) цикла. Тогда рассмотрим вершину О, в которой они 'разветвляются'. Эта вершина, очевидно, имеет степень три. Удалим эту вершину и три выходящих из нее ребра ОА, ОВ, ОС. Нетрудно заметить, что граф сохранил связность, так как существует путь, соединяющий вершины А, В и С. Рассмотрим полученный граф. Если в нем есть два пересекающихся цикла, то повторим операцию, и так далее. Очевидно, что никакие две удаленные вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени три, а после каждой операции степени вершин, соседних с удаленными, уменьшались, т.е. они не могут стать равны трем. Предположим, что в связном графе n вершин и не менее 4 чем n ребер. Докажем, что в таком графе обязательно 3 есть два пересекающихся цикла. Предположим, что это не так. В силу связности графа в нем можно выделить дерево с n вершинами. Будем 'возвращать' в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает количество циклов по крайней мере на один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее чем три вершины, и никакая вершина не входит в два цикла. Кроме того, дерево с n вершинами содержит ровно n 1 ребро. n 4n Следовательно, ребер не более чем n - 1 + < . 3 3 Противоречие. Пусть N = 1998 исходное количество вершин, тогда 3 исходное количество ребер равно N . За каждую опера2 цию выкидывания вершины количество вершин уменьшается на одну, а количество ребер уменьшается на три. Предположим, что было сделано х операций. Тогда стало 3 N 3х ребер. До тех пор, пока N х вершин и 2 3 4 выполняется неравенство N 3 x N - x , вершины 2 3 N удалять можно. Решив это неравенство, получаем x , 10 1998 т.е. можно удалить + 1 = 200 вершин. Отсюда и 10 следует утверждение задачи. Д.Карпов, Р.Карасев Ф1668. Автомобиль выезжает из города А и приезжает, двигаясь без остановок по прямому шоссе, в город Б. Оказалось, что в течение первой половины времени поездки его скорость была 40 км/ч, половину оставшегося пути он проехал со скоростью 60 км/ч, а остаток пути со скоростью 80 км/ч. Найдите среднюю скорость автомобиля за все время путешествия.

mr


i

покрытия прямоугольника фигурами от равномерного. По нашему предположению все числа j не могут быть равными нулю. Выберем числа d j 0 так, чтобы величина уклонения была минимальна, где
2

=


j

2 . Покажем, что полуj

чившиеся числа j образуют искомое заполнение клеток прямоугольника. При этом обоснование существования набора di , который минимизирует , читатель без большого труда проведет самостоятельно. Заменим одно число di на di = di + х, x - di . Тогда

mr

j = j xPij , следовательно,

2

=

2x


j

j Pij + x

2


j 2

Pi2 , т.е. j

2

= y x = ax2 2bi x +

bg


j

2 j =


j



2 j



+с. Здесь а =


j

Pi2 = j


j

Pij = N, где N число клеток

в фигуре, с = . Квадратный трехчлен у = y x , заданный на множестве x - di , принимает наименьшее значение при х = 0 в случае bi = 0, если di > 0, и в случае bi 0, если di = 0. Таким образом, предположив, что минимален на наборе { di }, мы получаем, что если di > 0, то bi =

bg


j

j Pij = 0, а если di = 0, то bi 0. Значит, сумма

b

g

чисел, закрываемых фигурой Фi , а это


j

j Pij ,

неположительна; с другой стороны, сумма всех чисел в прямоугольнике положительна, так как она равна а


j j

j =


КВАНT 1999/?2

=

2 j

F G1 - G H
j j j j




j

j ,

2 . Действительно, j
di Pij

=


j

I JJ = FGG H K
j

j -

d e
i i j

j Pij

j

i,di > 0



j Pij =


j

I jJJK

b

g

=

j ,

LM N

OP Q

так как bi = 0 при di > 0. Этим завершается решение задачи.

А.Белов

М1660*. В стране 1998 городов. Из каждого осуществ-

ляются беспосадочные авиарейсы в три других города (все рейсы двусторонние). Известно, что из любого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет

20