Bez różnicy

[tororo]

Masz 10 urn. Rozmieść w tych urnach jak najwięcej kul ponumerowanych
kolejnymi liczbami naturalnymi (od 1 począwszy) tak, żeby w żadnej urnie nie
było kuli z liczbą (numerem), która jest różnicą dwóch dowolnych numerów kul
w tej samej urnie.

pozdr

tororo
www.rozgrywka.pl

[Gość: lukkasz]

O ile mój pomysł jest dobry i nie pomyliłem się w rachunkach, wychodzi 1535.
Pozdr,
lukkasz

[Gość: Dr Zoidberg]

Ja raczej umiem rozmiescic tak 29524 kulek. O ile nie pomylilem sie w
rachunkach. Nie twierdze takze, ze to jest najlepsze rozwiazanie.
Pozdro
Dr Zoidberg

[tororo]

Doktorze Zoidberg i dokładnie i daleko :)

Znana jest mi bowiem informacja iz matematycy węgierscy P.Erdös i J.Surányi
udowodnili twierdzenie iz dla tego problemu zachodzi zachodzi nierówność

N< 3n!

gdzie N to maksymalna liczba kulek a n to liczba grup. dla n=10 wychodzi okrona
liczba 10 886 400. Czyli daleko. Jednakże najlepsza znana mi realizacja tego
problemu okresla maksymalna liczbe kulek wzorem

N = ((3 do potegi n) -1)/2 czyli dokładnie 29 524.

A zatem BINGO!
A może pokazesz Doktorze swoja metode zanim ja ujawnie tę która znam?


pozdr
tororo
www.rozgrywka.pl

[Gość: Dr Zoidberg]

Moge pokazac, aczkolwiek to moze byc troche skomplikowane.
Moze przedstawie to rekurencyjnie.
Dla 1 kociolka wrzucamy do niego jedna kulke i po klopocie.
Dla n kociolkow wrzucamy ile sie da do n-1 kociolkow (przypusmy, ze dalo sie k)
a nastepnie k+1 kulek do n-tego kociolka i znowu k kulek do pierwszych n-1
kociolkow. Latwo pokazac, ze takie wrzucanie bedzie spelnialo warunki zadania.
Oczywiscie, zakladamy, ze umiemy wrzucic k kulek do n-1 kociolkow.
Gdyz:
w n-tym kociolku najwieksza roznica to 2k-1 - k = k-1 a najmniejsza liczba w
tymze kociolku to k.
w n-1 kociolkach kulki z 1 wrzucania spelniaja warunki (na mocy zalozenia)
w n-1 kociolkach kulki z 2 wrzucania spelniaja warunki, bo
zadna roznica nie jest liczba z 1 wrzucania(bo to sa takie same roznice jak
w 1 wrzucaniu)
maksymalna roznica wynosi k-2 i jest daleko od minimalnej liczby w 2
wrzucaniu.

Jak sie rozwikla te rekurencje, tzn t(n) = t(n-1) + t(n-1)+1 + t(n-1) = 3*t(n-1)
+1
z warunkiem brzegowym t(1) = 1 to pewnie wychodzi to co mialo wyjsc.
Ale moglem sie gdzies pomylic, chociaz mocno w to watpie.
Moge jeszcze dodac, ze to byl moj drogi pomysl wrzucania. 1 byl zdecydowanie
ladniejszy, niestety nie tak skuteczny.
Oto ladna idea.
Do i-tego kociolka wrzucamy kulki (i-1)-parzyste. i-parzystosc niech oznacza ze
dana liczba dzieli sie przez 2^i, ale juz nie przez 2^(i+1).
Wtedy w kazdym kociolku roznice sa conajmniej o 1-wiecej parzyste niz liczby.
Niestety, tylko 1023 kulki uda sie w ten sposob powrzucac.
Pozdro
Dr Zoidberg