Artlandia spy returns

[smiechowiec]

Artlandia i Zenodia byly w stanie wojny.
Wywiad Artlandii odkryl, ze w pewnym miescie w Zenodii wielce prawdopodobnie produkowana jest smiercionosna bron.
W miescie tym bylo 15 fabryk i wiadomo bylo, ze co najwyzej w trzech z nich moze byc wytwarzana ta bron.
Artlandia wyslala wiec swojego szpiega do Zenodii z zadaniem, by ten zdobyl
i przeslal szyfrem do centrali wywiadu informacje, w ktorych z tych 15 fabryk wytwarza sie te bron.
Zawczasu uzgodniono, ze informacja ta zakodowana bedzie za pomoca jednej liczby, ktora jednoznacznie określi, jakie trzy (lub dwie, lub jedna, lub zadna) z 15 fabryk produkuja te bron i przez to maja byc zbombardowane.

Szyfr zostal tak ustalony, żeby
- był łatwy do zapamiętania,
- każda z mozliwych kombinacji zwracała inny (jednoznaczny) wynik

Dla przykladu przypuscmy, ze do zakodowania sa maksymalnie trzy obiekty,
którym przypisujemy liczby naturalne, a wynikiem jest ich suma przedstawiana binarnie
poprzez zapalenie okien w pokojach, dla których w zapisie binarnym występują jedynki.
Mozna im przydzielic odpowiednio liczby 13, 14, 15.
Teraz kazda suma jednoznacznie okresli, o jaki zbior nam chodzi.
27 wskaze na 13+14, 28 na 13+15, 42 na 13+14+15 itd.

w umowiona noc szpieg ma wynajac wszystkie 12 pokoi na najwyzszym pietrze hotelu.
Nastepnie zapali swiatla w tych pokojach, dla ktorych wypada 1 w zapisie binarnym wyliczonej liczby
np liczba 10 (dziesietnie) = 1010 zostanie zamieniona na 000000001010
Przelatujacy tej nocy satelita wykona zdjecia hotelu i przekaze je kryptologom.
Jaki sposób kodowania dzieki ktoremu mozliwe bylo jednoznaczne zakodowanie
w powyzej opisany sposob trzech z pietnastu fabryk produkujacych bron,
mogli zaproponować szyfrolodzy Artlandii ?


Autor : cardemon

dodam, że ta wersja zagadki jest na tyle łatwa,
że zdarzyło się iz poprawna odpowiedź padał po mniej niż 30 sekundach.


Wersja II trudniejsza,
podaj sposób kodowania gdy hotel ma tylko 10 pokoi, na najwyższym piętrze.

[republican]

Witam Jester
Byles na urlopie w Ortlandii?
Wydaje mi sie ze gdy uzywamy okien to wysatarczy nam 8.
Dwa kore mowia ile jest fabryk (0 do 3)
6 ktore koduja sume jak opisales powyzej

[smiechowiec]

Witam,
na urlopie, tego lata jeszcze nie byłem :)

republican napisał:
> Wydaje mi sie ze gdy uzywamy okien to wysatarczy nam 8.
> Dwa kore mowia ile jest fabryk (0 do 3)
> 6 ktore koduja sume jak opisales powyzej
Nie bardzo rozumiem w jaki sposób.
Z moich wyliczeń wynika, że mamy do czynienia z liczbą możliwych stanów równą
15 nad 0 = 1 +
15 nad 1 = 15 +
15 nad 2 = 15 * 14 / 2 = 105 +
15 nad 3 = 15 * 14 * 13 / ( 2 * 3) = 455
czyli razem 576
co mozna zakodować za pomocą co najmniej 10 bitów

Sposób kodowania na 12 bitach jest bardzo prosty,
a sposób kodowania na 10 bitach jest jego pewną modyfikacją,
której analogiczne rozwiązanie już miało miejsce przy okazji innej zagadki.

Pozdrawiam

[republican]

Masz racje przeskoczyl mi zab w moich trybach
Zgadzam sie z 455
Vide
www.mathwords.com/c/combination_formula.htm--
Dlaczego dodajesz inne kombinacje?
455 mozna wyrazic w 9 bitach (max 511)

Takie te ciarachy tworde, trza by stoc i walic w morde.

[smiechowiec]

> Dlaczego dodajesz inne kombinacje?
> 455 mozna wyrazic w 9 bitach (max 511)
Tak, ale to oddaje jedynie przypadki dokładnie 3 fabryk z 15,
a z treści wynika, że może być ich również 2, 1 lub 0,
więc należy uwzględnić wszystkie możliwości.

Pozdrawiam i życzę dobrych pomysłów

[republican]

IEEE 754 ?

[smiechowiec]

> IEEE 754 ?
Nie, przynajmniej ja nie znam prostej translacji reprezentacji liczby zmiennoprzecinkowej, 12 bitowej, na jeden z 576 przypadków.
Podaj więcej szczegółów, żeby można było przeanalizować Twój pomysł.
Miłego weekendu.

[republican]

Masz racje, floating point w dziesieciu bitach nie pomoze.
Wiec uzywamy tzw "brute force" rozwiazanie.
Numerujemy kazda kombinacje 1 do 576.
Uzywajac 10 okien mamy 10 bitow (0 do 9 od prawej do lewej)
Wyswietlamy poprostu numer kombinacji np
576 1001000000
Umawiamy sie ze 0 fabryk to kombinacja numer 576-
Nasza tabela z kombinacjami choc dluga jest latwa do zapamietania.
Zaczynamy od jedynek 1-15
Pozniej dwojki 16-121
Trojki 122 -itd
Takie te ciarachy tworde, trza by stoc i walic w morde.

[smiechowiec]

republican napisał:
> Numerujemy kazda kombinacje 1 do 576.
> Zaczynamy od jedynek 1-15
> Pozniej dwojki 16-121
> Trojki 122 -itd
Brawo!
Ciekawe rozwiązanie, jednak wymaga nieco obliczeń, przy których można się pomylić, a skutki pomyłki mogłyby być katastrofalne.
Przyjmijmy, że przy dodawaniu/odejmowaniu pomyłki są wystarczająco mało prawdopodobne, natomiast przy mnożeniu/dzieleniu powyżej akceptowalnego progu.
Błąd przy obliczaniu pozycji bitu i ustawienie zer i jedynek na odpowiednim miejscu są mało prawdopodobne.
Czy w takiej sytuacji da się podać na tyle proste rozwiązanie, aby dopuszczalny błąd był do zaakceptowania przez centrale ?

[republican]

Nie ma tu mnozenia i dzielenia ani nawet dodawania..

Metoda jest prosta, powiedzialbym mechaniczna.
Mamy 15 bitow (fabryk) 0 do 14
Jest 576 kombinacji kazda me 15 bitow np:
1 000000000000001
2 000000000000010
576 111000000000000
Lewa kolumna to numer kombinacji
Mamy tabele ze wszystkimi kombinacjami i poprosu porownujemy notatki szpiega z tabela.
Mamy numer ktory wyrazamy w formie dwojkowej i zapalamy swiatla w odpowiednich pokojach.
Dla niebardzo rozgarnietego szpiega nasz tabela moze miec 10 + 15 bitow

nnnnnnnnnn kkkkkkkkkkkkkkk
n-Numer kombinacji w ukladzie dwojkowym,
k- Kombinacja

Wiem ze masz rozwiazanie analityczne, czy jest prostsze?
Takie te ciarachy tworde, trza by stoc i walic w morde.

[smiechowiec]

republican napisał:
> Jest 576 kombinacji kazda me 15 bitow np:
> Mamy tabele ze wszystkimi kombinacjami i poprosu porownujemy notatki szpiega z
> tabela.
Ok, wszystko pięknie.
Ale dla szpiega noszenie z sobą takiej kartki mogłoby być niebezpieczne.
Załóżmy, że ewentualne notatki szpiega nie mogą być większe niż 20 lini po maksymalnie 40 znaków.

> Wiem ze masz rozwiazanie analityczne, czy jest prostsze?
Wydaje mi się że tak, ale przedstawię je na końcu, o ile prędzej nie padnie lepsze.

[republican]

"Czy w takiej sytuacji da się podać na tyle proste rozwiązanie, aby dopuszczalny błąd był do zaakceptowania przez centrale ?"

Czy sugerujesz forward error correcting code?
Np 1 bit error correcting code?
Moja metoda jest:
-niezawodna
_pozwala na uzycie szpiega niskiego poziomu (throw away)
Kilkanascie stron 0 i 1 to moga byc kombinacje Ohio Lottery 3 out of 15 gdy go zlapia.
Pamietaj tez ze kazdy pokoj musi miec co najmniej dwie zarowki (redundancy).
A teraz po zapaleniu swiatel ide spac glodny i spragniony bo po zaplacebnu za 10 pokoi braklo mi forsy.
Obudz mnie rano a Twoim rozwiazaniem prosze
Takie te ciarachy tworde, trza by stoc i walic w morde.

[smiechowiec]

republican napisał:
> Czy sugerujesz forward error correcting code?
> Np 1 bit error correcting code?
Nie, chodzi o prostotę, która pozwoli zapamiętać sposób kodowania bez konieczności wykonywania mnożeń przed ostatecznym ustaleniem postaci liczby

> Moja metoda jest:
> -niezawodna
> _pozwala na uzycie szpiega niskiego poziomu (throw away)
> Kilkanascie stron 0 i 1 to moga byc kombinacje Ohio Lottery 3 out of 15 gdy g
> o zlapia.
Nie traktuj agentów nazbyt lekce.

> Pamietaj tez ze kazdy pokoj musi miec co najmniej dwie zarowki (redundancy).
To nas nie interesuje, w razie awarii lokaj w 5 minut dokona wymiany żarówki.

> Obudz mnie rano a Twoim rozwiazaniem prosze
Czyżbyś dał za wygraną ?

Jeżeli chcesz dać sobie szansę to na razie nie czytaj dalej.

Dla 12 pokoi mamy akurat 3 czwórki bitów (pokoi).
Koncepcja jest taka, że każdej czwórce bitów przypisujemy numer fabryki.
Liczba 0 oznacza brak, od 1 do 15 to numer jeden z fabryk.
Gdy np mamy fabryki o numerach 1, 7, 9 to kodujemy następująco
0001 0111 1001
Jeżeli tylko dwie fabryki np 11 i 15 wtedy w jedną czwórkę wstawiamy 0
0000 1011 1111
jeżeli tylko jedna np 2 wtedy wstawiamy dwa 0
0000 0000 0010
a jeżeli nigdzie to same zera
0000 0000 0000

I co o tym myślisz ?
Czy da się to zapamiętać bez dodatkowych informacji ?

Pozdrawiam i liczę, na podobną propozycję kodowania dla 10 bitów.

[Gość: xxx]

Parę tygodni rozmyślałem nad tym zadaniem. Doszedłem do ciągu Fibonacciego. Pierwsze piętnaście wyrazów tego ciągu.Suma trzech wyrazów zawsze daje jednoznaczną odpowiedź które fabryki trują.Gdy sumę binarnie zapiszemy w kierunku odwrotnym( z lewej do prawej strony) to mamy opisane dwie fabryki trujące. Natomiast gdy w hotelu zapalimy światła w czterech pokojach ( 12,13,14,15) to opiszemy przypadek gdy jedna fabryka truje. Reasumując musimy odczytać dziesięciocyfrową liczbę i zorientować się czy należy ją czytać z lewej czy z prawej strony.

Przykład : (0110111100)-światło zapalone w pokojach 3,4,5,6,8,9 daje sumę 442 . I suma ta nie mieści się w ciągu Fibonacciego. Odczytujemy ją teraz z lewej na prawą stronę i mamy sumę 246=233+13, czyli fabryki odczytani z piętnasto-elementowego ciągu Fibonacciego mają numer 8 i 14.

Przykład :(1101000000)....pierwsze cztery cyfry dają sumę 13. Truje tylko fabryka nr.13

[republican]

Doskonaly pomysl, ale jak dajesz sobie rade z F(1) AND F(2) =1 ?

[Gość: XXX]

Celowo podałem rozwiązanie z tą wadą by teraz podać rozwiązanie bez wady. Otóż jedną jedynkę odrzucamy i jako piętnasty element tego ciągu będzie liczba 610.Mały problemik będziemy mieli ze sumą trzech ostatnich liczb których suma przekracza maksymalną wartość dziesięciocyfrowej binarnej liczby czyli 1023.I tak proponuję szyfrantom by sumom :

610+377+233 przypisać zamiast 1220 liczbę1023--(1111111111)
610+377+144 przypisać zamiast 1131 liczbę1022--(1111111110)
610+377+89 przypisać zamiast 1076 liczbę1021--(1111111101)
610+377+55 przypisać zamiast 1042 liczbę1020--(1111111100)
610+377+34 przypisać zamiast 1021 liczbę1019--(1111111011)

I to jest tylko pięć różnych sum.

Reasumując należy dziesięciocyfrową binarną liczbę odczytać z lewej na prawą i sprawdzić czy suma ta mieści się w piętnastoelementowym ciągu Fibonacciego (bez jednej jedynki) jak nie to odczytać binarną z lewej na prawa.
Szyfranci mają cztery zbiory do rozwiązania :
(1001101000)
(1111111101)
(0010010000)
(0001000000)

Które fabryki trują ?

[republican]

Musisz tez odrzucic F(0) =0
Twoj Fibonnaci bedzie 1,2,3,...................987
Klopoty jeszcze wieksze

[Gość: XXX]

Bronię się......
Szyfranci wiedzą, że czytając z prawej na lewą i wynik jest pozytywny to muszą być trzy fabryki :
(0010010000)=144=0+16+128....czyli fabryki 1 i 10 i 11

Natomiast czytając z lewej na prawą i wynik jest pozytywny to muszą być dwie fabryki :
(0100000000)=2=0+2....czyli fabryki 1 i 2

........i tutaj masz rację. Jedynek nie potrafię zrobić.

Ale przyznać musisz , że jeżeli potrafimy zaszyfrować wszystkie dwójki i trójki to "Alianci" powinni być z nas zadowoleni.

[tomasz.kielpinski]

Może tak:

Pierwszy bit mówi nam czy mamy doczynienia z 3 (1) czy mniejszą liczbą fabryk (0).

Jeśli zero, to drugi bit też ustawiamy na zero i zostają nam dwie pary po 4 bity na zakodowanie dwóch cyfr.

Jeśli jeden, to zostaje 9 bitów na zakodowanie 455 kombinacji 3 fabryk.

Da się. Pytanie tylko, czy szyfrant jest w stanie zapamiętać które światła, przy której kombinacji powinny się palić ;-)

Pozdrawiam,
Kiełpiś

[tomasz.kielpinski]

A teraz doczytałem do końca wątek :-) Muszę jednak pomyśleć o innym rozwiązaniu:-)

[tomasz.kielpinski]

Czy na zdjęciu jest możliwe rozróżnienie okna (z zapalonym światłem) w którym stoi szpieg? :-)

[tomasz.kielpinski]

Jeśli tak, to mam rozwiązanie.

Szpieg pierwsze dziewięć okien grupuje po 3. Może w nich zasygnalizować binarnie 3 liczby od 0 do 7. Komunikuje fabryki w kolejności rosnącej (np. 1,2,3 czyli 001,010,011). Jeśli którakolwiek fabryka ma numer wyższy od 8, od jej liczby odejmuje 8 (np. 1,5,12 - okna 001,101,100).

W dziesiątym oknie natomiast sygnalizuje w której grupie okiem jest pierwsze przekroczenie 8 w numerze fabryki (0 - w pierwszej, 1 - w drugiej, 1+szpieg - w trzeciej)

[tomasz.kielpinski]

A jeśli się nie da, to nie szkodzi. Tę samą informację można uzyskać zamieniając kolejność komunikowania fabryk. I nie będzie do tego w ogóle potrzebne dziesiąte okno :-)

Dla fabryk 1,2,7 / 1,2,15 / 1,10,15 / 8,10,15 w wersji z potrójnym stanem dziesiątego okna szpieg ustawia 9 okien tak samo (001,010,111).

W tej wersji musi tylko zapamiętać że:
- układ 127 oznacza to, co oznacza
- 172 - to podniesienie o 8 fabryki komunikowanej jako 7 (czyli producentami są fabryki 1,2 i 15)
- 217 - podniesienie fabryk 2 i 7 (czyli 1, 10 i 15)
- 271 - podniesienie 3 fabryk (czyli 8,10 i 15)

[republican]

A moze Fibonnaci z:
F(0)=151
F(1) =157
Pozostale F(n) standardowe

[republican]

Fibonnaci odpada bo
F(N)= F(n-1) + F(n-2)
czyli nie wiemy czy to numer czy suma dwoch poprzednich

[republican]

Taki ciag ma przyszlosc

n n^2 +19

1 20
2 23
3 28
4 35
5 44
6 55
7 68
8 83
9 100
10 119
11 140
12 163
13 188
14 215
15 244

[republican]

n^2+19 i n^2+21 niestety maja klopoty
Szukam innych ciagow

Kornel
Uzyj Excel i pomoz nam prosze

[Gość: XXX]

Wymyślenie ciągu którego conajwyżej trzy elementy dają sumę wskazującą jednoznacznie na trujące fabryki jest wezwaniem Ale zaszyfrowanie w inny sposób tej informacji w dziesięciocyfrowej liczbie binarnej jest bardzo proste. Geniusz tkwi w prostocie.

Spróbujcie go znaleźć.....na spacerze z pieskiem mnie olśniło.

[republican]

Miales juz dwa bledne rozwiazania, wiec podaj to trzecie i pogadamy.
Pozdrowienia
R

[tomasz.kielpinski]

Gość portalu: XXX napisał(a):
> Spróbujcie go znaleźć.....na spacerze z pieskiem mnie olśniło.
A patrzyłeś na moją propozycję? MSZ wystarcza 9 bitów.

[Gość: XXX]

Tomek szczerze przyznam, że nie kumam tego co napisałeś tam wyżej.To są mądre rozważania ale ...no nie umiem.Szczególnie stwierdzenie, że wystarczy 9 okien. Z tym się nie zgadzam.Co do republicana to matematyk nie musi być czarno biały, zasadniczy.Trochę luzu. To jest przyjemna zabawa i mamy prawo do błędu.Nawet dwa razy.Chodzi by gonić króliczka ... i dogonić go. Do trzech razy sztuka:

Słuchajcie trzy fabryki to są trzy liczby (4,6 14)=24 albo (13,14,15)=42 a ja wpadłem na pomysł by wykorzystać "odległości' między fabrykami. Sumy te będą o wiele mniejsze i zmieszczą się w 9 bitach. Dziesiąty bit wykorzystam do oznaczenia kierunku

fabryki (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

Trują fabryki 5, 6 i 11 ....opisuję je od lewej do prawej.
Od lewego nawiasu do 5 fabryki są cztery fabryki....od 5 do 6 jest zero....od 6 do 11 są cztery fabryki , od 11 do prawego nawiasu są też cztery fabryki.

Dla mnie oznaczenie(5 6 11) jest teraz (4 0 4 4), ostatnią czwórkę wyrzucam ( bo jest oczywistym wypełnieniem,tzn jak są trzy fabryki w 15-tu to reszta wynosi 12) czyli

( 5 6 11) =(4 0 4) .....czterystacztery to binarnie (110010100)

Przyjemnie zdziwiłem się gdy zauważyłem, że największa liczba (111111111)=511 opisuje ostatni możliwy układ trzech fabryk.

(5 1 1)........(ooooo6o8o10ooooo) tzn. trują fabryki 6 8 i 10.

Inny przykład:
Gdy trują fabryki 7 8 i 10 to zapiszę je od stront prawej do lewej.Od prawego nawiasu do 10 jest 5, od 10 do 8 jest jeden ,od 8 do 7 jest zero, od 7 do lewego nawiasu jest 6........
i zamiast (7 8 10) mam (5 1 0 6). Szóstkę wyrzucamy bo jest oczywistym wypełnieniem ciągu piętnastoelementowego i otrzymujemy (510) który zapiszemy w 9 bitach.

Czyli patrząc na 15-fabryczny ciąg zapisujemy go z tej strony gdzie będzie mniejsza liczba.Umawiamy się, że kierunek z lewej na prawa to (1) a z prawej na lewą (0). Gdy truje jedna fabryka (ooooooooo10ooooo) to mamy zawsze dwie liczby których suma daje 14...binarnie jest to oczywiste do zaszyfrowania. Gdy trują dwie fabryki to mamy trzy liczby "wypełniające" których suma jest zawsze 13. Binarnie też bardzo łatwa do zapisnia.

Z trzema fabrykami wygląda tak :

Zapalono następujące światła (1000110010) szyfranci odczytali z pierwszej cyfry , że będą odliczać z lewej do prawej.Dziewięciocyfrowa binarna daje 50. Gdyby suma cyfr dała 13 albo 14 byśmy kombinowali z dwiema fabrykami albo z jedną. A tak wiemy, że są trzy fabryki trujące.Dopisujemy dlatego zero z przodu (musimy mieć trzy odstępy między fabrykami) i mamy 050 co daje trujące fabryki (1ooooo78ooooooo)... 1 7 i 8.

(1111110100) mówi nam, że odliczamy z lewej na prawą (500). Od lewego nawiasu 5 kroków w prawo fabryka , zero kroku fabryka, zero kroku fabryka.
(ooooo678ooooooo) trują 6 7 i 8.

Przejście z numerologii na odstępy jest sednem tego pomysłu.

[republican]

Bravo!
Myslalem tez o odstepach ale gdzies mi sie cos poplatalo i odrzucilem te metode.
Poza tym nie mam pieska.
PS
Ponoc koncept bomby atomowej przyszedl do glowy Szilardowi gdy przechodzil ulice Strand w Londynie na swietle.

[tomasz.kielpinski]

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

> Tomek szczerze przyznam, że nie kumam tego co napisałeś tam wyżej.To są mądre
> rozważania ale ...no nie umiem.Szczególnie stwierdzenie, że wystarczy 9 okien.
> Z tym się nie zgadzam

Zawsze miałem problemy z przelewaniem myśli na papier (albo na monitor). :-)
Spróbuję jeszcze raz. Chociaż po kolejnej analizie dochodzę do wniosku, że jednak dziesiąty bit będzie potrzebny.

Mam do dyspozycji 3 grupy po 3 okna.
W każdej z grup mogę zakodować binarnie liczbę od zera do siedmiu.
Czyli podać numery dowolnych fabryk a,b,c o numerach z przedziału 1-7 (w tym brak fabryki, kodowany jako zero).
Ale mogę to zrobić na sześć różnych, równoważnych sposobów: 123,132,213,231,312,321
Chcę wykorzystać różne kolejności i dziesiąty bit (oznaczmy go jako X ) jako dodatkową informację pozwalającą na jednoznaczne określenie numerów fabryk w zakresie 0-15.

Szyfrując:
- jeśli numer fabryki jest >7, odejmuję 8 (czyli fabryki 1,10,11 zapisuję jako 1,2,3 ale tak samo zapiszę fabryki 1,2,3 / 1,2,11 / 1,3,10 / 1,10,11 / 2,3,9 / 2,9,11/ 3,9,10 / 9,10,11)
- układam liczby (okna) w odpowiedniej kolejności (najmniejsza=M, średnia=Ś, największa=W):
MŚW - polecenie dla szyfranta: nie dodawaj nigdzie
MWŚ - dodaj 8 do Ś
ŚMW - dodaj 8 do W
ŚWM - dodaj 8 do Ś i W
- dodaję 10 bit:
X=0 - nie dodawaj 8 do M
X=1 - dodaj 8 do M
- wysyłam

Przykłady deszyfrowania:
1,2,3 + 0 => 1,2,3
2,1,3 + 1 =>2,9,11

Wątpliwości mogą budzić sytuacje gdzie dwie liczby są takie same i tym samym nie ma możliwości określenia która jest największa/najmniejsza (np. 1,1,3 czy 0,4,4). W takiej sytuacji proponuję specjalne układ okien, który to wyjaśni.

Dla układu MMW: MMW+0 -> bez zmian, WMM+0 -> tylko W+8, MWM+0 -> M+8, dowolny układ+1=M+8, W+8
Dla układu MWW: MWW+0 -> bez zmian, WWM+0 -> tylko M+8, WMW+0 -> W+8, dowolny układ+1=M+8, W+8

[tomasz.kielpinski]

Pomysł super :-)