IMO 2007

Ето ги и задачите от тазгодишната Международна Олимпиада.

[линк]

Това което на мен ми напрaви впечатление е доста тривиалната геометрия , а също и слуховете че Виетнамския отбор има 0 точки на една от геометричните задачи !!?


Es fickt mich nicht

Даже ги има и на български език:

[url]
[линк]
[\url]
[url]
[линк]
[\url]

Ееее, чак пък 0 на геометрична. Резултатите ги има на сайта на олимпиадата ; имат 0 на 6-та (ако нея броиш за геометрична), но там много други имат толкова ; ние примерно имаме 2.

На 6-та задача съм доста сигурен, че отговора е 2*n-1. Някой може ли да го докаже или отхвърли?

Ми мен ми се струва, че още при n = 2 ще се узориш ...

като начало минимума трябва да покрива доната равнина която е квадрат от точките х,у където х + у > 0 и х,у <= n и това трябва да стане с прави за което май няма как да сколасаш с по малко от 2n а с 2n става тривялно....

иначе е някъде между 2н + 1 и 3н ама съм до тук за сега ...

да нямаш случайно в предвид 2n+1 понеже 2n-1 e май грешен отговор, примерно за n=1 (7 то4ки на върховете на куб със страна 1, без осмия връх (0,0,0)) могат да бъдат покрити с три равнини но не и с една разбира се.

дай 2D първо понеже там е лесно да се визуализира - имаме решетка в първи квадрант на координатна с-ма на която е махнат центъра (0,0), с колко най-малко линии може да покрием решетката? ако там го измисли човек трябва да стане и в 3-д...

На мен лично ми е малко трудно да разбера примера даден за n=1 ...
Обаче за нарисуваната двумерна решетка е ясно че може да се покрият целочислените й точки (без нулата/началото) с 2n прави.
Рисуваме куба, стават 2n равнини, но ни трябват още n равнини, за да покрием точките "над" нулата. Тъй че с 3n равнини може (това беше казано преди мен). Тоест отговорът е най-много 3n, но вероятно доста по-малко.
Ако ползваме диагоналните прави, сключващи ъгъл 45 градуса с осите, само
2n-1 прави са достатъчни да покрият решетката в равнината. С други думи, може и с 3n-1 равнини. Следващият резонен въпрос е: "А какво става ако разгледаме телесния диагонал на хиперкуба и покриваме точките с равнини, перпендикулярни на него? Колко такива равнини има?"
Разбира се, трябва да докажем, че никакъв друг "микс" от равнини не е по-добър, което поне на мен засега не ми се удава.
Или пък да преброим точките във всяка хиперравнина, перпендикулярна на телесния диагонал свързващ (0, ..., 0) с (n, ..., n).

"Ако ползваме диагоналните прави, сключващи ъгъл 45 градуса с осите, само
2n-1 прави са достатъчни да покрият решетката в равнината."

tva to4no ne mi stava qsno kakvo imash v predvid, naprimer v 2D i n=1 iskash da kazesh 4e mozem da pokriem s 2*1-1=1 pravi? pri n=1 imash 3 to4ki v ravninata - 3-te vurha na kvadrat, bez (0,0). tam ni trqbvat 2 linii.

Сгрешил съм. Имах намерения да изправя куба върху единия ъгъл и да го сеча със хоризинтални равнини. Ето така:



В случая обаче броят равнини е:
4*(n-1)

Вероятно има и по-добро решение.

Значи дотук стигнахме че никой не намира покритие с под 3n равнини (твърдящите обратното да си погледнат пак чертежите). Почвам да си мисля, че това е верният отговор, откъдето следва, че трудната част е втората (както се и предполагаше). чудя се няма ли как да има алгебрично решение - с уравненията на равнините да се докара някой полином, който да се окаже, че има прекалено много корени и трябва да е поне от степен 3n (или в противен случай да е тъждествено нула, което да е еквивалентно на това някоя от равнините да минава през (0,0,0). Продължавам да размишлявам.

Изглежда, че ъгълът под който съм пускал равнините не е бил оптимален. Така е по-добре:



И вече е 3*(N-1)

В момента не мога да видя картинката, но фсе пак ми е любопитно как процедираш в случая н=1 и н=2. Особено в първия от тях.

При n = 1 има само една точка и задачата не е интересна. При n = 2 има куб от 8 точки и се решава със 3 равнини.

Сега като чета пак условието на задачата изглежда, че имам разлики в началото на индексите. При мен започват от 1, което е направо за срам, защото при тях започват от 0, а аз не съм програмирал на Бейсик от 500 години. Значи формулата ми всъщност е 3*n.

За доказване че може с 3n равнини все дават една точица, ако се поизглади идеята за полинома - още една, демек поне Виетнам бием ;)

Не мисля, че ще дадат 1 точка за доказване, че може с 3н .... то не може да бъде по тривялно .....

Според мен биха дали 1 точка за решаване на равнинната задача (където трябва да е 2н отговора с прави) но пък за това може и да дадат повече....

i se kazva:es fickt mir nicht!:)

Значи ето как става в 2Д за 3Д сигурно нещо подобно ще мине но не мога да мисля сега ...трябва и да се работи ....

Значи за 2Д става дума за покриването на квадрат с прави и отговора е 2н.
За да се докаже трябва да се разгледа по общата задача за покриване на правоъгълник МхН с прави и да се каже, че мин е М + Н прави (как става с М+Н прави е ясно).

За да го докажем ще отбележим:

1х1 е тривялно

Нека сега да вземем да допуснем, че има поне 1 правоъгълник МхН който може да се покрие с по малко от М + Н прави -> от всичките тия има поне един който има свойството М + Н да е минимално, демек този с най малка сума на страните...

Сега за него ще разгледаме няколко интересни факта.
1. той се покрива с М+Н-1 прави (ако са по малко ще вкараме няколко излишни)
2. да разгледаме най дясната и най горната страни на квадрата.

а) Ако някоя от тях е покрита от цяла права (да речем дясната) махаме тази права (в същност махаме цялата дясна стена) и получаваме правоъгълник М-1хН който се покрива с М + Н -2 (всичките без най дясната от МхН случая) тоест този който сме взели не е с мин М+Н -> кофти.

б) ако нито дясната нито горната страни са покрити от права то тогава ще разгледаме точките по контура на квадрата. Те са 2м + 2н -1 (без 0,0) на брой и всяка една от участващите прави може да мине най много през 2 от тези точки (щото иначе или ще минава през 0,0 или ще е горна или дясна) -> трябва да има поне м+н прави

Та за 3Д си мисля, че може да се ползва подобно разъждение, или може да се разглеждат на равнините пресечниците с дадена равнина и да се ползва горното като лема и тн ..... ще си помисля, но няма да е сега :((