Strona główna » Algorytmy » Testament Farmera
 

Testament Farmera

Zagadka

Pewien farmer miał 9 ha ziemi w kształcie kwadratu, którą chciał podzielić pomiędzy bliźniaczki i młodszą córkę, aby starsze dostały taką samą część, a młodsza mniejszy jej kawałek. Jak może dokonać podziału pod warunkiem, że fragmenty działek każdej z sióstr powinny móc utworzyć kwadrat? Ile jest różnych sposobów podziału ziemi?

Rozwiązanie

Odpowiedź

Oto wszystkie trzy możliwości podziału działki:

Przykład 1
Przykład 2
Przykład 3

Niezależnie od podziału działek pewne jest, że bliźniaczki dostają po 4 ha (zaznaczone kolorem niebieskim), a najmłodsza córka tylko 1 ha.

Wyjaśnienie

Przyjmijmy, że najmłodsza córka dostaje x ha. Wiadomo, że działka ma 9 ha, więc x musi być liczbą nieparzystą, ponieważ pozostałą część działki należy równo podzielić pomiędzy bliźniaczki. Dla x = 1 ha podział jest możliwy, ponieważ starsze siostry dostaną po 4 ha. Kolejną wartością możliwą dla x jset 3. Tu jednak pojawia się wynik, że bliźniaczki dostaną wtedy po 3 ha. Oznacza to, że każda siostra dostanie po tyle samo co przeczy woli farmera, aby młodsza córka dostała najmniej. Każda kolejna wartość x powoduje, że bliźniaczki dostaną po coraz mniejszym kawałku ziemi, więc nie istnieje inny podział niż na 4 ha, 4 ha i 1 ha.

Po podziale działek wszystkie fragmenty należące do danej siostry powinny móc utworzyć kwadrat. Jedna z bliźniaczek powinna dostać kwadrat 2×2, a najmłodsza 1×1. Wtedy gwarantowane jest, że obie mają działki w kształcie kwadratów (bez dodatkowego przemieszczania działek na mapie). Z kolei ostatnia siostra dostaje pozostałe 4 ha, które mogą utworzyć kwadrat identyczny jak ma pierwsza bliźniaczka.