Cztery kulki
Cztery kulki na górnym poziomie są gotowe do staczania się kolejno po stoku z czterema ponumerowanymi dołkami (piąty dołek jest bezdenny – sięga do nieskończoności).
Pod literami na kulkach ukrywają się cyfry – takie jak numery dołków, czyli od 1 do 4, ale cyfry na kulkach nie muszą być różne. Kulki staczają się pojedynczo i jeśli kulka z cyfrą x trafia na dołek z numerem x, to do niego wpada. Nad dołkiem z innym numerem kulka przelatuje dalej – ale tylko wtedy, gdy jeszcze nie dotrze do dołka ze swoją cyfrą. Jeśli natomiast okaże się, że dołek z jej cyfrą został już wcześniej zajęty, wtedy wpada do najbliższego następnego wolnego dołka – niezależnie od jego numeru.
Łatwo zauważyć, że przy niektórych numeracjach kulek przynajmniej jedna z nich trafi do nieskończoności. Na przykład dla abcd=1231 taki los spotka kulkę d. Ponadto więcej niż trzy kulki nie polecą do „piekła”, a trzy wpadną tylko w jednym przypadku, gdy abcd=1111.
Jeśli umówimy się, że cyfry na kolejnych kulkach tworzą 4-cyfrową liczbę, to ile jest takich liczb, dla których efektem spadania będzie znalezienie się czterech kulek w czterech ponumerowanych dołkach, czyli bez trafienia którejś do piekła?
A może komuś uda się znaleźć ogólny wzór na liczbę liczb „bezpiekielnych” dla n kulek i n dołków.
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Jeśli moje kulki staczają się właściwie, to jest 125 liczb 4-cyfrowych dla których nic nie wpada do piekła.
W poszukiwaniu wzoru ogólnego:
Dla liczb 4 cyfrowych:
125 to jest 5 do potęgi 3.
Czyli (4+1) do potęgi (4-1).
Analogicznie dla liczb 5 cyfrowych byłoby:
(5+1) do potęgi (5-1) = 1296
Sprawdziłem eksperymentalnie, że to działa.
Tutaj liczba możliwych kombinacji to 4^4 = 256.
Nie ma problemu, jeżeli kulki mają różne liczby, nieważne w jakiej są kolejności.
Problem pojawia się dla powtórzeń, bo jeżeli x powtarza się n razy, to powinno zostać min. (n-1) ‚wolnych’ elementów, czyli mniejszych od x.
Przykładowo, jeżeli 3 powtarza się 2 razy, to ALBO 1 ALBO 2 nie są już ‚wolne’.
Jeżeli 3 powtarza się 3 razy, to nie ma wolnych elementów, i jedyna możliwa kombinacja to 4-3-3-3.
Wykluczone jest powtórzenie 1, bo nie ma mniejszej dostępnej liczby.
Liczba kombinacji błędna, choć rozumowanie w zasadzie poprawne.
mp
Odpowiedź dla n kulek to: (n+1)^(n-1).
Dla n=4 mamy 5^3 = 125.
Przy wyprowadzaniu ogólnego wzoru pomocne było spostrzeżenie, że dla n kulek liczba różnych k cyfrowych początków naszych liczb wynosi ((n+1)^(k-1))*(n+1-k).
Ogólny wzór mi wyszedł taki:
(n + 1)^(n – 1)
dla n = 1 tych liczb jest 2^0 = 1
dla n = 2 tych liczb jest 3^1 = 3
dla n = 3 tych liczb jest 4^2 = 16
dla n = 4 tych liczb jest 5^3 = 125
Czyli 4-cyfrowych liczb spełniających warunki zadania jest 125.
Pani Olu, czy mogę prosić o krótki opis sposobu wyprowadzenia wzoru?
mp
15 “bezpiekielnych” liczb dla 4 kulek i 4 dołków
Ogólny wzór: n!-!n
Dla n=4 bezpiekielnych kulek jest 125.
Ogólnego wzoru raczej nie zdążę wyprowadzić, ale zadanie jest świetne.
A jednak się udało: (n+1)^(n-1)
Sprawdziłem do n=7.
Ciąg prawie identyczny z tym: https://oeis.org/A000272
Ustaliłam dla pierwszych czterech n na piechotę, ile ostatecznie jest zestawów tych liczb. A potem wnikliwie przyjrzałam się tym liczbom, usiłując znaleźć prawidłowość. Przyszła mi do głowy właśnie taka. Uznałam, że wysonduję, czy jest dobra, zamieszczając odpowiedź na Łamiblogu. Jeśli wzór byłby nietrafny (wszak zgodność dla 4 liczb to jeszcze nic), to najwyżej Pan ujawni i będę myśleć dalej.
🙂 No cóż, można i tak, choć spodziewałem się czegoś bardziej analitycznego (matematycznego).
mp
Zapisków analitycznych mam parę stron, tylko finału jakby brak 🙂 A, nie finał znam. To brak środka.
Do nieba idzie 125 liczb a do piekła 131.
Dla n=4, 107 mówi, że jest tyle liczb dla których jedna kulka wpada do piekła, 23 liczby dla których 2 wpadają do piekła, itd…
n= 4
niebo 125
piekło 131
niebo/piekło 0.9541984732824428
poziomy piekła [131, 107, 23, 1, 0]
niebo + piekło = 256
———————————————————-
n= 5
niebo 1296
piekło 1829
niebo/piekło 0.7085839256424276
poziomy piekła [1829, 1346, 436, 46, 1, 0]
niebo + piekło = 3125
———————————————————-
n= 6
niebo 16807
piekło 29849
niebo/piekło 0.5630674394452075
poziomy piekła [29849, 19917, 8402, 1442, 87, 1, 0]
niebo + piekło = 46656
———————————————————-
n= 7
niebo 262144
piekło 561399
niebo/piekło 0.4669477501741186
poziomy piekła [561399, 341986, 173860, 41070, 4320, 162, 1, 0]
niebo + piekło = 823543
———————————————————-
Nastał 1 lutego, więc można już zabrać głos w sprawie styczniowych zadań ze Świata Nauki, które są inkarnacją zagadnień kulkowych z tego wpisu:)
Zadanie drugie, które polegało na znalezieniu liczby dobrych kolejek, które może utworzyć 5 aut na parkingu 7-miesjcowym, jest proste do zrealizowania programistycznie (w szczególności po przyswojeniu sprytnej reguły opisanej w artykule odrzucającej kolejki spełniające warunek s_k > k). Wynik wynosi 12288, a przykładowy program wygląda tak: github.com/ersonasolidna/lamiblogswiatnauki/blob/main/2024_01_Zad2.py
Jednak prawdziwym wyzwaniem byłoby znaleźć ogólną regułę na liczbę dobrych kolejek dla k pojazdów na n-miejscowym parkingu. Okazuje się, że post ejsj z 24 września zawiera ten wzór:
„Przy wyprowadzaniu ogólnego wzoru pomocne było spostrzeżenie, że dla n kulek liczba różnych k cyfrowych początków naszych liczb wynosi ((n+1)^(k-1))*(n+1-k).”
ejsj szukając wzoru (n+1)^(n-1) przeszła przez ((n+1)^(k-1))*(n+1-k), co jest uogólnionym rozwiązaniem zadania 2!
Niestety nie znam szczegółów rozumowania ejsj, ale podobno było ono pokrętne i inne niż to zaprezentowane w artykule. Jednak analityczne!