Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/autumn06/u5-1kozh.pdf Дата изменения: Sun Nov 5 18:30:08 2006 Дата индексирования: Sun Dec 23 00:54:56 2007 Кодировка: IBM-866 Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п р п р п р п р п р п р п р п п п п п п п п п

рупп "р г ". дея цикличости (в р зых проявлеиях). д чи.

орция 1. 1.1. ешите систему ур веий ) для n = 9; ) для n = 10.
x1 + x2 = x2 + x3 = . . . = xn + x1 = 2

1.2. выпуклом могоугольике все углы р вы. звесто, что вутри его есть точк , из которой все стороы виды под р выми угл ми. ок жите, что этот могоугольик пр вильый. 1.3. футбольом первестве уч ствуют 20 ком д. ок жите, что после двух туров можо выбр ть 10 ком д, среди которых ет двух уже сыгр вших. 1.4. меются кр сые и сиие бусики. ост вляется ожерелье из 20 бусиок. о зыв ется хорошим, если в ем ет двух кр сых бусиок, между которыми рово k - 1 бусиок. кое ибольшее количество кр сых бусиок может быть в хорошем ожерелье, если ) k = 2; б) k = 3; в) k = 4; г) k = 5. 1.5. усть
m | тур льое число, fn f1 = f2 = 1, fn+1 = fn + fn-1 .

| последов тельость ибо ччи:
fn fn

) ок жите, что последов тельость ост тков б) ок жите, что йдется т кой омер n, что

при делеии делится m.

m

периодич .

орция 2. 2.1. пересечеии пяти отрезков получе пятикоеч я звезд . е веший котур состоит из 10 отрезков. скр сим эти 10 отрезков поочередо в кр сый и сиий цвет . ожет ли ок з ться, что любой кр сый отрезок длиее любого сиего? 2.2. ескоеч я последов тельость цифр 9, 6, 2, 4, . . . строится по пр вилу: к жд я следующ я цифр р в последей цифре суммы предыдущих четырех. стретится ли в этой последов тельости четверк идущих подряд цифр 2, 0, 0, 7? 2.3.* гр фе к жд я верши имеет степеь е меьше длиы е меьше k + 1. 2.4. ешите з д чу 1.4 для произволього числ
n k 2.

ок жите, что в гр фе имеется цикл
k [n/2]

бусиок в ожерелье и любого

.


оммет рии, ук з ия и решеия. дея з циклив ия, цикличости т к или и че присутствует во могих олимпи дых з д ч х. д ой серии предст влеы з д чи р зообр зой тем тики ( лгебр , геометрия, делимость, комби торик ), объедиеые этой общей идеей. 1.1. ) ешеие. метим, что x1 = x2 = . . . = xn = последов тельо получ ем, что x2 < 1, x3 > 1, . . . , приходим к противоречию, если x1 < 1. б) бросок решеия. з условия вытек ет, что xi то р сстояие от xk до 1 увеличив ется с ростом k. 1.2. ешеие. усть
1 | решеие. x9 > 1, x1 < 1 [0; 2].

усть x1 > 1. з р веств | противоречие. логичо
x1 = 1

етрудо док з ть, что если

,

A1 A2 . . . An | могоугольик, и O | точк вутри его. з р веств A1 A2 A3 = A2 A3 A4 = . . . = An A1 A2 = (n-2) , A1 OA2 = A2 OA3 = . . . = An OA1 = 2n следует, что n OA1 A2 = OA2 A3 = . . . = OAn A1 . реугольики OA1 A2 , OA2 A3 , . . . , OAn A1 подобы, поэтому OA1 /OA2 = k, OA2 /OA3 = k, . . . , OAn /OA1 = k. ереможив р веств , получим k = 1, откуд OA1 = OA2 = . . . = OAn .

1.3. бросок решеия. ост вим гр ф сыгр ых игр. з к ждой вершиы выходит дв ребр , поэтому гр ф предст вляет собой объедиеие епересек ющихся циклов. ти циклы четой длиы (цикл ечетой длиы е может быть сыгр в дв тур ). з к ждого цикл дост точо выбр ть половиу ком д, е игр вших друг с другом. 1.4. м. общий случ й в з д че 2.4. 1.5. ешеие. ыпишем последов тельость ост тков чисел ибо ччи при делеии m: r1 = 1, r2 = 1, . . .. порядочеых п р ост тков коечое число, поэтому йдутся омер i = j т кие, что ri = rj и ri+1 = rj +1 . ст тки ri и ri+1 одоз чо определяют последующий и предыдущий ост тки, поэтому последов тельость ост тков периодич с периодом l = j - i. з периодичости вытек ет, что rl+1 = rl+2 = 1, откуд rl = 0. 2.1. к з ие: ля пяти треугольиков, содерж щих кр сую и сиюю стороы, примеим утверждеие о том, что против большей стороы лежит больший угол. 2.2. твет: встретится. бросок решеия: логичо з д че 1.5 док жем, что последов тельость периодич . егко видеть, что появлеию четверки 9, 6, 2, 4 предшествует четверк 2, 0, 0, 7. 2.3. ешеие: ойдем по ребр м гр ф , чи я с екоторой вершиы A0 . ждый р з будем переходить в вершиу, в которой мы еще е побыв ли, если это возможо. ссмотрим момет, когд мы прошли пусть A0 A1 . . . An и уже евозможо пройти в овую вершиу это уже евозможо. то оз ч ет, что k ребер ведут из вершиы An в вершиы из можеств A0 , A1 , . . . , An-1 . озьмем Ai , соедиеую с An , для которой омер i имеьший. огд i n - k, и An-k An-k+1 . . . An | искомый цикл. 2.4. бросок решеия: оедиим п ры верши, между которыми k - 1 буси. то "гр ф з претов": две кр сые вершиы е могут быть соедиеы ребром. усть d =(n, k). огд гр ф р сп д ется d циклов длиы n/d. к ждом цикле может быть е более половиы кр сых верши, и [n/2d] кр сых верши покр сить можо. твет: d[n/2d].