Matematyka.pl

Mamy do dyspozycji cegły o wymiarach 6x10x15. Możemy, kładąc je jedną na drugiej(leżąco, na sztorc i stojąco), budować wieże. Wyznaczyć taką najmniejszą liczbę \(\displaystyle{ G \in N}\), że da się zbudować wieże każdej wysokości \(\displaystyle{ \ge G}\).

W książce mam dopisek, że jest to zbliżone do problemu Frobeniusa jednak tutaj liczby nie są względnie pierwsze. Próbowałem zrobić prosty generator takich kombinacji \(\displaystyle{ 6x+10y+15z}\) ale nawet dla bardzo dużych ograniczeń wciąż znajduję luki między liczbami.

Ta liczba to \(\displaystyle{ 30}\), gdyż kolejne sześć liczb \(\displaystyle{ 30,31,32,33,34,35}\) można wyrazić podaną sumą, ale liczby \(\displaystyle{ 29}\) nie można.

Nie stosowałem żadnego algorytmu. Zastanowiłem się kiedy ostatnią cyfrą może być 9. Najmniejsza taka liczba to \(\displaystyle{ 39=4 \cdot 6+15}\). Potem wystarczyło sprawdzić czy \(\displaystyle{ 30,31,32,33,34,35}\) można wyrazić podaną sumą.

Oh rzeczywiście, mam jeszcze jedno pytanie czy są jakieś dobre źródła mówiące coś o problemie Frobeniusa. Szukałem sam, ale po za wikipedią i kilkoma płatnymi pracami nie znalazłem nic ciekawego.

A gdyby założyć że istnieje dla \(\displaystyle{ x ,y, z\ge0}\) liczba \(\displaystyle{ G=6x+10y+15z}\).
Aby uzyskać liczbę równa \(\displaystyle{ G+1}\) wystarczy nadać wartości \(\displaystyle{ x_1=x+1 , y_1=y+1 , z_1=z-1}\).
Jak widać jedynie \(\displaystyle{ z}\) ulega zmniejszeniu o \(\displaystyle{ 1}\). Po osiągnięciu \(\displaystyle{ z=0}\) należy wielokrotność \(\displaystyle{ 15}\) usunąć \(\displaystyle{ x}\), a \(\displaystyle{ z}\) odpowiednio powiększyć. .
Pierwszą liczbą z wielokrotnością \(\displaystyle{ 15}\) jest \(\displaystyle{ x=5}\), czyli \(\displaystyle{ 30}\).