Przyjaciele w restauracji

[cardemon]

Pewnego razu pieciu przyjaciol (lubiących bardzo zagadki logiczne) wybrało
się wspólnie do bardzo egzotycznej restauracji serwujacej wylacznie potrawy
kuchni Mikronezji. Panowie nigdy wczesniej nie byli w tej restauracji ani tez
na wyspach Pacyfiku i nazwy wszystkich potraw byly dla nich zupelnie obce.
Kazdy z nich zamowil dokladnie jedno danie z dziewieciu, jakie figurowaly w
menu. Kelner potrawy przyniosł i ustawil je dokladnie po srodku stołu tak, ze
nie wiadomo bylo, ktora jest ktora. Przyjaciele specjalnie nie nastawali na
kelnera, by ten pokazal, ktore danie z karty jest ktorym na stole. Wrecz
przeciwnie; potraktowali cale zajście jako doskonałą zagadkę logiczną, po
czym stwierdzili, ze tak szczęśliwie sie sklada, ze aby skosztowac wszystkich
potraw z menu i moc jednoczesnie wskazac z wyglądu, jak sie kazda z nich
nazywa, beda musieli jeszcze przyjsc do tej restauracji kilka razy i postapic
tak samo jak dzis, czyli kazdy zamowi po jednym daniu z menu.

Ile razy w sumie przyjaciele odwiedzili te restauracje, by poznac wyglad,
smak i nazwy wszystkich potraw?

Nalezy zalozyc, ze za pierwszym razem ich zamowienie bylo tak szczesliwe, ze
w sumie wyszla im najmniejsza mozliwa liczba.

Pozdrowienia i powodzenia dla wszystkich łamigłowkowiczów,
CdM

3

[mesquaki]

Popieram: 3 (notxt)

[marchewa4]

[musztardek]

Oj, ja bym musiał wysłać ich jeszcze trzy razy oprócz pierwszej wizyty...
Czyli wychodzi mi na to, że 4 razy, i nie mam na razie pojęcia, jak to
zmniejszyć :(

Pozdrawiam,
Musztardek

OK, 3 wystarczą.

[musztardek]

musztardek napisał:

> wychodzi mi na to, że 4 razy, i nie mam na razie pojęcia, jak to
> zmniejszyć :(


I ledwie to napisałem, doszedłem do sposobu, w którym wystarczają 3 dni.
Wcześniej niepotrzebnie założyłem, że jedna z potraw musi być zamawiana w 3
różne dni.

Pozdrawiam raz jeszcze,
Musztardek

[cardemon]

Oczywiscie odpowiedz trzy wizyty w restauracji wystarczą, jest prawidlowa. Moze
ktos by sie pokusil o podanie przykladowych zamowien potraw dla kazdego dnia?
A czy mozna jakos udowodnic, ze NIE wystarczą trzy wizyty dla poznania
DZIESIECIU dan?

[marchewa4]

cardemon napisał:

> Moze ktos by sie pokusil o podanie przykladowych zamowien potraw dla kazdego
> dnia?
No to sie pokusze:

1) 1, 4, 5, 7, 7
2) 2, 4, 6, 8, 8
3) 3, 5, 6, 9, 9

> A czy mozna jakos udowodnic, ze NIE wystarczą trzy wizyty dla poznania
> DZIESIECIU dan?

I znow trzeba myslec ;-)

M.

[marchewa4]

marchewa4 napisał:

> > A czy mozna jakos udowodnic, ze NIE wystarczą trzy wizyty dla poznania
> > DZIESIECIU dan?
Sprobujmy tak (dowod jest zmudny i jego przesledzenie wymaga chyba kartki
papieru; szkoda, ze nie da sie na forum rysowac ;-)):

Przyjmijmy, ze sie da i pokazmy sprzecznosc.

Opiszmy kazde danie uporzadkowana trojka liczb (ile dan tego rodzaju zamowili
przyjaciele odpowiednio 1, 2 i 3 dnia). Zeby dania mozna bylo rozpoznac po
wygladzie i poznac ich smak kazda trojka musi byc rozna i zadna nie moze
skladac sie wylacznie z 0.
Zauwazmy, ze suma liczb na poszczegolnych pozycjach dla wszystkich 10 dan
wynosi 5.
Zatem co najmniej 5 dan musi miec na pozycji 1 liczbe 0, co najmniej 5 dan na
pozycji 2 liczbe 0 i co najmniej 5 dan na pozycji 3 liczbe 0.
Bez zmiany ogolnosci przyjmijmy, ze pierwszych 5 dan ma na pozycji 1 liczbe 0.
Rozpatrzmy dalej nastepujace przypadki:
a) co najmniej 3 z pierwszych pieciu dan maja na pozycji 2 liczbe 0.
Zeby dalo sie rozroznic te trzy dania musza one miec na pozycji 3 rozne liczby.
Nie moze to byc 0. Najmniejsza suma trzech roznych liczb calkowitych dodatnich
wynosi 6 (1+2+3), a to juz jest wiecej od 5 -> sprzecznosc.

b) zadne z pierwszych 5 dan nie ma na 2 pozycji liczby 0.
Wszystkie 5 dan z drugiej piatki ma zatem na drugiej pozycji liczbe 0.
Poniewaz co najmniej 5 dan ma na 3 pozycji liczbe 0, zatem co najmniej 3 dania
sposrod pierwszych pieciu maja na pozycji 3 liczbe 0 lub co najmniej 3 dania
sposrod drugich pieciu maja na pozycji 3 liczbe 0. W obu przypadkach mamy trzy
dania, ktore na dwoch takich samych pozycjach maja 0. I analogicznie jak w a.

c) jedno z pierwszych 5 dan ma na drugiej pozycji liczbe 0.
Bez zmiany ogolnosci (ze wzgeldu na symetrie numeracji dan) mozemy przyjac, ze
jest to danie nr 1, a pozostale dania, ktore maja na pewno liczbe 0 na drugiej
pozycji to 6 - 9.
Na pozycji 3 liczbe 0 ma na pewno co najmniej 5 dan. Jesli co jamniej 3 dania z
grupy 2-5 lub co najmniej 3 dania z grupy 6-9 mialy na trzeciej pozycji 0, to
mielibysmy znow przapdaek jak w a). "Najgorszy" przypadek jest wtedy, gdy danie
nr 10 ma na 3 pozycji 0, a pozostale 4 zera sa po dwa rozdzielone w grupach 2-5
i 6-9. I znow bez zmiany ogolnosci niech beda to dania 2,3 oraz 6,7.
Zeby rozroznic od siebie dania 2 i 3 musza one miec na pozycji drugiej dwie
rozne liczby calkowite dodatnie. Ich najmniejsza suma wynosi 3. Zatem co
najmniej dla jednego z dan 4,5,10 musi na drugiej pozycji tez wystapic liczba 0.
Jesli byloby to 10, to mamy trzy dania, ktore na pozycjach 2 i 3 maja 0:
6,7,10. I analogicznie jak w a)
Zeby odroznic od siebie dania 6 i 7 musza one miec na pozycji pierwszej dwie
rozne liczby calkowite dodatnie. Ich najmniejsza suma wynosi 3. Zatem co
najmniej dla jednego z dan 8,9,10 musi na pierwszej pozycji tez wystapic liczba
0.Jesli byloby to 10, to mamy trzy dania, ktore na pozycjach 1 i 3 maja 0:
2,3,10. I analogicznie jak w a)
Jesli w obu opisanych przypadkach nie jest to danie 10, to mamy trzy dania,
ktore na pozycjach 1 i 2 maja 0. A mianowicie: 1, (4 lub 5), (8 lub 9).
I analogicznie jak w a).

d) dwa z pierwszych dan maja na pozycji 2 liczbe 0.
niech beda to (b.z.o.) dania 1 i 2. Zeby sie je dalo rozroznic musza one miec
na 3 pozycji dwie rozne liczby calkowite dodatnie. Ich najmniejsza suma wynosi
3. Zatem suma liczb na 3 pozycji dla pozostalych 8 dan wynosi co najwyzej 2,
stad wniosek, ze co najmniej 6 sposrod tych liczb jest rowne 0.
Zalozmy dalej (b.z.o.), ze dania, ktore maja na drugiej pozycji liczbe 0, to
oprocz 1 i 2 rowniez 6, 7 i 8. Jesli co najwyzej jedno z dan 9, 10 ma na
trzeciej pozycji 0, to co najmniej 5 zer przypada na 3 pozycji dla dan 3-8.
Zatem co najmniej 3 z nich przypadaja na dania 3-5 lub co najmniej 3 z nich
przypadaja na dania 6-8. W obu przypadkach znow mamy trzy dnia jak z punktu a)
Pozostaje do rozpatrzenia sytuacja, kiedy oba dania 9 i 10 maja na trzeciej
pozycji 0. Pozostaja do rozdzielenia jeszcze 4 zera na pozycji 3. "Najgorszy"
przypadek jest wtedy, gdy przypadaja one po rowno na grupy 3-4 i 6-8. Bez
zmiany ogolnosci mozemy przyjac, ze sa to dania 3, 4, 6 i 7. Zeby odroznic od
siebie dania 3 i 4 musimy miec na pozycji drugiej dwie itd. Zatem na pozycji
drugiej dla pozostalych dan (5, 9, 10) musi byc co najmniej jedno 0.
Jesli jest to danie 5, to mamy trojke dan (1,2,5) jak z punktu a)
Jesli jest to 9 lub 10, to tez mamy trojke dan (9 lub 10, 6, 7) jak z punktu a).

Gratuluje cierpliwosci wszystkim, ktorzy dotarli do tego punktu moich wypocin i
liczac na to, ze ktos poda prostszy dowod pozdrawiam wszystkich

M.