две задачки

[avva]

Разбирая всякие очень старые бумаги, наткнулся на несколько листов с задачками примерно-олимпиадного стиля. Вот две из них, обе геометрические, решения которых мне запомнились с тех времён своей изобретательностью. Профессиональным математикам: если задачки для вас тривиальны, не обессудьте . Всем: если интересно, попробуйте решить.

Хотелось бы считать это прелюдией к длинной записи о мат. доказательствах, которую давно хочется сформулировать, но не получается.

1. Дана фигура на плоскости. Всё, что о ней известно - её площадь строго меньше единицы. Расчертим на плоскости целочисленную координатную сетку (т.е. горизонательные и вертикальные линии на расстоянии 1 друг от друга). Доказать: данную фигуру можно так положить на плоскость, что она не пересечёт ни одну вершину сетки (т.е. ни одно перекрестье линий).

2. Дано некоторое конечное кол-во точек на плоскости со следующим свойством: если провести прямую через любые две из них, эта же прямая пройдёт ещё через какую-то из данных точек (к-я необязательно будет находится между двумя начальными). Доказать: все точки находятся на одной прямой.

Если правильные решения не появятся в комментах, то запощу их сюда через сутки.

Update: появились первые решения... но пока неправильные ;)
Update: появилось правильное решение первой задачи в комментах. Правильное решение второй, если там не появится, запощу не завтра утром, а послезавтра по просьбе товарищей.

Comments

[henic.livejournal.com]

Ïî÷åìó "÷óäîì"? íàïðèìåð, åñëè íàðîä îáëîìàåòñÿ ðåøàòü...

[avva.livejournal.com]

Âîò ÿ òîæå ïîäóìàë è óáðàë ýòî èç çàïèñè ;)

[henic.livejournal.com]

Ñ ïëîùàäüþ - íàâåðíîå îò ïðîòèâíîãî... Åñëè íåëüçÿ òàê ïîëîæèòü, çíà÷èò, âêëþ÷àåò ÄÂÅ óçëîâûå òî÷êè. À òîãäà - èç-çà ðàâíîöåííîñòè êîîðäèíàòíûõ èçìåðåíèé - ÷åòûðå.
íî òîãäà åå ïëîùàäü áîëüøå åäèíèöû, ò.ê., ýòî ìèíèìàëüíûå èçìåðåíèÿ >1 (èíà÷å ìîæíî áûëî áû ñäâèíóòü ñåòêó).
À ñ òî÷êàìè íà ïðÿìîé - ñìåñü èíäóêöèè è ìåòîäà "îò ïðîòèâíîãî"?

[avva.livejournal.com]

Åñëè íåëüçÿ òàê ïîëîæèòü, çíà÷èò, âêëþ÷àåò ÄÂÅ óçëîâûå òî÷êè.

Ïî÷åìó? ß óæå çà ýòèì øàãîì íå ìîãó óñëåäèòü.

×òî êàñàåòñÿ âòîðîé çàäà÷è - äàéòå ïîëíîå ðåøåíèå, òîãäà áóäåì ãîâîðèòü ;)

[muchacho.livejournal.com]

Áóäó÷è ìàòåìàòèêîì ïî äèïëîìó, òåì íå ìåíåå ïðèçíàþñü, ÷òî ðåøèòü ïåðâóþ çàäà÷ó ñàìîñòîÿòåëüíî ÿ íå ñìîã.
Âòîðàÿ ðåøàåòñÿ ïî èíäóêöèè (http://www.livejournal.com/talkread.bml?itemid=19044631).

[avva.livejournal.com]

Ïîçâîëüòå Âàñ îãîð÷èòü. Ðåøåíèå âòîðîé çàäà÷è íåâåðíîå; îøèáêà â ýòîì, äåéñòâèòåëüíî êàæóùåìñÿ âåñüìà ë¸ãêèì, äîê-âå íåòðèâèàëüíà, è ÿ íå ñòàíó ëèøàòü Âàñ óäîâîëüñòâèÿ íàéòè å¸ ñàìîìó :)

[henic.livejournal.com]

Óáèâåö :))) Òî ëèíãâèñòè÷åñêèå èçûñêè, òî ìàòåìàòèêà... Âòîðîé ðàç íå áóäó è ïûòàòüñÿ äîêàçàòü... :)
Íàäî áóäåò ÷òî-íèáóäü øàõìàòíîå ïîäêèíóòü...

[avva.livejournal.com]

Î, õîðîøàÿ èäåÿ. Êàêîé-íèáóäü ðåäêèé õîðîøèé ýòþä - íå õîòèòå?
Ìåæäó ïðî÷èì, ó ìåíÿ óæå áûë òàêîé îäèí ðàç, ñåé÷àñ íàéäó.
Âîò: http://www.livejournal.com/talkread.bml?itemid=5016378
Ðåêîìåíäóþ.
Åñëè ðåøèòå, òî çàïîñòèòå ðåøåíèå ãäå-íèáóäü: òàì, çäåñü, ó ñåáÿ - íåâàæíî ;) ìíå èíòåðåñíî ñî ñâîèì ñðàâíèòü.

[toshick.livejournal.com]

Âòîðàÿ çàäà÷à õîðîøà, íàä íåé íàäî âñåðüåç äóìàòü. Òàì âåäü íàäî äîêàçûâàòü ðàñõîäèìîñòü ïîñëåäîâàòåëüíîñòè òî÷åê.

Ïåðâàÿ - íà òåõíèêó. Ñòðîèì ïîêðûòèå ôèãóðû êîîðäèíàòíîé ñåòêîé ñ øàãîì d òàê, ÷òîáû ñóììà ïëîùàäåé êâàäðàòèêîâ, âêëþ÷àþùèõ òî÷êè ôèãóðû áûëà ìåíüøå 1 (ýòî ìîæíî ñäåëàòü ïî îïðåäåëåíèþ ïëîùàäè êàê æîðäàíîâîé ìåðû), ïîñëå ÷åãî ñòðîèì èñêîìóþ ñåòêó òàê, ÷òîáû îíà íå ïîïàëà â íàáîð èç êîíå÷íîãî ÷èñëà îäèíàêîâûõ êâàäðàòèêîâ. Íó òàì ïðîâåñòè îêðóæíîñòü â ïðàâèëüíîì ìåñòå òàêóþ, ÷òîáû îïèñûâàëà åäèíè÷íûé êâàäðàò, ïîñòðîèòü íà òîì êâàäðàòå ñåòêó è ïîâîðà÷èâàòü åå, èëè ïðîñòî äâèãàòü. Åñëè óòðåííÿÿ ëåíü ïðîéäåò, äîäåëàþ.

[toshick.livejournal.com]

óòî÷íåíèå (óòðåííÿÿ ëåíü ïðîøëà, íàâåðíîå):
Áåðåì øàã ìàëîé ñåòêè d=1/n, ñòðîèì îïèñàííîå âûøå ïîêðûòèå, êëàäåì íà íåãî ñâåðõó ñåòêó ñ øàãîì 1 òàê, ÷òîáû îíà ïðîøëà ïî ãðàíèöàì.
Ó êàæäîãî êâàäðàòèêà ìåëêîãî ïîêðûòèÿ åñòü êîîðäèíàòû â ñîîòâåòñòâóþùåì êâàäðàòå åäèíè÷íîé ñåòêè. Ïåðåíîñèì âñå êâàäðàòèêè, â êîòîðûõ åñòü òî÷êè ôèãóðû, â îäèí êâàäðàò, ñîõðàíÿÿ ýòè îòíîñèòåëüíûå êîîðäèíàòû. Êâàäðàò áóäåò ïîêðûò íå ïîëíîñòüþ (ñì. âûøå). Áåðåì ëþáóþ íåïîêðûòóþ òî÷êó, áåðåì òî÷êè ñ òàêèìè îòíîñèòåëüíûìè êîîðäèíàòàìè âî âñåõ êâàäðàòàõ åäèíè÷íîé ñåòêè. Ýòî è åñòü èñêîìîå ïîêðûòèå.

Äåéñòâèòåëüíî, ÷èñòàÿ òåõíèêà ìàòàíàëèçà.

[toshick.livejournal.com]

PS
Êñòàòè, òîãäà è ìåëêîå ïîêðûòèå ñòðîèòü íå íàäî. Ïðîñòî áåðåì ëþáóþ åäèíè÷íóþ ñåòêó, ðåæåì ôèãóðó íà êóñî÷êè, ïåðåíîñèì â îäèí êâàäðàò, èùåì â íåì íåïîêðûòóþ òî÷êó è ñòðîèì ïî íåé ñåòêó. Âñå.

[awp.livejournal.com]

Óïñ, ðåøåíèå ïåðâîé toshick óæå äàë. Âòîðàÿ - òîæå òðèâèàëüíà, ÷òîáû ÄËß ËÞÁÛÕ äâóõ òî÷åê íàõîäèëàñü íîâàÿ, íå ëåæàùàÿ íà ïðåäûäóùåé ïðÿìîé, èõ ìíîæåñòâî äîëæíî áûòü ÁÅÑÊÎÍÅ×ÍÛÌ.

ÿ áû òàê íå áðîñàëàñü ñëîâàìè -

[veroniq.livejournal.com]

òðèâèàëüíà, òðèâèàëüíà.
Ïðîñòîå ðåøåíèå íå åñòü îáÿçàòåëüíî òðèâèàëüíîå.

Îñîáåííî, åñëè ó÷åñòü, ÷òî âû òàê è íå äàëè ðåøåíèå âòîðîé :-), à ïðîñòî ïåðåôîðìóëèðîâàëè óñëîâèå.

Ìíå ïðèâîäèòü çäåñü ðåøåíèå íå î÷åíü ÷åñòíî. Âî-ïåðâûõ, ÿ ìàòåìàòèê, à âî-âòîðûõ ïðîôåññèîíàëüíî çàíèìàëàñü îëèìïèàäàìè, òàê ÷òî îáå çàäà÷è ðåøàëà êëàññå â ñåäüìîì-âîñüìîì :-) (÷òî, òåì íå ìåíåå, íå îçíà÷àåò èõ î÷åâèäíîñòü.)

[(Anonymous)]

Ufff.... A ja-to bylo uzhe podumal chto sovsem uzhe otupel ;)
Vtoraja dejstvitel'no krasivo reshaetsja, esli ja konechno
ne oshibajus' ( na kartinke poluchaetsja chto-to tipa kolodtsa
to the hell ), a vot s pervoj nichego ne pridumyvaetsja poka ...

À ìîæíî

[french-man.livejournal.com]

äî ïîñëåçàâòðà ïîäîæäàòü ñ ðåøåíèÿìè?

Re: À ìîæíî

[avva.livejournal.com]

Çàïðîñòî.

êàê ï÷åëîâåê, ïèøóùèé â ãðàôå "ïðîôåññèÿ" - mathematikerin

[veroniq.livejournal.com]

îòâåòñòâåííî Âàì çàÿâëÿþ - çàäà÷êè íå ÿâëÿþòñÿ òðèâèàëüíûìè, õîòü è ýëåìåíòàðíû ïî òåõíèêå.

Re: êàê ï÷åëîâåê, ïèøóùèé â ãðàôå "ïðîôåññèÿ" - mathematikerin

[avva.livejournal.com]

Âîò è çäîðîâî :)

[lom.livejournal.com]

Ïeðâàÿ çàäà÷à - íe ñàìàÿ ëeãêàÿ. Äeéñòâèòeëüío, ee íàäo ðeøàòü oò ïðoòèâíoão, ío ïo äoðoãe ïðèäeòñÿ äoêàçàòü êàêóþ-íèáóäü ëeììó, ÷òoáû ïeðeôoðìóëèðoâàòü óñëoâèe "íeâoçìoæíoñòè" oáõoæäeíèÿ óçëàìè ñeòêè ìèìo ôèãóðû. ( íàäo ïeðeïèñàòü ýòo êàê íeêèe óñëoâèÿ äëÿ òo÷eê ôèãóðû )... È òàê äàëee. Âïoëíe âoçìoæío, eñòü è êðàñèâoe ðeøeíèe - òèïà ðàñêðàøèâàíèÿ - èìeþùee oòíoøeíèe ê òeoðèè ãðàôoâ.


Âòoðàÿ - ïðoùe, ïoñêoëüêó ëeãêo äoêàçàòü oáðàòíoe ( òo eñòü, óòâeðæäeíèe - íeâeðío ), ïoñòðoèâ êoíòð-ïðèìeð. -:)
ñêàæeì, âçÿòü 9 òo÷eê, 3 ãðóïïû ïo 3 òo÷êè.  êàæäoé ãðóïïe - òo÷êè ðàñïoëoæeíû íà oäíoé ïðÿìoé, èòoão - òðè ñoâeðøeíío ðàçíûe
ïðÿìûe... Òðeòüÿ òo÷êà íe oáÿçàòeëüío ëeæèò ìeæäó äâóõ äàííûõ...
Çàäà÷à ïðèoáðeòàeò ñìûñë, eñëè èçìeíèòü óñëoâèe â ñêoáêàõ: òðeòüÿ òo÷êà äoëæíà áûòü âñeãäà âíeøíeé ê äâóì äàííûì.
Òoãäà... oíà ëeãêo ðeøàeòñÿ ìeòoäoì èíäóêöèè.

[avva.livejournal.com]

Âòoðàÿ - ïðoùe, ïoñêoëüêó ëeãêo äoêàçàòü oáðàòíoe ( òo eñòü, óòâeðæäeíèe - íeâeðío ), ïoñòðoèâ êoíòð-ïðèìeð. -:)
ñêàæeì, âçÿòü 9 òo÷eê, 3 ãðóïïû ïo 3 òo÷êè.  êàæäoé ãðóïïe - òo÷êè ðàñïoëoæeíû íà oäíoé ïðÿìoé, èòoão - òðè ñoâeðøeíío ðàçíûe
ïðÿìûe... Òðeòüÿ òo÷êà íe oáÿçàòeëüío ëeæèò ìeæäó äâóõ äàííûõ...

Íåò, åñëè Âû ïîïðîáóåòå ýòî íàðèñîâàòü, òî óâèäèòå, ÷òî åñòü äâå òî÷êè (èç ðàçíûõ ãðóïï), òàê ÷òî ïðÿìàÿ ìåæäó íèìè íå ïåðåñåêàåò íè îäíîé äðóãîé.

[french-man.livejournal.com]

Ïåðâóþ çàäà÷ó ÿ áû äåëàë òàê. Êàæäóþ òî÷êó íàøåãî ì-âà À ìîæíî ïðèâåñòè ïî ìîäóëþ Z^2 â êâàäðàò [0,1)x[0,1). Ïëîøàäü ïîëó÷àþùåãîñÿ ì-âà À' íå ïðåâîñõîäèò ïëîùàäè À, è À ñîäåðæèò öåëóþ òî÷êó òîãäà è òîëüêî òîãäà , êîãäà À' ñîäåðæèò íà÷àëî êîîðäèíàò. Áîëåå òîãî, ñäâèã À íà íåêèé âåêòîð õ ñîäåðæèò öåëóþ òî÷êó òîãäà è òîëüêî òîãäà, êîãäà òî æå âûïîëíÿåòñÿ äëÿ ñäâèãà ì-âà À' íà õ. Ýòî ñâîäèò çàäà÷ó ê ñëó÷àþ, êîãäà À ñîäåðæèòñÿ â óïîìÿíóòîì êâàäðàòå.

Òåïåðü, ò.ê. ïëîùàäü À ñòðîãî ìåíüøå 1, íàéäåòñÿ òî÷êà õ, ñîäåðæàùàÿñÿ â [0,1)x[0,1), íî íå â À. Ñäâèãàÿ íà -õ, ïîëó÷àåì òðåáóåìîå.

Âòîðàÿ òîæå ïðîùóïûâàåòñÿ, íî ïîïîçæå.

[avva.livejournal.com]

Äà, âñ¸ ïðàâèëüíî. Æäó âòîðîé ;)

à âîò êîãäà

[veroniq.livejournal.com]

ìíå òàêîå ðàññêàçàë âîñìèêëàññíèê, íà÷àâøèé çàíèìàòüñÿ â êðóæêå ñîâñåì íåäàâíî... :-)

[37.livejournal.com]

2) Ïî èíäóêöèè. Äëÿ òðåõ òî÷åê - òðèâèàëüíî. Ïóñòü âåðíî äëÿ n òî÷åê. Äîáàâèì åùå îäíó òàê, ÷òî îíà áóäåò ëåæàòü íà îäíîé ïðÿìîé ñ êàêèìè-òî äâóìÿ. Íî òîãäà îíà ëåæèò íà îäíîé ïðÿìîé ñî âñåìè (íà òîé ñàìîé, êîòîðàÿ ïðîõîäèò ÷åðåç ýòè äâå òî÷êè). Çíà÷èò âåðíî äëÿ ëþáîãî n.

[avva.livejournal.com]

Èíäóêöèÿ íåâåðíà. Íå äîêàçàíî, ÷òî, äîáàâëÿÿ îäíó òî÷êó ê n ñóùåñòâóþùèì, ïîëó÷àåì îáùóþ âîçìîæíóþ êîíôèãóðàöèþ èç n+1 òî÷åê. À äëÿ øàãà èíäóêöèè òðåáóåòñÿ èìåííî ýòî: äîêàçàòü, ÷òî äëÿ ëþáîãî íàáîðà èç n+1 òî÷åê, åñëè îí âûïîëíÿåò óñëîâèå, òî òî÷êè ëåæàò íà îäíîé ïðÿìîé.

Ïðî ïðÿìûå ñäàþñü

[french-man.livejournal.com]

Çàäà÷à, î÷åâèäíî, ÷èñòî àôôèííàÿ. Ìåòðè÷åñêèå ñîîáðàæåíèÿ ðàáîòàòü íå äîëæíû. Âîçìîæíî, ÷òî-òî, ñâÿçàííîå ñ âûïóêëîñòüþ. Åñòü ñìóòíûå àññîöèàöèè ñ Òåîðåìîé Õåëëè, íî ñàìà îíà çàäà÷ó íå ðåøàåò.

Ïîçîð Ôðàíöóçèêó, íî áîëüøå íå ìîãó.

Re: Ïðî ïðÿìûå ñäàþñü

[avva.livejournal.com]

À ÿ êàê ðàç ïèøó îòâåò, ìèíóò ÷åðåç 15 áóäåò. Çàäà÷à èìååò ïðîñòîå ìåòðè÷åñêîå ðåøåíèå. Àôôèííîãî ðåøåíèÿ, ïîäîçðåâàþ, íå ñóùåñòâóåò, õîòÿ ñòðîãî ÿ ýòî íå ïûòàëñÿ äîêàçàòü (íàäî ïîñòðîèòü àôôèííîå ïðîñòðàíñòâî, â ê-ì óòâåðæäåíèå íå âûïîëíÿåòñÿ).

Èçþìèíêà çàäà÷è êàê ðàç ñîñòîèò â ÷ðåçâû÷àéíî àíòè-èíòóèòèâíîé íåîáõîäèìîñòè îáðàòèòüñÿ ê ìåòðèêå.