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

рупп "р г ". четое коструиров ие. д чи.

орция 1. 1.1 ок жите, что можо осветить плоскость бескоечым бором прожекторов, освещ ющих углы в 1 , 1 , 1 , . . . 21n , . . . . 2 4 1.2 ок жите, что можо тур льые р сст вить в клетки бескоечой клетч той плоскости числ т к, чтобы к ждое число встреч лось рово оди р з, и чтобы любые дв числ из одой строки или одого столбц были вз имо простыми.

орция 2. 2.1. ок жите, что можество тур льых чисел можо р збить т кие бескоечые рифметические прогрессии с р зостями d1 , d2 , . . ., что d11 + d12 + . . . < 0, 1. 2.2. ок жите, что существует т кое подможество M тур льых чисел, что к ждое тур льое число предст вляется едиствеым обр зом в виде р зости двух чисел из M . 2.3*. ок жите, что можо окр сить целочислеые точки плоскости в 2006 цветов т к, чтобы к ждой прямой ( которой е меее двух целых точек) р скр ск был периодической, р скр ск плоскости е был периодической.


оммет рии, ук з ия и решеия. ту тему можо коротко ох р ктеризов ть к к "коструировие без явого предъявлеие кострукции". острукция строится в счетое число ш гов. ешеия з д ч очеь короткие, од ко придум ть их епросто. ребуется определеый вык, ощущеие приципи льой р зицы между в свойств х коечых и счетых можеств. 1.1. ешеие. окроем углом с омером k круг р диус k с цетром в ч ле коорди т. 1.2. ешеие. ереумеруем клетки. сст вляем числ 1, 2, 3, . . . по порядку по следующему пр вилу. первом ш ге пост вим число 1 в клетку с омером n. усть после n ш гов уже р сст влеы числ 1, 2, . . . , n, и клетк k | ез ят я клетк с миим льым омером. ост вим n + 1 в клетку с омером k, если n + 1 просто. че пост вим n + 1 в любую клетку т кую, что в ее строке и столбце еще е р сст влео чисел. ерез есколько ш гов клетк с омером k будет з ят , т к к к простых чисел бескоечо мого. 2.1. ешеие. одберем прогрессии с р зостями di = 2i+k для подходящего k. пишем выбор первых члеов ai . усть a1 = 1. сли a1 , . . . , an уже выбр ы, то пусть an+1 | имеьшее тур льое, е входящее и в оду из прогрессий (очему т кое число йдется? д же среди первых dn чисел?). к к к dn+1 делится d1 , d2 , . . . , dn , то прогрессия с омером n + 1 е пересек ется с уже определеыми (очему?). 2.2. бросок решеия. оложим a1 = 1, a2 = 2. усть a1 < a2 < . . . < a2k M уже определеы и т ковы, что в все р зости вид rij = aj - ai для 1 i < j 2k р зличы, и среди их есть числ 1, 2, . . . k . усть Rk | можество р зостей rij , и mk | м ксим льое из a1 , a2 , . . . , a2k . сли Rk k + 1, то положим a2k+1 = 2mk , a2k+2 = 2mk + k + 1. сли Rk k + 1, то положим a2k+1 = 2mk , a2k+2 = 4mk . огд a1 < a2 < . . . < a2k < a2k+1 < a2k+2 и т ковы, что в все р зости вид rij = aj - ai для 1 i < j 2k + 2 р зличы, и среди их есть числ 1, 2, . . . k + 1. 2.3. ешеие. ереумеруем прямые, содерж щие бескоечое можество целочислеых точек. ереумеруем целочислеые векторы. первом ш ге покр сим первую прямую периодичо, используя 2006 цветов. i-м (i 2) ш ге покр сим периодичо i-ю прямую (это возможо, т к к к до i-го ш г ей покр шео коечое число точек), з тем йдем две еще е покр шеые точки, отстоящие вектор с омером i - 1, и окр сим их в р зые цвет . з определеия процедуры вытек ет, что окр ск к ждой прямой периодич , о окр ск плоскости епериодич , т к к к е совмещ ется сдвигом и к кой целочислеый вектор.