>Spotkałem się ostatnio z pewnym problemem i prosiłbym o pomoc w jego rozwiązaniu.
>Otóż:
>mamy 3 xboxy i budynek o n piętrach. Musimy sprawdzić z jakiego najwyższego piętra możemy zrzucić
>xboxa bez jego uszkadzania. Rozważ ten problem dla n=10.
Wprawdzie nie wiem, co to są xboxy, ale mocno przypuszczam, że problem jest empiryczny, a nie matematyczny.

Musisz mi podpowiedzieć, czy z dla n=1 wiadomo, że się NIE rozbije?
Jeśli nie, to:
dla n=10 zrzucasz z 5, później z 3 lub 7 , później z 2 lub 4, albo z 6 lub 8. Nie ogarnięte zostają piętra 9 i 10. Za to dostajemy odpowiedź DOKŁADNĄ.

Jeśli chcesz odpowiedzi NIEdokładnej, to idzie się algorytmem złotego podziału odcinka.

Pozdrawiam

---

Server and receiver are both blind.

W zadaniu nie ma nic o ilości prób, wystarczy jedno urządzenie i testowanie co piętro od dołu w górę. Po zniszczeniu masz odpowiedź.

>W zadaniu nie ma nic o ilości prób, wystarczy jedno urządzenie i testowanie co piętro od dołu w górę. Po zniszczeniu masz odpowiedź.

Jeśliby tak było nie nazwałbym tego problemem matematycznym. Chodzi o rozwiązanie go w czysto matematyczny sposób.

>>W zadaniu nie ma nic o ilości prób, wystarczy jedno urządzenie i testowanie co piętro od dołu w górę. Po zniszczeniu masz odpowiedź.
>Jeśliby tak było nie nazwałbym tego problemem matematycznym. Chodzi o rozwiązanie go w czysto matematyczny sposób.

Nie rozumiem co uważasz za matematyczne rozwiązanie. Może spróbuj przeformułować zadanie to będzie wiadomo czy w zadaniu pytasz o minimalną ilość prób, czy o minimalizację uszkodzonych urządzeń. Nie wszystkie zadania muszą mieć jedną poprawną odpowiedź.

>Nie rozumiem co uważasz za matematyczne rozwiązanie. Może spróbuj przeformułować zadanie to będzie wiadomo czy w zadaniu pytasz o minimalną ilość prób, czy o minimalizację uszkodzonych urządzeń. Nie wszystkie zadania muszą mieć jedną poprawną odpowiedź.

To zadanie, w takiej formie zostało mi przedstawione przez wykładowcę. Jeśli ilość prób nie była, by określona zadanie było by banalnie proste. Utrudnianie sobie życia to nie jest coś co szczególnie lubię, ale w tym przypadku postanowiłem to zrobić. Założyłem, że moja wiedza jest nie pełna i być może istnieje jakiś algorytm, pozwalający rozwiązać to zadanie, przy założeniach, że chodzi o ilość prób, a wynik zawiera się w 0<=n<=10.
Poniżej przeformułowałem to zadanie na problem z monetami, który mam nadzieję jest bardziej precyzyjny i przepraszam, że ten taki nie był.

Załóżmy, że xbox zrzucony z pierwszego piętra nie uszkadza się.

Z założenia mamy, więc że w P(1)=0.

Ponieważ indukcyjnie każde kolejne piętro da się przedstawić w postaci sumy n(x) pięter pierwszych:

n=(n-1)+1=(n-2)+1+1...

mamy P(n₁)+P(n₂)+...+P(n_n)=0+0+...+0=0

Indukcyjnie mamy, więc odpowiedź

Teraz poważnie. Najszybszy algorytm wyszukiwania jaki znamy dla posortowanych danych działa ze skutecznością log2n . log2(10)~3,35 czyli trzy próby niestety mogą w tym przypadku nie wystarczyć. Jesteśmy jednak w komfortowej sytuacji, bo możemy zejść po xboxa i rzucić nim ponownie.

Możemy więc zrzucać xboxa do skutku. Najpierw z pierwszego piętra, później z drugiego itd. aż do skutku. Dla oszacowania niepewności możemy powtórzyć dla pozostałych dwóch xboxów i oszacować odchylenie standardowe i na tej podstawie zawęzić wyniki.

Jeśli natomiast przyjmiemy założenia, że nie możemy drugi raz rzucać każdym xboxem bo np. jesteśmy księżniczką zamkniętą w wieży, która próbuje umilić sobie czas to zadanie wydaje się nie być takie wesołe.

Dla n=8 nie byłoby żadnego problemu zrobić to w trzech rzutach. Zrzucilibyśmy z 4 piętra później z 2/6, a następnie 3/1 / 7/5. Dla n=10 chyba nie da się tego rozwiązać właśnie dlatego, że log2(10)=3,37 Wydaje mi się, że nie ma żadnej pewnej metody, niestety.

---

"Mądrość jest dobrem, aczkolwiek jest pożądana nie sama dla siebie, ale z uwagi na konsekwencje"

>Jesteśmy jednak w komfortowej sytuacji, bo możemy zejść po xboxa i rzucić nim ponownie.
Wpadłem na ten pomysł nieco wcześniej i dobrze, że nie zdążyłem go rozwinąć, bo nie był wtedy całkiem dojrzały.
Dysponujemy tylko trzema xboxami, więc musimy postępowac z nimi rozważnie. Rzucamy abox z 3-go piętra. Nie rozbije się, to bbox z 5-go. I ten przeżyje, to cbox z 7-go. Rozbił się - pech! Taki wynik obarczony jest największym błędem. Jeżeli nie, zrzucamy dalej cbox z 7-go aż do skutku. Wynik notujemy. Teraz każdy doświadczony doświadczalnik (inklusive ja) na podstawie tego wyniku (i następnego) wyznaczy dalsze piętra i xboxy. Otrzyma np. wyniki z pięter 7, 5 i 4 (zaniedbujemy zrzut z 3-go). Bierzemy teraz ODWROTNOŚCI tych wyników (żeby uwolnić się od nieskończoności) i nanosimy jako c(7), b(5) i a(4) przeciw oś pięter. Teraz metodą najmniejszych kwadratów wyznaczamy prostą (przy większej ilości xboxów dużo lepszą parabolę), której punkt przecięcia z osią pięter daje nam żądany wynik.
Może da się to udoskonalić, ale podkreślam jeszcze raz: o żadną poważną matematykę się tu nie rozchodzi, czysta buchalteria empiryczno-statystyczna.

Bardzo empiryczne podejście. Ja skromny teoretyk z informatycznym zacięciem pominąłem zużywanie się xboxów po tym jak zostały rzucone.

Autor zadania mógłby coś więcej o nim powiedzieć, bo bezsprzecznie Twoje rozwiązanie empiryczne wydaje mi się najlepsze. Jeżeli miała to być zagadka logiczno-matematyczna to wydaje mi się po prostu, że nie da się tego rozwiązać tak jak takich zagadek z ważeniem kulek np.

---

"Mądrość jest dobrem, aczkolwiek jest pożądana nie sama dla siebie, ale z uwagi na konsekwencje"

>Bardzo empiryczne podejście.
Bo zbierałem i nadal zbieram w dupę.
>Ja skromny teoretyk z informatycznym zacięciem pominąłem zużywanie się xboxów po tym jak zostały rzucone.
Jest jeszcze jeden ciekawy aspekt całej afery: co określamy jako rozbicie xboxu? Czy jedno pęknięcie robi już grę?
PS. Oj, Powinienem był to zdanie wykasować - jasne, że robi. Przynajmniej jako symptom. Taki xbox się na tym piętrze bankowo rozleci.
PS 2. Moje podejście ma jednak kopyto: niską, jak już wspomniałem,, sygnifikancję wyniku z najwyższego piętra. Możemy tedy odpuścić sobie najmniejsze kwadraty i ciągnąć prostą przez dwa pozostałe wyniki.
PS3. Znajdowanie bezpiecznej wysokości wielokrotnego upadku (to nie to, czegoi chciał autor) jest ograniczone przez kruchość materiału. Jeżeli założymy, że energia kinetyczna upadku kumuluje się jakoś w skrzynce, to ta rozleci się kiedyś i na pierwszym piętrrze. No chyba, że limitu sprężystości jakiegoś nie przekraczamy.

>Autor zadania mógłby coś więcej o nim powiedzieć, bo bezsprzecznie Twoje rozwiązanie empiryczne wydaje mi się najlepsze. Jeżeli miała to być zagadka logiczno-matematyczna to wydaje mi się po prostu, że nie da się tego rozwiązać tak jak takich zagadek z ważeniem kulek np.

Niestety w tym zadaniu chodziło mi tylko o właśnie logiczno-matematyczne rozwiązanie.
Sposób podziałem przy 3 próbach jest skuteczny dla n=2^3 czyli dla 8. Problem zaczyna się dla większego n, z tego co mi wiadomo powinna istnieć jakaś metoda na to.

>Problem zaczyna się dla większego n, z tego co mi wiadomo powinna istnieć jakaś metoda na to.

Rozważmy wszystkie 10 przypadków drzewa decyzyjnego przy pierwszym rzucie z 5 piętra.

1) 5 -> 2 -> 1 sukces
2) 5 -> 2 -> 1 sukces
3) 5 -> 2 -> 4 porażka, więc musimy założyć że skok następuje do 3, rozważmy jeszcze raz zmodyfikowany algorytm od tego momentu
3') 5 -> 2 -> 3 sukces
4) 5 -> 2 -> 3 sukces
5) 5 -> 2 -> 3 znów porażka, gdyż nie jesteśmy w stanie określić, czy się popsuje spadając z czwartego piętra, czy nie musimy więc rozpatrzyć algorytm od nowa na początku zrzucając z 4 piętra

Oszczędzę sobie pisania. Dla 4 piętra będzie to oczywiście działać. Startując od 4 jeśli z niego spadnie będziemy w stanie zdiagnozować wszystkie poniższe piętra.

Jeśli nie spadnie skoczmy do 6 wiadomo, że bez trudu określimy teraz czy 5 czy 6. Problemem będą wyższe, kiedy został nam jeden skok. Skacząc na 9 nie będziemy w stanie określić skąd spadnie. Przenosząc drugi skok w algorytmie na 7 stracimy możliwość określenia czy 6 czy 5. Stąd prosty wniosek, że nie ma rozwiązania.

Jeśli moje rozwiązanie nie przemawia to proponuję napisać program, który będzie testował wszystkie takie drzewa wyboru po kolei dla wszystkich 10 pięter. Jeśli jakiś algorytm zdiagnozuje poprawnie wszystkie 10 drzew to (dlatego że jest deterministyczny) to będziemy wiedzieć że się pomyliłem. Tych drzew będzie stosunkowo niedużo. I algorytm prosty. W sumie w excelu można zrobić.

Jestem jednak na 99,999% pewien, że to nie ma rozwiązania (patrz: mój słowny dowód powyżej).

---

"Mądrość jest dobrem, aczkolwiek jest pożądana nie sama dla siebie, ale z uwagi na konsekwencje"

Robimy 10 pięter (bez parteru) i 3 próby:
Czy ma rozwiązanie, jeśli w zadaniu jest ZAŁOŻENIE, że istnieje 10>=n>0, dla którego xbox się nie rozbija. Niestety Maciej.Ł prawdopodobnie nie doszedł do tego, że jest to ważna informacja.
Z powyższego założenia wynika, że ZAWSZE dla n=1 xbox przetrwa. Czy dla 10 pięter da się dojść do maksymalnego piętra z trzema próbami? Spróbujmy.
Zaczynamy od 7. Przetrwał. To 9. Przetrwał. To 10. Obojętnie, co wyjdzie, zrobione.
Alternatywnie. Zaczynamy od 7. Nie przetrwał. To 4. Nie przetrwał. To 3. Nie przetrwał i lądujemy w kłopocie, bo nie wiemy, czy n=1 czy n=2 jest właściwą odpowiedzią.
Wygląda na to, że wciąż brakuje nam jednego piętra do ogarnięcia. Co prawda mogą się zdarzyć ciągi, że otrzymamy odpowiedź, ale nie wszystkie one do niej prowadzą.
Pytanie, czy istnieje jeszcze jakaś informacja, która pozwoliłaby wyeliminować to jedno piętro?

Pozdrawiam

---

Server and receiver are both blind.

>Czy ma rozwiązanie, jeśli w zadaniu jest ZAŁOŻENIE, że istnieje 10>=n>0, dla którego xbox się nie rozbija.

Jeśli przyjmiemy, że 10>n>=0 wtedy tylko sprawdzić czy rozbija się w przedziale <2;9>, a to jest do zrobienia.

Zrzucamy z 5 i jeśli się rozbije to z 3 jeśli się rozbije to z 2, a jeśli nie to z 4.
Jeśli z 5 się nie rozbije to rzucamy z 8 i jeśli się rozbije to z 6 (teraz wiemy, że jeśli się nie rozbije to odpowiedzią jest 7 w przeciwnym wypadku 8). Jeśli z 8 się nie rozbije rzucamy ostatniego z 9 i tu też sprawa jest oczywista - jeśli się rozbił to 9, a jeśli nie to 10 (oczywiście przy założeniu, że z któregoś się rozbija).

Tak więc możemy to rozwiązać redukując problem tylko do 8 pięter. Każde założenia, które sprawiają, że chcemy wybrać z n pięter w x próbach muszą spełniać nierówność:

log2(n) <= x

---

"Mądrość jest dobrem, aczkolwiek jest pożądana nie sama dla siebie, ale z uwagi na konsekwencje"

>Robimy 10 pięter (bez parteru) i 3 próby:
>Czy ma rozwiązanie, jeśli w zadaniu jest ZAŁOŻENIE, że istnieje 10>=n>0, dla którego xbox się nie rozbija. Niestety Maciej.Ł prawdopodobnie nie doszedł do tego, że jest to ważna informacja.

Innych założeń nie ma, takie zadanie zostało mi przedstawione. Takie założenie prawdopodobnie jest słuszne, czy można je w tym zadaniu zastosować-nie wiem, i za to chciałbym przeprosić. Rozwiązania empiryczne, jak i z większą ilością prób, z racji że zadanie nie zawiera w tym względzie żadnych obostrzeń, są prawidłowe.

Jednak, aby ich uniknąć zaproponuję podobne zadanie:
Mamy 10 monet, w tym 1 fałszywą o niższej wadze. Dysponując 3 ważeniami określ która jest fałszywa.

I chciałbym przeprosić jeszcze raz, że poprzednie zadanie nie było precyzyjne.

Ważenie pierwsze - po 3 monety na szali. Jeśli waga pokazuje równowagę, to wiemy, że w pozostałej trójce jest fałszywa. Ważymy po jednej monecie z pozostałej trójki. Brak równowagi, to ważymy ostatnią monetę (nie ważoną jeszcze) z jedną monetą już ważoną - na tej podstawie ustalamy, która jest fałszywa (jeśli równowaga, to ta nie ważona; jeśli nierównowaga, to ta którą ważyliśmy dwa razy - przy okazji wychodzi, czy fałszywa jest cięższa czy lżejsza).

Oczywiście kolejność, to znaczy chwila, gdy natrafimy na sytuację nierównowagi może się przydarzyć przy pierwszym ważeniu. Ważymy wtedy ostatnią z trójek (nie ważoną jeszcze) z jedną z ważonych. To wystarcza, by ustalić, czy fałszywa moneta jest cięższa, czy lżejsza i w której trójce się znajduje.

Pozdrawiam

---

Server and receiver are both blind.

>Ważenie pierwsze - po 3 monety na szali. Jeśli waga pokazuje równowagę, to wiemy, że w pozostałej trójce jest fałszywa. Ważymy po jednej monecie z pozostałej trójki. Brak równowagi, to ważymy ostatnią monetę (nie ważoną jeszcze) z jedną monetą już ważoną - na tej podstawie ustalamy, która jest fałszywa (jeśli równowaga, to ta nie ważona; jeśli nierównowaga, to ta którą ważyliśmy dwa razy - przy okazji wychodzi, czy fałszywa jest cięższa czy lżejsza).
>Oczywiście kolejność, to znaczy chwila, gdy natrafimy na sytuację nierównowagi może się przydarzyć przy pierwszym ważeniu. Ważymy wtedy ostatnią z trójek (nie ważoną jeszcze) z jedną z ważonych. To wystarcza, by ustalić, czy fałszywa moneta jest cięższa, czy lżejsza i w której trójce się znajduje.
>Pozdrawiam
>

---

Server and receiver are both blind.

Niestety źle sformowałem to zadanie bo tutaj istnieje proste rozwiązanie dla n=14.
Jutro postaram się zrobić to lepiej.

Nie zauważyłem, że była lżejsza. Dwa ważenia wystarczają w takim przypadku.

Pozdrawiam

---

Server and receiver are both blind.

Na szczęście, czy też nieszczęście, autor zdążył uzupełnić, że jest lżejsza, Sceptymucha ma tutaj rację.
Nie do końca zresztą, bo po pierwszym ważeniu mamy 433, a z czwórki(jak wypadnie)nie wyizoluje się jednym ważeniem lżejszej/cięższej monety. Nie zawsze.

>Na szczęście, czy też nieszczęście, autor zdążył uzupełnić, że jest lżejsza, Sceptymucha ma tutaj rację.
>Nie do końca zresztą, bo po pierwszym ważeniu mamy 433, a z czwórki(jak wypadnie)nie wyizoluje się jednym ważeniem lżejszej/cięższej monety. Nie zawsze.

Przenosząc ten problem na zadanie poprzednie, z xboxami przy założeniu ze 3 xboxy odpowiadają 3 próby, chyba doszliśmy do wniosku, że nie ma metody która w 100% przypadków była by skuteczna.

>Przenosząc ten problem na zadanie poprzednie, z xboxami przy założeniu ze 3 xboxy odpowiadają 3 próby, chyba doszliśmy do wniosku, że nie ma metody która w 100% przypadków była by skuteczna.
Coś mi się widzi, że te dwa zagadnienia: zrzucanie xboxów i wynajdowanie fałszywej/lżejszej monety przez ważenie w ogóle nie są izomorficzne.
No chyba, że n pięter odpowiada n+1 monetom.

>Niestety w tym zadaniu chodziło mi tylko o właśnie logiczno-matematyczne rozwiązanie.
>Sposób podziałem przy 3 próbach jest skuteczny dla n=2^3 czyli dla 8.
W temacie zadania mowa jest o 3ch BOXACH, nie o 3ch PRÓBACH! Przecież jasne, że naprężenia powstałe po zrzucie z niższego piętra można zaniedbać w stosunku do skutków upadku z wiele wyższego. Taki box jest jeszcze do użytku.
Maruda zwrócił już na to uwagę, a ty go olałeś.

Mamy trzy urządzenia do zniszczenia, proponuję równoczesne zrzucanie większej ilości urządzeń w jednej próbie. W pierwszej próbie rzucamy urządzenia z pięter 1, 3 i 6. Nie musimy badać które przetrwało, sprawdzamy tylko ile urządzeń przetrwało i w kolejnej próbie w zależności od ilości urządzeń wybieramy piętra z których przeprowadzimy kolejną próbę.
Jeżeli zostało jedno urządzenie piętro 2.
Jeżeli zostały dwa urządzenia piętra 4 i 5.
Jeżeli zostały trzy urządzenia piętra 7, 8 i 9.
W ten sposób przy dwóch próbach sprawdzamy piętra od 1 do 9 włącznie. Przyjmuje też pewne "oczywiste założenia", które pomijam dla prostoty wypowiedzi.