Budowanie wieży z cegieł. Problem Frobeniusa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Mati2000xcx
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 26 maja 2017, o 21:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 4 razy

Budowanie wieży z cegieł. Problem Frobeniusa

Post autor: Mati2000xcx »

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.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Budowanie wieży z cegieł. Problem Frobeniusa

Post autor: kerajs »

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ą.
Mati2000xcx
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 26 maja 2017, o 21:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 4 razy

Budowanie wieży z cegieł. Problem Frobeniusa

Post autor: Mati2000xcx »

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.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Budowanie wieży z cegieł. Problem Frobeniusa

Post autor: Brombal »

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}\).
Ostatnio zmieniony 24 cze 2019, o 14:09 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Poprawa wiadomości: \ge. Interpunkcja.
ODPOWIEDZ