Jasnowidz

[Gość: Linear]

Witam

Do stworzenia tej zagadki "zmusił" mnie Kornel. Jest to pierwsza zagadka logiczna, którą wymyśliłem. Raczej nie jest najwyższych lotów. Nie jestem też pewien czy znam najlepsze rozwiązanie.

We Wrocławiu żył sobie pewien jasnowidz. Jego dar był specyficzny. Mógł powiedzieć co stanie się z przedmiotem, którego dotknął. Postanowił wykorzystać swoje umiejętności do gry w totka. Skreślał liczby na kuponie i "sprawdzał" ile ma trafień. Jaka jest najmniejsza ilość kuponów jaką musi zbadać aby być pewnym trafienia szóstki.

założenia:
1) Jasnowidz gra w dużego lotka.
2) Jeden kupon to skreślenie 6 liczb z 49
3) W rozwiązaniu proszę podać algorytm postępowania jasnowidza

Przykładowe rozwiązanie:
Jasnowidz wypełnia kupony na wszystkie możliwe kombinacje i każdy sprawdza. Aby być pewnym wygranej musi skreślić 13 983 816 kuponów.

Jak coś jest niejasne to będę doprecyzowywał założenia.

BR
Linear

[smiechowiec]

Jeśli przez "co stanie się z przedmiotem, którego dotknął" rozumieć
wiedzę ile będzie trafień na danym kuponie wtedy powinno wystarczyć
około 40 kuponów.

I etap - 8 kuponów po 6
1,2,3,4,5,6 (1)
7,8,9,10,11,12 (2)
12,14,15,16,17,18 (3)
...
43,44,45,46,57,48 (8)
czyli 8 kuponów
Pozostała 49 liczba wynika wprost z liczby już uzyskanych trafień,
jeśli było ich 5 wtedy jest ona właściwa,
w przeciwnym przypadku nie.

II etap
jeśli pojawiło się 6 trafień dla jakiejś szóstki koniec zabawy
dla mniejszej liczby trafień w grupach mieszam liczby z 2 kuponów,
aby odkryć, które są poprawne
np w grupach
1,2,3,4,5,6 - 1 trafienie [1]
7,8,9,10,11,12 - 1 trafienie [11]

1,2,3,7,8,9 - 1 trafienie [1] (9)
4,5,6,10,11,12 - 1 trafienie [1] (10)

1,2,3,10,11,12 - 2 trafienia [1,11] (11)
4,5,6,7,8,9 - 0 trafień [] (12)

teraz wiem że w grupie 1,2,3 - jest 1 trafieni1 [1]
i w grupie 10,11,12 - jest 1 trafienie [11]

Dokonując maksymalnie 2 sprawdzeń z liczbami bez trafień jestem w
stanie ustalić jakie to liczby
1,4,5,6,7,8 - 1 trafienie [1] (13)
2,4,5,6,7,8 - 0 trafienie [1] (14)

Analogicznie 2 sprawdzenia dla trójki 10,11,12 czyli (15) i (16)
Wynika z tego maksymalnie 8 kuponów na ustalenie właściwych liczb z
dwu kuponów.

Ostatecznie daje to maksymalnie 8 kuponów + 4 x 8 kuponów = 8 + 32 =
40 kuponów

Oczywiście w każdej rzeczywistej sytuacji można to optymalizować
adaptacyjnie i nie badać grup z zerową liczbą trafień, w związku z
tym najmniej korzystny jest układ gdy w pierwszym z ośmiu kuponach
będziemy mieli po 1 trafieniu.

[Gość: Linear]

Witam

Najbardziej cieszy mnie fakt, że ktoś dobrze zrozumiał moja zagadkę.

smiechowiec napisał:

> Jeśli przez "co stanie się z przedmiotem, którego dotknął" rozumieć
> wiedzę ile będzie trafień na danym kuponie ...

Tak o to właśnie chodziło.

Twoje rozwiązanie jest fajne - inny sposób myślenia niż mój - jednak cały czas
poszukujemy krótszego rozwiązania (przynajmniej moje takie jest)

BR
Linear

[Gość: Krzyś]

czyli, inaczej mówiąc, grał z kimś 49 kolorami w 6-polowego master-minda, bez
podziału na białe i czarne szpilki?

[Gość: alior]

Krzyś, bardzo trafna uwaga.
Warto by jeszcze dodać, że mastermind jest bez powtórzeń.
Właściwie to jest starsza od masterminda gra w numerki albo w słówka.
Znalezienie algorytmu zapewniającego minimum krków jest b. trudne.
a

[tomasz.kielpinski]

Ile jasnowidz może skreślić liczb na każdym kuponie? OIMW mniejsza liczba
skreślonych nie powoduje nieważności kuponu. A większa niż 6 oczywiście
spowoduje że kupon jest nieważny, ale on przecież tylko sprawdza ile ma trafień.

Pozdrawiam,
Kiełpiś

[Gość: Linear]

Witam

Jedno z założeń w treści zagadki to:
- Jeden kupon to skreślenie 6 liczb z 49

Istnieje coś takiego jak gra w dużego lotka ze skreśleniem większej ilości liczb
na kuponie ale nie chciałem tego tutaj uwzględnić. Można stworzyć alternatywną
zagadkę dodając Twoje założenie.

Problem pojawia się jeszcze w innym miejscu. Gdyby jasnowidz na kuponie skreślił
20 liczb to nie był by w stanie określić ile liczb trafił. On potrafi określić
przyszłość przedmiotu, którego dotknie, a przyszłość takiego kuponu to
odrzucenie przez lottomat.

BR
Linear

[tomasz.kielpinski]

Ok. Rozumiem że więcej niż 6 skreślić nie można.

Jeśli dopuszczalne jest skreślenie mniejszej ilości to szóstkę można wygrać w najpóźniej 29 skreśleniu:

- 16 skreśleń w grupach po 3 liczby (1,2,3 - 4,5,6 - ... - 46,47,48)
- 12 kuponów z pojedynczymi liczbami. Po dwie liczby z każdej z grup w których było jakiekolwiek trafienie, w najgorszym możliwym rozkładzie będzie 6 grup po jednym trafieniu.
- 1 skreślenie szóstki

A jeśli jasnowidz musi skreślić dokładnie 6 w każdym sprawdzeniu to.. odpowiedź postaram się znaleźć póżniej ;)

Pozdrawiam,
Kiełpiś

[Gość: Linear]

Witam

Niestety w dużym lotku nie można skreślać mniej niż 6 liczb (to nie jest multilotek)

Na każdym kuponie musi być dokładnie 6 skreśleń.

BR
Linear

[tomasz.kielpinski]

Co właściwie jest nieistotne bo skreślając za każdym razem 6 liczb, szóstkę skreślimy najpóźniej w 27 zakładzie :)

Pozdrawiam,
Kiełpiś

s
p
o
i
l
e
r

s
p
a
c
e

Tak jak śmiechowiec wziąłem 8 grup po 6 liczb, jednak nie mieszałem ich potem ze sobą, tylko do wybranej trójki dołączałem 3 liczby na pewno nie wylosowane.

[Gość: Linear]

mógłbyś rozwinąć swoją myśl. nie bardzo wiem co oznacza "do wybranej trójki
dołączałem 3 liczby na pewno nie wylosowane"

[tomasz.kielpinski]

Mógłbym. Chyba najłatwiej będzie na przykładzie, bo z tłumaczeniem u mnie koślawo ;) Nie wylosowane to znaczy nie wygrywające.

W pierwszej turze sprawdzania (8 kuponów z kolejnymi liczbami: 1-6,7-12,itd lub ogólnie: A,B,C,D,E,F ) będą co najmniej dwa kupony bez trafień. Dowolne 3 z tych 12 liczb biorę do dalszych analiz (oznaczmy je "x"). I po kolei analizuję wszystkie kupony z co najmniej jednym trafieniem, żeby odnaleźć wygrywające liczby. Przykładowo:

ABCDEF ma 1 trafienie. Wypełniam kolejny kupon: ABCxxx. Mogę mieć jedno trafienie (czyli trafienie jest A lub B lub C) lub zero trafień (czyli trafione było D lub E lub F) Jeśli jedno to najgorszym możliwym wariancie wypełniam Axxxxx (0 trafień) a następnie Bxxxxxx (jeśli trafienie to B, jeśli brak to C). Analogicznie jeśli w ABCxxx miałem 0 trafień, to sprawdzam Dxxxxx i Exxxxx (jeśli oczywiście będzie to konieczne). Dla jednego trafienia w ABCDEF potrzebuję maksymalnie dodatkowo 3 zakładów.

Analogicznie dla 2,3 lub 4 trafień w ABCDEF potrzebuję 5 dodatkowych zakładów, dla 5 trafień - 3 zakładów, a dla 6 - żadnego :)

Najgorszy z możliwych rozkładów to po 1 trafieniu w zakładach 3-8 z pierwszej tury sprawdzania. Na znalezienie trafionej liczby potrzebuję maksymalnie 3 dodatkowe zakłady czyli razem 6*3 = 18. Dodaję 8 zakładów z pierwszej tury i jeszcze jeden żeby trafić szóstkę.

Pozdrawiam,
Kiełpiś

[smiechowiec]

> skreślając za każdym razem 6 liczb, szóstkę skreślimy najpóźniej w
27 zakładzie :)

> wziąłem 8 grup po 6 liczb,
>do wybranej trójki dołączałem 3 liczby na pewno nie wylosowane.
"nie wylosowane" czyli takie, które należą do kuponów, na których
było 0 trafień

Licząc na spokojnie, mamy 8 kuponów na początek,
następnie maksymalnie 6 kuponów może być niepuste,
więc je testuję 6 grup maksymalnie po 3 sprawdzenia co daje
8 + 6 x 3 = 26 kuponów


Ale można to chyba jeszcze udoskonalić tworząc coś w rodzaju
kwadratu o wymiarach 6x6.
Wypisujemy w 6 rzędach liczby z 6 niepustych kuponów,
jeżeli jest ich mniej to pozostałe rzędy wypełniamy liczbami z
pustych kuponów.
W II fazie skreślamy na kuponach liczby z pierwszych pięciu kolumn -
wynik z szóstej jest zależny więc już go nie badamy.
Skreślamy w III fazie 5 kuponów z liczba na 5 przekątnych - wynik z
szóstej jest zależny więc już go nie badamy.

Dla uproszczenia pokażę ideę na tablicy 3x3 z trzema skreśleniami
I faza
123 [1]
456 [2]
789 [0]

II faza
147 [1]
258 [1]
wynik 369 da się wywnioskować jako równy 1 w tym przypadku

III faza
149 [2]
267 [1]
wynik 348 da się wywnioskować jako równy 0 w tym przypadku

Ostatecznie mamy 8 + 2 * 5 = 18 kuponów

[Gość: Linear]

No tak, teraz wszystko jasne.

Rozwiązanie wygląda na poprawne. Uzyskany wynik jest lepszy od tego, który sam
wymyśliłem. Brawo.

Teraz sam poszukam lepszego rozwiązania choć trudno będzie.

BR
Linear

[smiechowiec]

Podaj, proszę, Twoje początkowe rozwiązanie.

[Gość: Linear]

Moje początkowe rozwiązanie było tylko trochę lepsze od Twojego.

1 )
Na początku szukam kuponu, który nie posiada żadnego trafienia. Skreślam zatem 6
kuponów. Pusty los znajduje się w skreślonych lub można go złożyć z pozostałych
liczb, których nie badałem.

2)
Zostało mi 49 - 6 liczb, wśród których są wygrywające. Mam zatem 43 liczby, z
których tworzę 21 kuponów. Cztery liczby z pustego kuponu i 2 liczby z
pozostałych 43. Ostatniej 43 liczby nie trzeba sprawdzać.

3)
Mam teraz maksymalnie 6 kuponów wygrywających, z czego wiem wśród których dwóch
liczb jest wygrywająca. Zatem biorę 5 liczb z kuponu pustego i dodaję jedną z
wygrywającej pary. Koniec

Otrzymałem zatem
1) 6 kuponów
2) 21 kuponów
3) 6 kuponów

Rezultat 33 kupony.

BR
Linear

[smiechowiec]

Linear napisał:
> Rezultat 33 kupony.
Bardzo interesujące podejście.

Myślę, że można by było wykorzystać jeszcze wiedzę z I kroku, a
mianowicie, mając 5 lub sześc kuponów, których znamy liczbę trafień
wystarczy utworzyć z nich 2 pary zamiast 3,
przykładowo
wiemy z I kroku, że w kuponie 123456 jest jedno trafienie [1]
wtedy podczas testu 43 kuponów testujemy
12XXXX - [0]
34XXXX - [0]
i wiemy już bez sprawdzania że wynik
45XXXX jest uzupełnieniem poprzednich czyli [1]
to pozwala nam zaoszczędzić przynajmniej 5 sprawdzeń.

>tomasz napisał :
>Ale z uwzględnieniem przekątnych w drugą stronę powinno zadziałać.
Czyli 8+3*5 = 23 próby :)
Zgadzam się.

[tomasz.kielpinski]

Zmartwię Cię. W podanym przez Ciebie przykładzie 3x3 168, 249 i 357 (a więc
przekątne w drugą stronę) dadzą te same składniki (dziewięć jedynek)

Pozdrawiam,
Kiełpiś

[tomasz.kielpinski]

Ale z uwzględnieniem przekątnych w drugą stronę powinno zadziałać. Czyli 8+3*5 =
23 próby :)

Pozdrawiam,
Kiełpiś