31 januára 2013

Ťažisko

Úlohou je do n ekvidištantných pozícií na kružnici vo vhodnom poradí rozmiestniť guľôčky s hmotnosťami 1, 2, 3, ..., n gramov a to tak, aby ťažisko sústavy týchto guľôčok bolo presne v strede kružnice. Nájdite čo najviac hodnôt n, pre ktoré sa táto úloha dá vyriešiť.


Na ilustračnom obrázku je rozmiestnených 5 guľôčok s hmotnosťami 1,3,4,2 a 5 gramov (v tomto poradí), ktorých ťažisko, označené červenou bodkou, je však máličko vychýlené voči stredu kružnice.

8 komentárov:

goober povedal(a)...

Pekná úloha! Zatiaľ s ňou viem pohnúť pre dvojnásobky nepárnych čísel; kľúč k odpovedi sa ukrýva vo výraze (0,1)+4 :-)

goober povedal(a)...

Tak, a už ma z párnych čísel trápia len mocniny dvojky :-)

Radoslav Harman povedal(a)...

Vidím, že Ťa tá úloha zaujala; až mám obavy o Tvoju dnešnú výkonnosť v práci :) Musím sa priznať, že ja som sa tak ďaleko ako Ty nedostal (aj keď je zasa pravda, že som si nemohol dovoliť premýšľať nad ňou viac ako pár desiatok minút) a ani som nečakal, že to niekto tak ďaleko dotiahne.

Mňa tá úloha napadla keď som sa hral s algoritmom simulovaného žíhania na riešenie jednej úlohy, ktorú som zadal na projekt k môjmu predmetu "stochastické optimalizačné metódy" (úloha "Turbína"). Neskôr som toto zadanie používal ako testovací príklad počas skúšky.

goober povedal(a)...

Najprv som sa normálne zľakol, že takéto príklady sa teraz riešievajú na skúškach a ja sa s tým hrám už pár večerov a neviem sa pohnúť ďalej :-)

Zatiaľ viem, že pre párne N sa úloha dá vyriešiť práve vtedy, keď N nie je mocnina dvojky. Pre nepárne N zase viem, že prvočísla nefungujú... ale zložené sú tvrdši oriešok.

Radoslav Harman povedal(a)...

Na skúške mali študenti už pripravený program na simulované žíhanie (urobili si ho sami doma), ktorý hľadá takú permutáciu zadaných hmotností do ekvidištantných pozícií na obvode kruhu, aby bolo ťažisko týchto hmotností čo najbližšie k stredu kruhu.

Ja som po nich samozrejme nechcel žiadne všeobecné tvrdenia, len som im zadal vypočítať optimálne rozloženie konkrétnych hmotností. Ako testovacia množina hmotností je najlepšia taká, pre ktorú sa dá optimálny výsledok ľahko zapamätať, a pritom je jeho optimalita nespochybniteľná. Takou je (povedzme) množina hmotností 1,2,...,12. :)

Ja som tento príklad zadal na blog skôr so zámerom, aby sa ľudia trochu pohrali s konkrétnymi malými číslami n, čiže napríklad aby si vzali papier a ceruzku a snažili sa okolo kruhu rozmiestniť čísla 1,...,6 tak, aby bolo ťažisko v strede. To je jednoduchý zábavný hlavolam.

Vyriešiť túto úlohu vo všeobecnosti (tak ako sa o to snažíš Ty) je určite ťažké a už aj to čo si ukázal sa zdá byť veľmi dobrý výkon.

Anonymný povedal(a)...

ťažisko.
problém je samozrejme riešiteľný pre každé n.
to ovšem neznamená, že exaktné riešenie viem poskytnúť.
dokázať by som to (riešiteľnosť) ovšem vedel.
ako ty stojíš s riešením?

Anonymný povedal(a)...

aha, nevšimol som si slovo "ekvidištantných".
tak to je už o inom.
jednoducho som blbec.

Radoslav Harman povedal(a)...

Anonymný: Náhodou, pokiaľ by sme nemali podmienku "ekvidištantnosti", tak dostaneme úlohu, ktorá je tiež celkom pekná, najmä ak by nemohlo byť viac guľôčok na jednom mieste.

Ďakujem za námet, ak sa mi niekedy uvoľní čas, možno to spracujem do príspevku.