Użytkownik "cbnet" <c...@n...pl> napisał w wiadomości
news:gd50h6$sif$1@news2.ipartners.pl...
> 1. W 4-ch pierwszych pytaniach pytam o każdy z 4-ch
> bitów liczby w konotacji binarnej.
>
> 2. W końcówce pytam tylko o wątpliwe liczby.
> Każda odpowiedź twierdząca zdradziłaby liczbę przekłamaną.
> Trzy przeczące świadczą, że nie skłamał ani razu.
>
> Kłamca wybiera wariant w którym nie skłamał.
> To daje wynik 15.

Pozwolę sobie rozwinąć ...
Liczby od 0-15 (symbolicznie oznaczane także jako 0-F)
dają się wszystkie zapisać na 4-ech bitach w kodzie dwójkowym.
0 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 1001
10 - 1010 (A)
11 - 1011 (B)
12 - 1100 (C)
13 - 1101 (D)
14 - 1110 (E)
15 - 1111 (F)

Każda liczba ma unikalny zapis bitowy. Jeśli wiec znamy
po kolei 4 bity to znamy liczbę.
I na tym opieramy 4 pierwsze pytania:
najpierw pytamy o wszystkie liczby nieparzyste, dzięki
temu poznajemy wartość 'ostatniego'
bitu - ponieważ wszystkie liczby nieparzyste mają ten bit
ustawiony na 1 (patrz tabelka wyżej).
W drugim pytaniu pytamy o drugi od końca bit - czyli
(patrzymy do tabeliki) 2,3,6,7,10,11,14,15.
I w dwóch następnych pytaniach o dwa pozostałe bity.

Gdyby nasz przeciwnik nie kłamał, to po tych czterech
pytaniach mamy gotową odpowiedź. 4xTAK oznacza cztery zapalone
bity - 1111 - co odpowiada liczbie 15.
Odpowiedź NNNT oznaczałaby, ustawiając bity od końca 1000
- czyli 8. NNNN to 0.
Ale nasz przeciwnik ma prawo do kłamstwa, więc jeden z bitów
może być inny, niż się nam wydaje.
Czyli jeśli odpowiadzi były TTTT (1111 = 15) to musimy jeszcze wziąć
pod uwagę liczby z jednym bitem wyzerowanym:
TTTN = 0111 = 7
TTNT = 1011 = 11
TNTT = 1101 = 13
NTTT = 1110 = 14

Sytuacja jest trochę podobna, jak poprzednio, tylko mamy
mniej liczb i mniej pytań. No i nie ma jużtakiego bezpośredniego
przełożenia na kod dwójkowy. Możemy znów działac 'metodycznie'
- numerujemy dozwolone liczby i nadajemy kody bitowe. Tym
razem mamy do dyspozycji 3 bity. Co ciekawe - możemy nadawać
te kody bitowe dość dowolnie, nie muszą być po kolei.
A nawet nie mogą. Teraz już nie pozwalamy sobie na niewykryte
kłamstwo - musimy wiedzieć, kiedy jest 15 a kiedy na pewno
coś innego. Uzyskujemy to w ten sposób, że nadajemy liczbie
15 taką kombinację bitów, która nie może zostać pomylona
z żadną inną przez zafałszowanie tylko jednego bitu. Inaczej,
jeśli nas oszuka, nie będziemy wiedzieli, czy zrobił to teraz,
czy wcześniej. Przykładowe najprostsze przypisania:

7 dajemy kod bitowy = 000
11 dajemy kod bitowy = 001
13 dajemy kod bitowy = 010
14 dajemy kod bitowy = 100
15 dajemy kod bitowy = 111

Teraz w kolejnych pytaniach, jak poprzednio, pytamy o kolejne bity:
ostatni => (11,15)
środkowy => (13,15)
pierwszy => (14,15)
I pytamy:

5. Is the number in: 11, 15?
Yes
6. Is the number in: 13, 15?
Yes
7. Is the number in: 14, 15?
No


Odpowiedź YYN = 011 = ??? - i proszę, nie mamy takiej kombinacji
w naszej nowej tabelce ! Oznacza to, że nas właśnie oszukał !
To oznacza, że nie mógł nas oszukać w pierwszych 4 pytaniach,
więc wynik = 15 ;)

Your guess was 15.
Correctamundo!

A jak spojrzymy w liczby, to widać, że nas musiał oszukać w ostatnich
trzech, bo jeśli 15, to skłamał w 7. pytaniu, a jak nie 15 to skłamał
w 5. lub 6. ;)
Ale mógłby np. odpowiedzieć NYN, czyli 010. Oznaczałoby to, że nas teraz
nie oszukał, a liczbą jest, zgodnie z tabelką - 13. I oszustwo byłoby
w pytaniu 2.

Można też sprawdzić, że jeśli nie skonstruujemy prawidłowo
tabelki i np. damy liczbie 15 kod 011 - to nie będziemy
w stanie stwierdzić, gdzie kłamie i będziemy się rozbijać
między możliwościami 15, 11 i 13 - jako podobnymi (tu sie
kłania 'za mała odległość Hamminga').

********************************

Ty, cebe, w swoich trzech ostatnich pytaniach, 'niejawnie' przyjąłeś
inny kształt tabelki do ostatnich trzech zapytań. A wyglada ona tak:
7 dajemy kod bitowy = 101
11 dajemy kod bitowy = 011
13 dajemy kod bitowy = 111
14 dajemy kod bitowy = 110
15 dajemy kod bitowy = 000

Ten kod także spełnia zasadę odpowiedniej odległości Hamminga
liczby 15 od pozostałych - nie da się przez jeden fałsz zrobić
z niej innej dozwolonej kombinacji z tabelki. No i ta tabelka
bezpośrednio uzasadnia zapytania:
> 5. Is the number in: 7, 11, 13?
> No
> 6. Is the number in: 11, 13, 14?
> No
> 7. Is the number in: 7, 13, 14?
> No
Odpowiedź NNN oznacza 000 czyli liczba 15 - nie skłamał
ani razu, inaczej niż u mnie.


****************************************************
***********

Co ciekawe, sztywne przywiązanie kodów bitowych do liczb
(pierwsze 4 pytania) nie jest konieczne(tak jak w pozostałych
3) - możemy dowolnie poprzypisywać 4 bitowe ciągi do liczb,
byleby były unikalne. Zdaje się, że vonBraun zaproponował
np. 'przesunięcie'. A inny ciekawy przykład - jak 'zmusić'
kłamcę, żeby zgadywał dokładnie to, co sobie zażyczymy:
zamieniamy np maski bitowe między liczbami 15 a 1. Skutkuje to tym,
że w naszych pytaniach wszędzie, gdzie mieliśmy 15 wstawiamy 1
i na odwrót. Modyfukując Twój przykład, cebe, możemy naszego
kłamliwego przyjaciela zmusić do tego by 'wylosował'
numer 1 - i przypuszczam, że podobnie zadziała dla każdej innej liczby,
aczkolwiek nie jest to przesądzone - zależy od algorytmu kłamcy. ;):

1.Is the number in: 1, 3, 5, 7, 9, 11, 13, 15?
Yes
2.Is the number in: 1, 2, 3, 6, 7, 10, 11, 14?
Yes
3.Is the number in: 1, 4, 5, 6, 7, 12, 13, 14?
Yes
4.Is the number in: 1, 8, 9, 10, 11, 12, 13, 14?
Yes
5.Is the number in: 7, 11, 13?
No
6.Is the number in: 11, 13, 14?
No
7.Is the number in: 7, 13, 14?
No
Your guess was 1.
Correctamundo!

****************************************************
***********

Padło pytanie o liczbę rozwiązań ...
Zapewne bardzo dużo ...
Metoda stosowana przez nas 4 pytania o bity + 3 rozwikłujące
nie jest chyba najprostszym opisem rozwiązanai. Skumałem
jak np. przełożyć na to zadanie kod Hamminga. Zamiast robić 4
+ 3 od razu postarajmy się do naszych liczb 0-15 przypisać
7-mio (nie cztero) bitowe ciągi, ale tak, by wszystkie między sobą
(nie tylko do 15) miały odległości Hamminga >2. Tabelkę konstruuję
zgodnie ze wskazówkami
http://pl.wikipedia.org/wiki/Kod_Hamminga#G.C5.82.C3
.B3wny_algorytm
Bity pierwszy, drugi i czwarty są dodane(wyliczone), pozostałe wyglądają
tak samo, jak w tabelce na początku. Cała tabelka, jeśłi się nie kopnąłem,
wygląda jak ponizej. Czy są spełnione wszystkie odległości - nie wiem
- wierzę na słowo ... Wygląda nie najgorzej ...

00 - 0000000
01 - 1101001 (to 0001 z wplecionymi trzema bitami parzystości)
02 - 0101010
03 - 1000011
04 - 1001100
05 - 0100101
06 - 1100110
07 - 0001111
08 - 1110000
09 - 0011001
10 - 1011010 (A)
11 - 0110011 (B)
12 - 0111100 (C)
13 - 1010101 (D)
14 - 0010110 (E)
15 - 1111111 (F)

Jako, że nie ma znaczenia kolejność zadawanych pytań, będziemy
dla ułatwienia jechać z zapytaniami od lewej do prawej. Pytamy więc
o pierwszy z lewej bit (patrzymy w tabelce, kto ma go ustawionego):
1. 1,3,4,6,8,10,13,15
i kolejne:
2. 1,2,5,6,8,11,12,15
3. 8,9,10,11,12,13,14,15 (bit danych, mamy pytanie identyczne, jak w
poprzedniej metodzie)
4. 1,2,4,7,9,10,12,15
5. 4,5,6,7,12,13,14,15 (bit danych, ...)
6. 2,3,6,7,10,11,14,15 (bit danych, ...)
7. 1,3,5,7,9,11,13,15 (bit danych, ...)

No to wpuszczam i dostaję odpowiedzi:
YYYYYYN, czyli 1111110
Sprawdzamy w tabelce ... Takiej kombinacji nie ma,
ale jest tylko jedna zbliżona 'o jeden bit' - 15 ;)

Correctamundo!
;)

Gdyby odpowiedzi były inne i mielibyśmy problem
z odnalezieniem 'podobnej' liczby, to korzystamy z własności
który powinna mieć tabelka skonstruowama wg kodu Hamminga - bity
parzystości powinny wskazać miejsce przekłamania. U nas bity parzystości
w odpowiedzi to 111, czyli po przeliczeniu tego na liczbą dziesiętną mamy 7.
Zgadza się ;) Właśnie na tej pozycji mamy zafałszowaną odpowiedź ;)
Nie wiem, co by było, gdyby zafałszował któryś z bitów parzystości
- wtedy po korekcie skazywanego miejsca dalej byłoby pewnie coś nie tak
i odpowiedź można by wziąć bezpośrednio z bitów danych jako niezafałszowaną.

Czary mary ... ;)