Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/autumn06/t4-23kozh.pdf Дата изменения: Sun Nov 5 19:35:02 2006 Дата индексирования: Sun Dec 23 01:00:33 2007 Кодировка: IBM-866 Поисковые слова: р п р п р п р п р п р п п р п п р п п р п п р п п р п п р п п р п п р п

рупп " йфу ". омби тор я геометрия: отрезки, прямоугольики, п р ллелепипеды... орция 1. 1.1. прямой р сположео есколько отрезков т к, что к ждый пересек ется е меее, чем с половиой из ост вшихся. ок жите, что екоторый отрезок пересек ется со всеми ост вшимися. 1.2. прямой р сположео есколько отрезков т к, что к жд я точк покрыт е более, чем k отрезк ми. ок жите, что отрезки можо р зделить k семейств т к, чтобы в к ждом семействе отрезки е пересек лись. 1.3. оридор длиы l произвольым обр зом покрыли дорожк ми (коечым числом). ок жите, что можо убр ть екоторые дорожки т к, чтобы ост вшиеся дорожки покрыв ли весь коридор, и их сумм р я дли е превыш л 2l. 1.4. оридор длиы l произвольым обр зом покрыли дорожк ми (коечым числом). ждую дорожку р зрез ли попол м, и убр ли оду из полови. ок жите, что ост вшиеся половиы покроют е меее трети коридор . (. оми, из еигр дских олимпи д) 1.5.* ждый из семи ребят в воскресеье 3 р з к т лся коьк х к тке. звесто, что к ждые двое из их в екоторый момет были льду одовремео. ок жите, что в екоторый момет льду ок з лись одовремео трое ребят. (. дж с, из сесоюзых олимпи д) орция 2. 2.1. плоскости р сположео есколько прямоугольиков со сторо ми, п р ллельыми осям коорди т т к, что к ждый пересек ется е меее, чем с 3/4 из ост вшихся. ок жите, что екоторый прямоугольик пересек ется со всеми ост вшимися. 2.2. плоскости р сположео есколько р вых кв др тов со сторо ми, п р ллельыми осям коорди т т к, что к жд я точк покрыт е более, чем k прямоугольик ми. ок жите, что прямоугольики можо р зделить 2k - 1 семейств т к, чтобы в к ждом семействе прямоугольики е пересек лись. 2.3. столе 20 Ѕ 20 р зброс о 90 с лфеток 1 Ѕ 1 со сторо ми, п р ллельыми кр ям стол . ок жите, что можо положить еще оду т кую с лфетку, е пересек ющуюся с уже леж щими. орция 3. 3.1. столе р зброс ы прямоугольики (к к угодо) т к, что любые дв пересек ются. ок жите, что йдется прям я, пересек ющ я их все. 3.2. столе 20 Ѕ 20 р зброс о 95 с лфеток 1 Ѕ 1 (к к угодо). ок жите, что столе можо рисов ть круг ди метр 1, е пересек ющий с лфетки. 3.3.* простр стве р сположеы 12 прямоугольых п р ллелепипедов с ребр ми, п р ллельыми осям коорди т. ост вим в соответствие к ждому из п р ллелепипедов вершиу гр ф . ве вершиы соедиим ребром тогд и только тогд , когд соответствующие п р ллелепипеды е пересек ются. ожет ли гр ф ок з ться циклом длиы 12? (. копя | со сероссийской олимпи ды) 3.4.* ( г ж в метро) ожо ли в екотором прямоугольом п р ллелепипеде с суммой ребер местить екоторый прямоугольый п р ллелепипед с суммой ребер, большей d? (. еь, с осковской олимпи ды(?))
d

по-


оммет рии, ук з ия и решеия. ри решеии з д ч предложеой серии полезы могие ст д ртые подходы, т кие к к примееие идукции, прицип ирихле. собео ч сто и эффективо при решеии з д ч по комби торой геометрии примеяется прицип \кр йего", состоящий в р ссмотреии объект , выделяющийся екоторым особым свойством среди всех объектов. ч ло р ссуждеий по приципу кр йего может выглядеть, пример, т к: \среди коцов всех отрезков (коечого числ ) р ссмотрим с мый левый (т. е. имеющий имеьшую бсциссу)" или \р ссмотрим п ру с мых уд леых точек д ого коечого можеств ", и т. д. д чи порции 1 предст вляют серию по \одомерой" геометрии. 1.1. ешеие. усть д ы отрезки [ai , bi ], i = 1, 2, . . . , n. усть a = ai = max{a1 , a2 , . . . , an }, b = bj = min{b1 , b2 , . . . , bn }. сли a b, то все отрезки содерж т [a, b]. че более n/2 отрезков пересек ют [a, b], и з чит содерж т точку a (счит ем, что отрезок пересек ется с м с собой). кже более n/2 отрезков пересек ют [a, b], и з чит содерж т точку b. о приципу ирихле йдется отрезок, содерж щий и a, и b. тот отрезок пересек ет все отрезки. 1.2. бросок решеия. усть д ы отрезки [ai , bi ], i = 1, 2, . . . , n. римеим идукцию по n. усть a = ai = max{a1 , a2 , . . . , an }. юбой отрезок, пересек ющий [ai , bi ], покрыв ет ai , поэтому [ai , bi ] пересек ется е более, чем с k - 1 отрезк ми. ыбросив [ai , bi ] из р ссмотреия, примеим предположеие идукции к ост вшимся отрезк м. ерув [ai , bi ], покр сим его в цвет, отличый от цвет пересек ющихся с им отрезков. 1.3. бросок решеия. берем дорожку, если о покрыт объедиеием ост льых. осле коечого числ ш гов мы придем к т кой системе дорожек, что к жд я коридор покрыт е более, чем двумя дорожк ми. 1.4. к з ие. усть после уд леия полови мы пришли к объедиеию покрытых дорожк ми отрезков 1 , . . . , n . " здуем" k в три р з , т. е. р ссмотрим отрезок k , получеый из k гомотетией с цетром с его середие и коэффициетом 3. ок жите, что отрезки 1 , . . . , n покроют коридор. 1.5. бросок решеия. ремя пребыв ия к тке к ждого из ребят | объедиеие Ai трех поп ро епересек ющихся отрезков числовой оси t | итого у с можество E = 7=1 Ai из 3 § 7 = 21 отрезков i прямой. ожество V верши всех этих отрезков состоит из 42 точек (можо вершиы счит ть р зличыми). цеим число т ких п р (e, v), для которых отрезок e E содержит вершиу v V отрезк , отличого от e. ждое пересечеие Ai Aj д ет хотя бы две т кие п ры. огд всего т ких п р е меьше 23 = 42. роме того, с м я лев я верши из E е входит и в оду 7 т кую п ру, поэтому екотор я верши входит хотя бы в две п ры, т.е. екоторый коец отрезк покрыт двумя другими отрезк ми. тот коец отрезк соответствует искомому момету времеи. 2.1. д чи порции 2 "двумеры". десь быв ет полез идея поижеия р змерости | спроектиров в к ртику оси коорди т, мы приходим к "одомерым" з д ч м. бросок решеия. проектируем прямоугольики оси коорди т. етодом з д чи 1.1 пок жем, что йдется более n/2 прямоугольиков, проекция которых ось Ox пересек ется с проекцией любого из ост вшихся. зовем т кие прямоугольики x-подходящими. логичо, йдем более n/2 y-подходящих прямоугольиков. о приципу ирихле йдется прямоугольик, одовремео x-подходящий и y-подходящий. етрудо видеть, что о пересек ется со всеми ост льыми прямоугольик ми. 2.2. бросок решеия. ссмотрим с мый верхий из р вых кв др тов. им пересек ется е более 2(k - 1) кв др тов (к ждый из их содержит оду из двух ижих верши). лее, к к и в з д че 1.2, примеим идукцию по числу кв др тов. 2.3. к з ие. ля к ждого кв др т A произведем "р здув ие": р ссмотрим кв др т A , получеый гомотетией с цетром в цетре A и коэффициетом 2. в др ты A и B е пересек ются тогд и только тогд , когд A е содержит B . овершив р здув ие кв др тов, док жите, что ост ется место для цетр еще одого кв др т . итер тур : Dol'nikov V.L. Some Problems for Mathematical Olympiad. Combinatorial Geometry, CIMAT, Mexico, 2004.