[a.....r]

#zagadkilogiczne

Ty i znajomy macie podaną listę N różnych liczb całkowitych.

Sześć liczb z tych N jest wybranych losowo i umieszczonych na sześciokątnej kostce. Ta kostka znajduje się dokładnie w środku pokoju, z jedną ze ścianek skierowanych do jedynych drzwi w tym pokoju (nie ma okien) w taki sposób, że wszystkie ścianki są równoległe do ścian pokoju. Twój znajomy może wejść do pokoju i może w dowolny sposób obrócić kostkę z zastrzeżeniem, że musi ją ustawić w tym samym miejscu: tj. na środku pokoju, ze ściankami równolegle do ścian pokoju.

Następnie znajomy zostanie wyproszony z pokoju, a Ty wejdziesz do środka i możesz zobaczyć wyłącznie pięć ścianek kostki (nie widzisz ścianki skierowanej do podłogi). Twoim zadaniem jest stwierdzić jaka liczba znajduje się na dolnej ściance.

Dla jakiej maksymalnej wartości N zadanie jest wykonalne i jaką instrukcję musisz wcześniej dać swojemu znajomemu (poza tą instrukcją, nie możecie się komunikować)?

[stefan_pompka]

@almafater: ze znajomym olewamy to i idziemy na piwo.

[pepkin88]

Na razie mam instrukcję dla N = 9, ale pewnie da się więcej.

[pepkin88]

@almafater: Strzelam

[k0rn1k]

@almafater: N=25? Zaraz postaram się napisać w miarę zrozumiałe rozwiązanie.

[a.....r]

@pepkin88: Da się więcej.

@k0rn1k: Zastanów się nad więcej zanim zaczniesz pisać ;)

[brak_nicku]

@almafater: 45?

[a.....r]

@brak_nicku: Przesadziłeś :)

Podpowiem tylko, że największe rozwiązanie nie jest znacząco większe od rozwiązania @k0rn1k.

[brak_nicku]

@almafater: uchylisz rąbka tajemnicy, czy czekasz:)

[a.....r]

@brak_nicku: Zapomniałem o tym zupełnie...

@k0rn1k: To możesz napisz to swoje rozwiązanie dla N=25 - może się okazać, że jest tak naprawdę bardzo podobne do tego, o które chodzi, a będzie tylko wymagało małych poprawek :)

[brak_nicku]

@almafater: dla 25, to ja sam mógłbym napisać, tylko nie wiem, czy dam radę się wysłowić, bo mam lekką gorączkę:)

[a.....r]

@brak_nicku: Spróbuj, dasz radę ;)

[brak_nicku]

@almafater: tę na górze możemy wybrać tak, że jest k-ta najwyższa spośród 5, a tę "twarzą do drzwi" jest n-ta najwyższa spośród pozostałych czterech, zatem mamy 20 kombinacji, którym możemy przypisać jedną z brakujących ze zbioru liczb. Dodajemy 5 widocznych i daje to 25. Mam nadzieję, że piszę językiem zrozumiałym dla ludzi:) 45 podałem, bo wydawało mi się, że każdą z 20 kombinacji można podzielić na 2 przypadki, ale sam potem

[a.....r]

@brak_nicku: Sam miałem trochę trudny dzień i teraz nie wiem czy opis jest mało precyzyjny czy ja nie łapię ;) Ale skąd wiadomo ile wynosi n i k?

[brak_nicku]

@almafater: jak mam 6 liczb od 1 do 25, widzę 5 z nich, to wiem, że jeśli na górze jest x, to jest to k-ta największa liczba ze zbioru widocznych pięciu. Widzę też liczbę na ścianie w kierunku drzwi i jestem w stanie określić, którą największą spośród 4 bocznych ścian jest ta liczba. Potem przypisuję (k,n) - m:

(1,1) - 1

(1,2) - 2

(1,3) - 3

(1,4) - 4

(2,1)

[a.....r]

@brak_nicku: Racja, już rozumiem :)

W zasadzie metoda nie odbiega aż tak znacząco od metody dla większego N.

Ok, mogę zdradzić, że największa możliwa opcja to dla


Zobaczymy czy z tą wiedzą wam się uda ;)

[k0rn1k]

@almafater: @brak_nicku bardzo zgrabnie to wyjaśnił. A skoro 29, to coś czuję, że będą 6x4 kombinacje+5 liczb widocznych.

[brak_nicku]

@k0rn1k: tylko skąd wiedzieć, która z 6 jest na górze:)

[k0rn1k]

@almafater: @brak_nicku:

Odmiana poprzedniej metody:

1. sprawdzamy, która (k-ta) jest ścianka od strony drzwi w zbiorze (drzwi, górna, lewa, prawa) - 4 możliwości.

2. sprawdzamy, która (n-ta) jest ścianka górna w zbiorze (górna, lewa, prawa) - 3 możliwości.

3. sprawdzamy, czy ścianka od strony drzwi jest większa, czy mniejsza od jej przeciwnej - 2 możliwości.

4x3x2+5 = 29?

[brak_nicku]

@k0rn1k: właśnie chciałem dopisać, że równie dobrze to 4x3x2+5, ale już dziś myślę zbyt ociężale żeby sprawdzić czy masz rację

[pepkin88]

@almafater: @brak_nicku: Ja mam pytanie: skąd pewność, że zawsze da się ustawić tak tę liczbę na górze? Przecież jak przekręcamy kość to zmienia nam się zestaw liczb widocznych, zatem zmienia się też liczba k.

[brak_nicku]

@k0rn1k: chciałem jeszcze dopisać do swojego rozwiązania warunek: jeśli ta na lewo od drzwi jest większa od tej na prawo od drzwi to do k dodaj 1. Tylko nie mam pojęcia, jak udowodnić, że kostkę zawsze można ustawić na te 2 sposoby

[brak_nicku]

@pepkin88: masz 5 liczb, ustawiasz k- tą najwyższą u góry - to jest proste. Potem z pięciu wykluczasz k-tą najwyższą i spośród pozostałych czterech n-tą najwyższą ustawiasz do drzwi. Pierwszy krok ogranicza zbiór liczb dostępnych w drugim, więc nie ma związku między pierwszym krokiem a drugim

[pepkin88]

@brak_nicku: Jak mam ustawić k-tą, skoro nie znam k? Przecież k jest determinowane przez liczbę na spodzie. Czy jednak nie?

[pepkin88]

@brak_nicku: Inaczej. Dla każdej liczby na kostce jest tylko jedna możliwa liczba k. Teoretycznie istnieje możliwość, że nie będę mógł ustawić kostki tak, aby następna osoba mogła to dobrze odczytać.

[pepkin88]

@almafater: @brak_nicku: Weźmy zwykłą kostkę do gry:

1 na spodzie, 6 na górze - k = 1

2 na spodzie, 5 na górze - k = 2

3 na spodzie, 4 na górze - k = 3

4 na spodzie, 3 na górze - k = 3

5 na spodzie, 2 na górze - k = 4

6 na spodzie, 1 na górze - k = 5

Chodzi o to,

[k0rn1k]

@pepkin88: Masz nadmiar swobody w ustawianiu k, ponieważ jeśli chcesz ustawić k=3, to możesz skorzystać z dwóch powyższych możliwości. Ustawiasz wybrane k (jedno z 5), następnie obracasz kostkę w kierunku drzwi, aby zdefiniować n (jedno z 4).

[pepkin88]

@k0rn1k: Najpierw muszę znać liczbę na spodzie, żeby znać k i n do zakodowania. Dla każdej liczby na spodzie liczby k i n do zakodowania są inne.

[pepkin88]

@almafater: @brak_nicku: @k0rn1k: Ja nie twierdzę, że to jest złe rozwiązanie, prawdopodobnie jest dobre, jednak brakuje tutaj dowodu na to, że dla każdego danego na początku zbioru liczb oraz dla każdego możliwego sposobu wybrania liczb na kostce, da się ustawić kostkę w pożądany sposób.

[a.....r]

@k0rn1k: @pepkin88: Na pierwsze sprawdzenie to rozwiązanie wygląda na poprawne, ale jako że jestem ekstremalnie padnięty, pomyślę nad tym na spokojnie jutro ;)

[brak_nicku]

@pepkin88: ja też nie twierdzę, że to dobre rozwiązanie. Co więcej, wiem, że to złe, bo almafater już napisał, że jest lepsze. Poza tym masz sporo racji w tym co piszesz, ale ja dziś już nie kontaktuję i merytorycznie się nie włączę w dyskusję

[pepkin88]

@almafater: @brak_nicku: @k0rn1k: Mam przykład obalający metodę @brak_nicku (sorry).

Dany na początku zbiór to liczby naturalne od 1 do 25. liczby na kostce to liczby z przedziału od 5 do 10. Układ na kostce liczb jest taki, że parami liczb na przeciwko są: 5 i 6, 7 i 8, 9 i 10 (tj. 5 i 6 leżą na przeciwko sobie, itd.).

Zakładając tę numerację nie będę mógł nigdy uzyskać

[a.....r]

@pepkin88: Masz rację. Chyba przez jakąś niejasność umysłu (?) zapomniałem, że o ile kostkę można przestawiać, to przecież nie można zmieniać tego co ma na ściankach w dowolny sposób.

Tak więc rozwiązanie, które ja znam jest faktycznie lepsze.

Nie wiem czy chcecie żeby coś z niego zaspoilować czy na razie nic?

[pepkin88]

@almafater: Ja bym jeszcze chciał trochę samemu powalczyć. Niech zadanie dojrzewa w mózgu, może w końcu dostąpię jakiegoś olśnienia :P

[a.....r]

@pepkin88: @brak_nicku: @k0rn1k: Właśnie zdałem sobie sprawę, że to już miesiąc wisi...

Jak wiadomo, co najwyżej możemy mieć N=29.

Załóżmy, że mamy liczby od 0 do 28.

Znajomy dodaje wszystkie liczby na kostce i liczy resztę z dzielenia tej sumy przez 6. Załóżmy, że wynik to i, gdzie 0≤i≤5. Jeżeli i=0, to do podłogi skierowuje ściankę z najmniejszą wartością, jeśli i=1 to ściankę z drugą najmniejszą

[brak_nicku]

@almafater: dla mnie jasne, ale jeszcze muszę przemyśleć skąd wynika kongruencja, ale to już do rozgryzienia na spokojnie:)