wiązka drutów

[Gość: grzesiek]

To zagadka z Internetu z troszkę zmienioną fabułą. Na razie nie powiem skąd.

W starym domu od piwnicy do strychu biegnie wiązka kabli w której jest N
drutów. Druty są na obu końcach odizolowane tak, że można je łączyć z jednej
strony i badać zwarcie z drugiej strony. Dostałem zadanie przyporządkowania
końcówek wystających w piwnicy z tymi wystającymi na strychu.

Mam do dyspozycji tylko przyrząd do wykrywania zwarcia. Nie mam żadnych
rezystorów ani diód ani baterii.

Jak to zrobić żeby jak najmniej nachodzić się miedzy piwnicą a strychem?

[kornel-1]

Gość portalu: grzesiek napisał(a):

> W starym domu od piwnicy do strychu biegnie wiązka kabli w której jest N
> drutów.

Jeśli dobrze rozumiem, przyrząd podłączony do wybranych DWÓCH drutów wskaże, czy po drugiej stronie są one połączone (zwarcie) czy nie (brak zwarcia).

Dla N=2 nie warto biegać po piętrach, problem nierozstrzygalny.
Gdy N=3, mamy (1,2,3) w piwnicy i (A,B,C) na strychu. Łączymy (12) i szukamy zwarcia, powiedzmy jest (AB), wówczas 3=C'; zwieramy (AC), rozłączamy (12) wówczas zwarcie jest (12) lub (13), czyli mamy 1=A, 2=B lub 1=B, 2=A. Biegamy 2 razy: w górę i w dół.
Dla N=4, 5... trzeba opracować podobne schematy, które redukują się do przypadków N=3.

Dla dużego N zaproponowałbym połączenie drutów w wiązki po 2, 3, 4, 5, .... Po przejściu na strych łatwo byłoby zidentyfikować grupy połączonych drutów: (AB), (CDE), (FGHI), (JKLMN)....
W obrębie wiązek 2-, 3-, 4-, 5-elementowych posługujemy się schematami opracowanymi wcześniej dla N = 3, 4, 5.... Po ustaleniu np 3=C, wracamy do wiązki dwuelementowej i przepinamy złącze.

To tylko ogólny zarys rozwiązania.

Alternatywa, nad którą myślę jest łączenie drutów w pary (12) (34) (56)...

Kornel

[Gość: grzesiek]

Ciepło, ciepło....

[kornel-1]

Będę rozwijał pomysł z tworzeniem podwiązek ;-)

Dla N=15 tworzę 5 podwiązek spiętych razem:
Piwnica: {1}, {2,3}, {4,5,6}, {7,8,9,10}, {11,12,13,14,15}

I bieg (na strych)
Po sprawdzeniu połączeń mam pogrupowane
Strych: {A}, {B,C}, {D,E,F}, {G,H,I,J}, {K,L,M,N,O}
Zatem 1=A
Grupuję na nowo:
{B}, {A,C}, {D}, {E,F}, {G}, {H,I}, {J}, {K}, {L,M},{N,O}

II bieg (do piwnicy)
Po rozłączeniu identyfikuję podwiązki:
{2}, {1,3}, {4}, {5,6}, {7}, {8,9}, {10}, {11}, {12,13}, {14,15}
2=B, 3=C, 4=D, 11=K
Teraz splatam je tak:
{1,5}, {6}, {2,7}, {3,8}, {9}, {10}, {11,12}, {13}, {4,14}, {15}

III bieg (na strych)
5=E, 6=F, 7=G, 8=H, 9=I, 10=J, 12=L, 13=M, 14=N, 15=O

Uff...

Jeśli się nie pomyliłem, wystarczy się przejść trzy razy po schodach.

Teraz wypadałoby zrobić rozpiską dla 30 drutów...

Kornel

[Gość: grzesiek]

Można szybciej i trochę prościej. Ale tylko trochę.

[kornel-1]

Gość portalu: grzesiek napisał(a):

> Można szybciej i trochę prościej. Ale tylko trochę.

No dobrze.
Czy w Twoim rozwiązaniu dla N=15 wystarczy chodzić po schodach raz lub dwa razy?

k.

[kornel-1]

Gość portalu: grzesiek napisał(a):

> Można szybciej i trochę prościej. Ale tylko trochę.

Wracam do pomysłu z łączeniem drutów parami (dla N=6)
W piwnicy łączę parami (1,2), (3,4), (5,6) i pędzę na strych (I bieg).
Na strychu stwierdzam trzy zwarcia, powiedzmy:
(A,C), (B,D), (E,F)
Wiem, że dla pary (A,C)
A = 1 i 2 = C lub
A = 2 i 1 = C lub
A = 3 i 4 = C lub
A = 4 i 3 = C lub
A = 5 i 6 = C lub
A = 6 i 5 = C
oraz jednocześnie zachodzi dla pary (B,D)
B = 1 i 2 = D lub
B = 2 i 1 = D lub
B = 3 i 4 = D lub
B = 4 i 3 = D lub
B = 5 i 6 = D lub
B = 6 i 5 = D
oraz jednocześnie zachodzi dla pary (E,F)
E = 1 i 2 = F lub
E = 2 i 1 = F lub
E = 3 i 4 = F lub
E = 4 i 3 = F lub
E = 5 i 6 = F lub
E = 6 i 5 = F.
Łączę teraz druty na strychu tak by wymienione pary (A,C), (B,D), (E,F) się nie powtórzyły, np:
(A,B), (C,E), (D,F) i pędzę do piwnicy (II bieg)
W piwnicy rozłączam dotychczasowe połączenia i stwierdzam trzy zwarcia, np.
(1,6), (2,4), (3,5)
Stąd wiem, że:
1 = A i B = 6 lub
1 = B i A = 6 lub
1 = C i E = 6 lub
1 = E i C = 6 lub
1 = D i F = 6 lub
1 = F i D = 6
oraz jednocześnie :
2 = A i B = 4 lub
2 = B i A = 4 lub
2 = C i E = 4 lub
2 = E i C = 4 lub
2 = D i F = 4 lub
2 = F i D = 4
oraz jednocześnie :
3 = A i B = 5 lub
3 = B i A = 5 lub
3 = C i E = 5 lub
3 = E i C = 5 lub
3 = D i F = 5 lub
3 = F i D = 5

Teraz szukam niesprzecznych rozwiązań uzyskanymi po I i II biegu:
Np. gdy A = 1 i 2 = C to dojdziemy do B = 5 i 3 = A <=tu sprzeczność!
Niesprzeczne rozwiązanie, gdy:
1 = B
2 = D
3 = E
4 = F
5 = C
6 = A
Zatem wystarczą dwa kursy!
Trzeba by było udowodnić, że schemat działa dla N>7. Dla N=7 Jeden drut będzie bez zwarcia - łatwy do identyfikacji i eliminacji.

Kornel

[Gość: grzesiek]

To już duży postęp. Podpowiem, że dwa wnioski są poprawne: wystarczą dwa spacery, i trzeba łączyć parami. Jednak Twój sposób ma niedogodności - jest skomplikowany i co ważniejsze nie jest jasne, czy znalezione niesprzeczne rozwiązanie jest słuszne. Nie można wykluczyć, że istnieje wiele niesprzecznych rozwiązań, zwłaszcza dla większych N.

[kornel-1]

Gość portalu: grzesiek napisał(a):
> nie jest jasne, czy znalezione niesprzeczne rozwiązanie jest słuszne.

Dlaczego?

k.

[Gość: grzesiek]

Podaj taki sposób znalezienia niesprzecznego rozwiązania żeby było jasne, że jest tylko to jedno. Z samego stwierdzenia, że znajdujemy niesprzeczne rozwiązanie jeszcze nie wynika jego unikalność.

[kornel-1]

Gość portalu: grzesiek napisał(a):
> Podaj taki sposób znalezienia niesprzecznego rozwiązania żeby było jasne, że je
> st tylko to jedno. Z samego stwierdzenia, że znajdujemy niesprzeczne rozwiązan
> ie jeszcze nie wynika jego unikalność.

Ale w mojej metodzie rozwiązania problemu dla N=6 jest tylko jedno rozwiązanie (rozwiązanie, czyli jedyna możliwość, że nie dochodzi się do sprzeczności)

k.

[Gość: grzesiek]

Zapewne tak. O ile rozumiem Twoją metodę, trzeba przeanalizować całe drzewo możliwości, np. zaczynając od A=1 i C=2, dalej B=3 i D=4, itd. Jak nie wyjdzie to się cofnąć i spróbować B=5 i D=6, itd. Będzie dobrze jeśli tylko jedna taka ścieżka zakończy się niesprzecznością.
Wierzę Ci, że dla N=6 tak jest, ale co dla większych N. Być może można udowodnić unikalność rozwiązania dla każdego N, ale nie warto. Istnieje metoda, która w sposób jasny prowadzi do jedynego możliwego rozwiązania.

[kornel-1]

Zadanie polegało na minimalizacji chodzenia po schodach.
Dla N=6 lub 7 znajduję rozw. z s = 2 przejściami po schodach
Nie sądzę, by się dało znaleźć s = 1.
W dalszym ciągu, (acz poza konkursem) jest minimalizacja liczby pomiarów zwarcia (p) a następnie minimalizacja liczby wykonanych złączeń/rozłączeń (z).
Dla N=6 mamy p maksymalnie 16, średnio p = 8; z = 12.
Po zminimalizowaniu p i z, możemy optymalizować proces wyszukiwania połączeń na podstawie uzyskanych danych pomiarowych. Może to za nas zrobić komputer.

Poczekam na rozwiązanie z mniejszą liczbą p i z.

Kornel

[xxxdwa]

Zadanie bardzo fajne mądre i .......proste .

Idziemy do piwnicy i ołówkiem na kartce wypisujemy ciąg arytmetyczny....

1+2+3+4+5+6+7+.......+17+18+19+........25=325

a końcówek jest 307....brakuje do 325 koncówek 18

18=11+7

na karteczce gumką ścieramy liczby 11 i 7

w piwnicy tworzymy z koncówek pęczki z ciagu arytmetycznego i w kazdym z pęczków końcówkom nadajemy numer tego pęczka. Oczywiscie pęczku nr 7 i nr 11 nie ma......biegniemy na strych.

Odtwarzamy pęczki i nadajemy im te same numery jak piwnicy.

Teraz wciagnij powietrze i pomysl !.......mamy 23 pęczki bo ( nr 11 i 7 nie ma).
Wybieramy z kazdego pęczku po jednym kabelku i w nawiasiku na kabelku wpisujemy numer pęczka i razem je skręcamy......mamy teraz na jakimś tam kabelku np 8(25) albo inny 21(25).

Mamy teraz 22 pęczki.......znowu wybieramy po jednym kabelku z kazdego pęczka i nadajemy mu numer 24 w nawiasiku i skręcamy.......3(24) 10(24) 19(24)

Mamy teraz 21 pęczków....wybieramy z każdego pęczka po jednym kabelku i nadajemy mu numer 23 i skręcamy.........6(23) 8(23) 9(23) itd

Mamy teraz 20 pęczków...............................

Na strychu mamy wszystkie kabelki opisane ......no to zbiegamy do piwnicy.

Rozkręcamy wszystkie kabelki i porzadkujemy je wedlug nowych (strychowych) wiązek nadając jednoczesnie na kabelku numer wiazki......i mamy 12(13) 15(20) 9(16).

Reasumujac.....dwa ciagi arytmetyczne (piwnica i strych) przeplatając pozwala rozwikłac tysiac kabelków w kablu przeprowadzonym przez Wislę na drugi brzeg i to za jednym razem.

[Gość: grzesiek]

W pierwszej chwili bardzo mi się to rozwiązanie spodobało, zwłaszcza że jest bardzo różne od oficjalnego. Jednak zacząłem mieć wątpliwości... Jak to będzie dla pięciu drutów?

[xxxdwa]

Rzeczywiscie......tym sposobem daje się rozwiazac tylko sumy kabelków z ciagu arytmetycznego czyli 1 3 6 10 15 21 28 37 47.......itd.

Wobec tego mam inna propozycję.......
Jestem piwnicy i pierwszy kabelek oznaczam numerem jeden i nie skręcam z żadnym kabelkiem. Resztë kabelków skręcam parami.......musi ich być parzysta ilość.
Biegnę na strych ....pary odnajduję i je ze sobą laczę jedniczesnie nadajac kabelkom kolejne numery 2 3 4 5......itd. Oczywistym jest, ze nr 2 połaczylem z nr 1a nr 3 z nr 4.....itd.Otrzymalem na rysunku jakoby zęby piły ręcznej żagi.Wierzcholki zęba na strychu a dół zęba w piwnicy. Zbiegam do piwnicy ....wiem który jest kabelek z jedynką i przyrzadem....... od jedynki odliczam każdy następny kabelek.....można to zrobic......nadajac mu kolejna liczbę. CND.

Ale jak to zrobić kiedy w piwnicy liczba wszystkich kabelków jest parzysta ??????

[Gość: grzesiek]

BRAWO XXXDWA! Tak samo jest w oryginalnym rozwiązaniu. Dla parzystej liczby jest tylko trochę bardziej skomplikowane.

[xxxdwa]

Dla parzystej ilosci kabelków należałoby w piwnicy dwa kabelki oznaczyc X a resztę parami skręcić. Pobiec ja strych i jednemu z iksów nadać nr 1 a drugi z nr 2 połączyć z ....V V V V V V numerujac je. W piwnicy 1 znajdziemy 2 znajdujemy i kolejne 3 4 5 6.....n tez znajdziemy.

[Gość: grzesiek]

DOBRZE! To już kończy zagadkę. Jej autorem jest Ken Duisenberg i oryginał można znaleźć tu
ken.duisenberg.com/potw/archive/arch07/071022.html