OT: patecni - N dratu

[Pavel Troller]

>> On 8/20/2012 13:01, Pavel Troller wrote:
>>> Zdravim,
>>>    ano, to je _skoro_ ono (tedy za predpokladu, ze muzeme merit i zkratovat
>>> dole i nahorec, coz v puvodnim zadani nebylo), ALE predpoklada to, ze
>>> alespon jeden drat je barevne odliseny, abychom rozlisili 1 od N.
>>>    A ted prosim jednoznacne reseni, kdyz jsou vsechny vodice _uplne_ stejne
>>> barevne :-).
>
> Na jedno vybehnuti tam/zpet to teda nedavam. Na dve by to mohlo jit, ale 
> moc jsem to nepromyslel, lec drze zvolim cestu spam misto premysleni:
>
> - spojit do skupin po 1, 2, 3, .. N dratech (skupin je rovnez N)
> -- dole omerit, v ktere skupine se kterej drat nachazel
> - spojit znovu do skupin po 1, 2, 3, .. N dratech ale tak, aby nikdy 
> "souskupenci" z minuleho kroku nebyli znovu v teze skupine
> -- to samy.
>
> Dratu je O(N^2) a kazdej dostane identifikaci dvojici cisel (1..N). Zhruba.
>
> Funguje?
> MP

Mohlo by, ale jist si nejsem, nejak mi to uplne nesimuluje vsechny moznosti...
No kdyz uz to jini sem pisou, uvedu "svoje" reseni. Abych byl uplne uprimny,
moje neni, ale asi v 15 letech jsme ho vycetl v jedne chytre knizce. Od te doby
si ho pamatuji, a tak dle prislovi "Co se v mladi naucis"... ho sem dam, kdyz
uz ho nosim v hlave 35 let :-). Pro jistotu uvedu i podminky ulohy, protoze
se lisi od puvodniho zadani.

1) Kabel ma nejmene 3 vodice, obecne N.
2) Vodice nejsou nijak rozliseny (barva, tloustka, oplet...)
3) Lze pouze zkratovat a merit zkrat, ale na obou stranach vodice.

Uloha ma mirne odlisne reseni pro sudy a lichy pocet vodicu. Sudy je ponekud
komplikovanejsi, proto ho uvedu. Lichy necht si kazdy odvodi, je to jen mala
uprava.

Reseni je nasledujici:

Krok 1: Na vychozi strane kabelu (dole) vytvorim smycky na vzdy dvou vodicich
KROME DVOU, ktere ponecham zcela volne. To je finta, kterou jsem tu v zadnem
jinem reseni nevidel. Jelikoz jsou 2, teoreticky by mohly byt taky ve smycce,
ale tim, ze nejsou, narusuji stereotyp a na druhe strane se mam na co
"zasynchronizovat".

Krok 2: Na opacne strane kabelu (nahore) naleznu ony 2 volne vodice. Jeden
oznacim 1, druhy N. Dale vezmu libovolnou smycku, jeden z jejich vodicu
pripojim k vodici 1. Oznacim jej jako 2 a ten druhy 3. Na vodic 3 pripojim dalsi
smycku, oznacim 4,5. Pokracuji dale, az vycerpam vsechny smycky. Posledni ma
cisla N-2, N-1. Vodic N NECHAM OPET VOLNY! Dalsi "synchronizacni finta".

Krok 3: Na vychozi strane kabelu (dole) naleznu vodic, ktery neni nikam
pripojen. Oznacim N. Druhy, puvodne nezapojeny vodic, oznacim 1. Nyni rozpojim
vsechny smycky na tomto konci, ale pamatuji si, jak byly zapojeny. Naleznu
vodic, ktery ma zkrat na 1, je to pochopitelne 2. Ten, se kterym byl ve
smycce, je tedy 3 (viz krok 2). Nyni naleznu vodic, ktery ma zkrat na 3 a je
jasne, ze to je 4. Takto postupuji az do identifikace vsech vodicu.

Reseni pro lichy pocet vodicu si laskavy ctenar jiste odvodi sam :-).

Zdravi Pavel