12 decembra 2009

Delenie hranatého koláča.


Zábavný článok v časopise New Scientist o krájaní pizze ma inšpiroval k formulovaniu nasledovnej, podobnej, ale omnoho ľahšej úlohy:

Koláč v tvare pravidelného n-uholníka (pričom n je párne) rozkrájame na n trojuholníkových kúskov tým spôsobom, že vedieme rezy od vrcholov koláča k náhodne zvolenému bodu vo vnútri koláča. Kúsky si potom medzi sebou striedavo rozdelia dvaja ľudia. Dostanú obaja rovnakú časť koláča?

Na ilustratívnom obrázku máme znázornenú situáciu pre n=6 a n=8. Jeden človek dostane kúsky vyznačené žltou farbou a druhý človek kúsky vyznačené hnedou farbou.

9 komentárov:

Unknown povedal(a)...

Moj tip je, ze ano. Minimalne pri tom osemuholniku je to zrejme (dva trjuholniky, ktore su "oproti" davaju spolu vzdy rovnaky obsah) - co sa da rozsirit na lubovolny kolac, kde dva trojuholniky proti patria jednemu jedakovi. Pri tom sestuholniku ma nieco lahke hned nenapadlo...

goober povedal(a)...

Žeby pre každé n>1 bol súčet všetkých n-tých komplexných odmocnín z jednotky fakt rovný nule? :-)

Rori povedal(a)...

ano pri n=4k je to dost zrejme ze je to rovnake. Teraz uz len pripad 4k + 2 :)

Radoslav Harman povedal(a)...

Vladimir, Rori: Áno, samozrejme ak je počet vrcholov deliteľný štyrmi, tak je to veľmi jednoduché, pretože súčet plôch dvojíc oproti sebe stojacich trojuholníkov je očividne konštantný. Prípad n=4k+2 je zaujímavejší.

goober: To samozrejme je, ale nechápem ako to súvisí s našou úlohou (ten bod, kde sa zbiehajú rezy, môže byť v zadaní úplne mimo stredu). Ale predchádzajúcimi riešeniami si si získal rešpekt, takže pripúšťam, že si prišiel na nejaké riešenie pomocou komplexných čísiel, len ma nenapadá aké (moje riešenie nepoužíva komplexné čísla). Skús to vysvetliť podrobnejšie.

katka povedal(a)...

Ja som vymyslela nejake riesenie chvilu po precitani tejto ulohy, len som chcela nejaky cas pockat, ci aj inych napadne to iste co mne, ale vidim ze ani velmi nie. Tak teda napisem svoje riesenie:

Obsah trojuholnika je strana krat vyska na nu deleno 2, ked za tu stranu zoberieme stranu pravidelneho n-uholnika, tak tie su vsetky rovnake... Teda staci dokazat, ze sucet vysok ("na strany n-uholnika") v zltych trojuholnikoch je rovnaky ako sucet vysok v hnedych trojuholnikoch.

Ked si predlzim kazdu druhu stranu n-uholnika, dostanem k-uholnik (k=n/2,tiez pravidelny), do ktoreho je ten n-uholnik vpisany. (To mozem spravit aj pri hnedych, aj pri zltych stranach). Lenze "vyska" na nejaku stranu n-uholnika z daneho bodu je zhodna s prislusnou vyskou na stranu toho k-uholnika. Teraz staci dokazat, ze sucet vysok na vsetky strany z lubovolneho bodu vnutri k-uholnika je v pravidelnom k-uholniku konstantny.
Obsah toho k-uholnika sa da vyjadrit ako sucet obsahov trojuholnikov, ktore vzniknu spojenim toho bodu s vrcholmi k-uholnika. Kedze je to pravidelny k-uholnik, mozem vynat dlzku strany lomeno 2 pred zatvorku a v zatvorke zostane uz len ten sucet vysok. A preto musi byt ten sucet rovnaky pre lub. bod z toho k-uholnika (obsah k-uholnika sa nemeni:)).

Radoslav Harman povedal(a)...

katka: Pekný dôkaz (hoci iný ako ten, ktorý napadol mňa).

goober povedal(a)...

Základná úvaha je rovnaká ako v riešení od Katky -- stačí dokázať, že súčet výšok žltých trojuholníkov nezávisí od polohy toho bodu vnútri pravidelného N-uholníka.

Položme ho do komplexnej roviny tak, že stredy jeho strán budú práve komplexné N-té odmocniny z jednotky, stred bude v nule a ten "zbiehací" bod bude číslo P. Teraz zoberme hociktorú N-uholníkovu stranu XY, stred ktorej nech je S, a skúsme vyrátať rozdiel výšok trojuholníkov XY0 a XYP. Ten sa dá vyjadriť ako reálna časť súčinu (P-0)*.S, kde * je komplexné združenie (ono to je vlastne preoblečený skalárny súčin vektorov zodpovedajúcich číslam P a S, pričom |S| = 1).

No a teraz spočítajme všetky takéto rozdiely napríklad pre žlté trojuholníky; dostaneme súčin (P*)(w^0 + w^2 + w^4 + w^6 + ... + w^(N-2)), kde w je primitívna N-tá odmocnina z jednotky. No a keďže ten súčet v zátvorke sa rovná nule (je rovný súčtu všetkých (N/2)-tých odmocnin z jednotky}, celý výraz bude nulový, nezávisle od voľby P. Pre detailistov, plochy/výšky trojuholníkových výsekov berieme so znamienkom, vďaka čomu to platí aj pre body P mimo N-uholníka.

Inak povedané, súčet plôch "žltých" výsekov nezávisí od polohy "zbiehacieho" bodu, a teda žltej a hnedej bude rovnako veľa.

Áno, bol to kanón použitý na vrabce (rovnako sa dali napríklad použiť obyčajné vektory), ale to mám asi z toho, že som predtým niečo s komplexnými číslami riešil, a tak som ich začal vidieť aj tu :-) Katka to vyriešila o dosť krajšie a ako tak rozmýšľam, asi aj všeobecnejšie (asi by som si vedel predstaviť určité zovšeobecnenie do viac rozmerov).

Radoslav Harman povedal(a)...

goober: No, tak to je naozaj kanón na vrabce, ale inak celkom pekný kanón :-) Prezradím teda aj ja moje riešenie, hoci tým môžem napomôcť rešiteľom zamýšlanej úlohy "Delenie hranatého koláča II".

Základom môjho riešenia je uvedomiť si, že ak fixujeme podstavu (čiže dva vrcholy) trojuholníka, tak plocha tohoto trojuholníka je lineárnou funkciou polohy tretieho vrchola (ak sa tým tretím vrcholom pohybujeme len v jednej polrovine určenej fixnou podstavou; samozrejme myslíme lineárnu funkciu dvoch premennných). To ale znamená, že súčet plôch všetkých (povedzme) hnedých trojuholníkov závisí od polohy spoločného vrchola vo vnútri koláča taktiež lineárne (súčet lineárnych funkcií je lineárna funkcia). Lenže ľahko nájdeme tri nekolineárne polohy spoločného vrchola také, že súčet plôch hnedých kúskov je presne polovica plochy celého n-uholníka; napríklad stačí zobrať tri rôzne vrcholy n-uholníka. Nuž ale ak je hodnota linerárnej funkcie rovnaká v troch nekolineárnych bodoch, tak musí byť rovnaká všade...

Páčia sa mi úlohy, ktoré majú viac riešení založených na úplne rozdielnych pohľadoch. Tentokrát sa mi podarilo fomulovať práve takú úlohu...

Rori povedal(a)...

No, uz som asi dlho z tej skoly :) nastastie som tie dokazy pochopil ale ze by som sam na ne prisiel :) Ale aj tak mam dobry pocit, ze tu mozem zas hybat logicko/matematickou castou mozgu :)