Matematyka.pl

Zagadka co prawda mojego autorstwa, ale jest tylko przeróbką pewnego systemu, który znalazłem w sieci.

Chcemy dokonać zakupu 5 przedmiotów. Oznaczmy je etykietami \(\displaystyle{ 0, 1, 2, 3, 4}\). Każdy z przedmiotów można kupić bądź sprzedać za darmo. Sprzedany przedmiot można ponownie zakupić (ceny nie odgrywają jednak w zagadce roli).

Oto zasady zakupów:

• Przedmiot \(\displaystyle{ n}\) można kupić bądź sprzedać tylko wtedy, gdy z przedmiotów o niższej etykiecie posiadamy wyłącznie przedmiot \(\displaystyle{ n-1}\).
  Przedmiot \(\displaystyle{ 0}\) można kupić bądź sprzedać w dowolnej chwili, gdyż pod nim nie ma żadnych innych przedmiotów.

Przykład. Mamy przedmioty \(\displaystyle{ 1, 3}\). Nie możemy kupić \(\displaystyle{ 4}\) gdyż posiadamy \(\displaystyle{ 1}\). Nie możemy sprzedać \(\displaystyle{ 1}\) gdyż nie posiadamy \(\displaystyle{ 0}\). Możemy kupić \(\displaystyle{ 2}\) gdyż posiadamy \(\displaystyle{ 1}\), ale nie posiadamy \(\displaystyle{ 0}\).

Zagadka polega na znalezieniu i wypisaniu najkrótszej drogi zakupów/sprzedaży, która pozwoli zaopatrzyć się we wszystkie przedmioty.

Sugeruję rozwiązania umieszczać w tagach [hide] [/hide] by nie psuć innym zabawy
Edycja - poprawa treści.

Zasady co nieco sprzeczne !
jaka jest zależność między "oddać za darmo" a "bądź sprzedać" .
Posiadanie "wyłącznie" przedmiotu \(\displaystyle{ n-1}\) nie pozwala dokupić innych przedmiotów poza \(\displaystyle{ n}\).

jacdiag pisze:Zasady conieco sprzeczne !

Nie wydaje mi się (ale przeczytam je raz jeszcze i jeżeli coś będzie źle, to poprawię).

jacdiag pisze: jaka jest zależność między "oddać za darmo" a "bądź sprzedać" .

Dzięki za zwrócenie uwagi. Nie ma już "oddać za darmo", jest tylko sprzedać.


Edycja:

jacdiag pisze: Posiadanie "wyłącznie" przedmiotu n-1 nie pozwala dokupić innych przedmiotów poza n.

To była nieścisłość. Dzięki za wyłapanie jej. Łatwiej zdecydowanie jest operować według zasad niż je odpowiednio zapisać.

Dasio11 pisze:

Odpowiedź:    

Kod Graya?