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

Search the boards