Informacje dla kandydatów

Bardzo trudne zadanie

Niech \(n \ge 1\) będzie liczbą całkowitą. Napisz program, który odpowiada na następujące pytanie:

Czy istnieje prostokąt, który można podzielić na \(n\) różnych kwadratów?



Dla \(n=1\) rozwiązanie jest trywialne gdyż każdy kwadrat spełnia warunek zadania.

Dla \(n = 2, 3, 4, 5, 6, 7, 8\) nie istnieje taki prostokąt. Dopiero dla \(n=9\) istnieje prostokąt np. taki jak poniższy:

kwadraty

Uwaga: całkiem zgrabny program rozwiązujący powyższe zadanie (32 linijki kodu) można napisać w języku programowania Prolog z wykorzystaniem technologii więzów. Program taki nie tylko odpowiada czy istnieje prostokąt ale podaje również jego wymiary i długości boków \(n\) kwadratów.