Нарязване на пръчка- руска олимпиада

[drago]

Пръчка с дължина [tex]2[/tex] метра е разрязана на [tex]N[/tex]парчета. Всяко парче има целочислена дължина в сантиметри. За кое най-малко [tex]N[/tex] е гарантирано, че всички парчета могат да се наредят, че да оформят контура на някакъв правоъгълник без допълнително да се режат.

Давана на руска олимпиада, автор А. Магазинов.

[ptj]

n>101 (1X100, 100X1)

[drago]

OK, дотук добре
Сега остава да се покаже, че при N=102 от всичките парчетата винаги може да се нареди правоъгълник.
Хайде, няма нищо повече освен малко принцип на Дирихле!

[ptj]

[tex]n=102[/tex]

Очевидно има поне 2 с еднаква дължина (сумата на числата от 1 до 100 >200). Игнорираме тези 2 парчета и разглеждаме останалите 100, тяхната сума е [tex]2S\le 198[/tex].
Подреждаме числата във възходящ ред и разглеждаме [tex]a_1< a_1+a_2<a_1+a_2+a_3<a_1+a_2+a_3+a_4< ...<a_1+a_2+a_3+...+a_{100}[/tex]. Очевидно сред тези [tex]100[/tex] суми има поне [tex]2[/tex] даващи един и същ остатък при деление на [tex]S[/tex]. Тяхната разлика (набор от различни парчета) ще дава остататък [tex]0[/tex] при деление на [tex]S[/tex], но тъй като всички суми са различни, то се получава точно [tex]S[/tex]. T.e. този набор от разрези ще е точно половината сума.

[drago]

Браво, ptj!
Идеята ти е да отделиш първо 2 еднакви пръчки(такива има) и после да покажеш, че останалите 100 могат да се разделят на две купчинки с еднаква сума.
Може би това решение е по-кратко от моето !

[drago]

Понеже ме изтормозват с една друг задача във форума, та забравих тази.

Нека да представим пръчката с интервала [0,200] , а разрезите, които са 101 са вътрешни точки в този интервал. Да разгледаме двойките точки [tex]\{i, i+100\}, \, i=1,2,\dots, 99[/tex]. Тъй като точките (разрезите) са 101, ще има 2 точки, които попадат в една такава двойка, т.е. ще има разрези i, i+100 за някое i. От тази пръчка правим две пръчки- едната [tex][i, i+100][/tex], другата я правим, като "слепваме" [tex][0,i], \, [i+100, 200][/tex] /слепваме точките i и i+100/. Teзи 2 пръчки/интервали ги слагаме една над друга и гледаме, дали от останалите 99 разреза има 2, които попадат един над друг. Ако над точката на съединяване на [0,i] и [i+100, 200] има разрез в пръчката [i, i+100] всичко е ОК, ако няма тогава имаме 99 разреза в 98 точки една над друга. Т.е. ще има два разреза, които са един над друг. Тези 2 и предишните 2 разреза разделят интервала на търсените страни, от които става правоъгълник.