задача на Силвестър

[Belov]

Смятам че за лубителите на нестандартни задачи тази ще е лесна. Моля Boyan да не поства решение защото той е решавал задачата с мен
Ето я и нея:
Нека М е множество от точки в равнината с повече от 3 точки.
М има следното свойство: като прекараме права през 2 точки от М, то и трета точка от М лежи на тази права. Да се докаже че всички точки от М лежат на една права.

[Реклама]

[Titu_Andrescu]

)))) Какво е това бе човек. Нещооо не схващам, ебаваш се нали?

[krassi_holmz]

Белов, имам 2 забележки към условието -
1. (не толкова съществена) Не е необходимо да
имаме повече от три точки. Твърдението от
задачата е вярно и когато точките са 3.
2. (съществена) броят на точките трябва да е
краен. За да се убедите в това, можете да
разгледате множество от точките с целочислени
координати в равнината.

[Belov]

Ами всъстонст е необходимо да имаме повече от 3 точки, защото то иначе ще е очевидно и за тва е дадено условието така, а колкото до решението тва не е мн така щот е възможно след известно време правите да се пресичат в 1 и същи точки и множеството да е крайно пак... и да не лежат на 1 права. Въпросът е в строгото доказателство, до което се надявам да стигнете, иначе наистина си прав че е мн съществено че са краен брой но искам сторого доказаталество на задачата


П.С.: Задачката е мн хубава... решавахме я май 7клас... разбирасе никой не я реши ма от тогава я помня и май никога няма да я забравя

[Titu_Andrescu]

НЕзнам, не мога да те разбера..

[krassi_holmz]

Ok.
Принципно тази задача се доказва с помощтта на нейната дуална и с теоремата на Ойлер за равнинни карти, но любимото ме доказателство е с метода на крайния елемент:
Нека точките изпълняват условието на задачата и не лежат на една права.
Понеже точките са краен брой, то ще съществува такава, която е най-близо до някоя права и не лежи на нея. Нека това е точката А, а правата, която е най-близо до А е р. Пускаме перпендикуляр l от А към р с пета H. Понеже върху р лежат поне 3 точки, поне 2 от тях ще са в една и съща полуравнина спрямо l. Нека това са точките B и C, като B e по-близко до AH, отколкото C. Но сега разстоянието между B и новата права AC е по-малко от AH. Противоречие!
Това доказателство показва колко е съществено точките да са краен брой - иначе нямаше да можем да използваме принципа на крайния елемент! Например за примера който дадох с целочислената решетка, за всяка точка от нея съществува права, която е на разстояние по-малко от е, колкото и малко да е е.

[Belov]

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

[krassi_holmz]

Тука май аз се изразих неправилно - става дума за формулата на 0йлер за равнинните графи:
V-E+F=2.
Една забележка - тая задача е много извесна. Известна е катозадача на Силвестър. Интересно е, че е доказана 40 години след като я е открил.

[Boyan]

много е хубава задачата

[OliGoFren]

А не може ли да се докаже и с метода на пълната математична индукция? Пoне на мен ми хрумна следното доказателство. Ще се радвам, разбира се, ако някой ми посочи евентуални грешки, които съм допуснал. и така, доказателството.

Означаваме твърдението "всички n на брой точки лежат на една права" с S(n).
Вземаме за база на индукцията случая с три точки. При него очевидно е изпълнено твърдениет S(3) = "всички 3 на брой точки лежат на една права".
Допускамe, че S(n) е изпълнено за някакъв краен брой точки n. Да ги означим с А₁, А₂, ... , А_n. Да означим праватa, на която лежат с p. Добавяме към тях още една точка А_n+1. Съгласно условието на задачата има някое естествено число i (1 <= i <= n-1), такова че точката А_i лежи на правата A_nA_n+1. Но понеже A_n и A_i лежат на прават p, то следва, че и A_n+1 лежи на същата права. Значи изпълнено е и S(n+1). С това доказателството е завършено.
Какво ще кажете?

[krassi_holmz]

В индуктивното ти доказателство наистина има грешка - нещото е известно като обърната рекурсия и е често срещано. Ти приемаш, че S(n+1) се получава от S(n) чрез прибавяне на една точка, но не си доказал че това винаги е така.

Един пример:
Задача: Да се намери минималното h(n), такова че същестува граф с n върха и h(n) ребра, който не съдържа 4-клика и със свойството ако прекараме ребро между произволни два ннесвързани върха да се получи граф, съдържащ 4-клика.

Отговора на задачата е 1+2(n-2) = 2n - 3, като екстремалния граф е [tex]K^2+E^{n-2}[/tex]. Доказателството може да се извърши по индукция по следния начин (неправилен):

Нека G e граф с n върха и h(n) ръба, изпълняващ условието. Ако прибавим още един връх към G, той трябва да е минимум от 2-ра степен, за да са изпълнени условията за новия граф. Тогава h(n+1) >= h(n) + 2.
Проблема тук е че сме предположили, че всеки граф G, изпълняваш условието съдържа подграф G' с едно рабра по-малко, изпълняващ условието. За да е вярно доказателството, остава да докажем и това:
Нека x е връх с минимална степен от G. Ако x>=3, броят на върховете в G е по-голям от h(V(G)) и G не ни интересува.
Задължително е d(x) = 2. Но сега за всеки четириъгълник с един връх x, който би се получил от прибавяне на ребро pq, е задължително p==x или q==x, значи G/x също изпълнява условието на задачата.

[tanas]

Аз ще предложа една подобна задача, попаднала ми неотдавна.Опитайте я, не е много трудна:

Нека М е крайно множество от отсечки в равнината.
М има следнете свойства:
1.Всеки две прави имат точно една обща точка.
2.През всяка пресечна точка на две прави, минава и трета права.
Да се докаже, че съществува точка, която лежи едновременно на всички прави от М.

[krassi_holmz]

Ами това е точно дуалната та теоремата на Силвестър, и от проективната геометрия знаем че две дуални задачи са еквивалентни.

[tanas]

[krassi_holmz]

[Baronov]

В тази връзка може да пробвате и следната леко усложнена задача:
Дадени са 2 крайни множества от точки в равнината А и В такива, че правата през всеки 2 точки от А съдържа точка от В и обратно. Да се докаже, че всички точки са на една права.

[krassi_holmz]

Интересно обобщение.
За да го докажа, ми бяха нужни два случая.
1. Да приемем, че съществува права определена от две точки от едно и също множество, такава че същесвува точка от другото множество която не е между двете едноцветни. Нека наречем такава права външна. Сега очевидно множеството от външни прави е крайно, защото А и В са крайни. Дефинираме А-множество от външни прави като множеството от външни прави, определени от две А-точки и аналогично дефинираме множеството от В-прави. Сега можем да изберем външна права р и точка А, нележаща на р, като А и р принадлежат на различни "множества", за които разстоянието между А и р е минимално (ако това не е възможно, значи всички точки лежат на една и съща права). Нека р е определена от точките B и C, които са от множеството В. Тогава понеже p е външна права, съществува точка от А върху р, външна за отсечката ВС. Нека това е точката D и Б.О.О. приемем, че BD>CD. Тогава, както се вижда от фиг.1 разстоянието от C до AD е по-малко от разстоянието от А до p, което противоречи на избора на а и p.

2. Ако няма външни прави, това означава, че за всеки две точки от едно множество, всички точки от другото множество, колинеарни на двете, лежат между тях. Сега избираме права р и точка А, нележаща на нея, от различно "множество", такива че разстоянието между тях е минимално (ако това не е възможно, тогава всички точки лежат на права). БОО нека точките В и С от множството В определят правата р и А е от множеството А. Сега съществува точка D от множеството A, лежаща между В и С. Следователно съществува точка F от множеството В, лежаща между D и A и съществува точка Q от множеството А, между F и C (фиг 2). Сега е ясно, че разстоянието от Q до p е по-малко от разстоянието от A до р.
Reductio ad absurdum.