Posted By: pluma (Pluma from Brno) on 'CZriddles' Title: Re: snakova vyzva:-) Date: Tue Dec 1 17:55:19 1998 Hodne davno se tu objevila nize uvedena hadanka: > 3) Zlaty hreb! Vypada to lehce, ale Lumiku, uskvaris se na tom:-))))): > Velbloudi problem (pochazi z MFF, nedopidil jsem se vyreseni:-( ) > Je n velbloudu v karavane. Protoze jsou uz z chuze celi zblbli a zacinaji > podlehat "ponorkove nemoci", bylo zjisteno, ze dojit se da pouze pokud budou > kazdy den menit poradi, a to tak, aby se zadny z nich nedival na nikoho z > predeslych. Tj. stal-li nekdy velbloud c. 2 TESNE za velbloudem c.7, uz > dalsi > dny tesne za nim stat proste nesmi. Prvni velbloud se nediva na nikoho, a > druhy az posledni vidi vzdy jen toho pred sebou, ostatni mu nevadi. Kolik > nejdele dni muze jit takova karavana? (tj. urcit fci f:N->N). Pro nazornost: > 1 > velbloud muze jit libovolne dlouho (jasne, neni to n z N:-)), dva velbloudi > mohou jit pouze dva dny (1, 2 a druhy den 2, 1), kupodivu tri > velbloudi...doplnte si sami... a jeste vetsi udiv pro ctyri velbloudy:-)...K > > petce jsem uz nedosel, nepovedlo se mi to ani naprogramovat:-( Nasel jsem priklad toho, ze karavana se sudym poctem velbloudu muze jit n dni a s licym poctem n-1 dni. Cimz je problem pro suda cisla vyresen (je zrejme ze karavana nemuze jit dele jak n dni) a pro licha cisla je potreba ukazat, jestli takovato karavana muze nebo nemuze jit n dni (coz se mi nepodarilo, ale osobne si myslim, ze ne). Postup pro n=2*v: Vezmeme si uplny graf o n vrcholech (pro ty kdo nevedi co to je, necht si predstavi n bodu rovnomerne umistenych na kruznici, kde je kazdy s kazdym spojen useckou). Vrcholy predstavuji velbloudy. Pokud se mi podari rozdelit hrany grafu (tj. usecky) do v skupin po (n-1) useckach, tak ze kazda skupina usecek tvori cestu po vsech vrcholech (tj. dlouhou lomenou caru, ktera projde vsech n vrcholu, ale v zadnem se nezastavi dvakrat), tak mi kazda cesta definuje dve mozna poradi karavany - pokud po ni jdu jednim a druhym smerem. Toto rozdeleni vypada nsledovne: Ocislujme vrcholy 1,2,...,n Prvni cesta je: ... - (n-1) - (v+2) - n - (v+1) - 1 - v - 2 - (v-1) - 3 - (v-2) - ... Pokud si to nakreslime na onu kruznici (vrcholy ocislovany dokola), tak vam vznikne takova stredove soumerna zubatice. Dalsi skupiny dostaneme tak, ze cisla vrcholu zvysujeme o 1, kde n+1-->1 (v kruznici se jedna o pootoceni cele cesty o udel 2*Pi/n). Priklad: n=6 Prvni cesta: 5-6-4-1-3-2 Dalsi dve cesty: 6-1-5-2-4-3 a 1-2-6-3-5-4 Z toho vzniknou karavany: 5-6-4-1-3-2, 2-3-1-4-5, 6-1-5-2-4-3, 3-4-2-5-1-6, 1-2-6-3-5-4, 4-5-3-6-2-1 Posup pro n=2*v+1: Tentyz, poze tech cest vytvorime v a nektere hrany vubec nevyuzijeme. Zubatice vznikne trochu jina - bude osove soumerna. Pochopitelne zbyva dokazat, ze pro liche n, ta karavana nemuze jit n dni. Ale to se mi nepodarilo dokazat. pluma