28 Aralık 2018

Euler Projesi 256. Soru

Tatami-Serbest Odalar

Tatami, bir odanın tabanını üst üste geçmeyerek tamamen kapatmak üzere kullanılan dikdörtgen hasırlardır.

Tek olası tatami boyutunun 1x2 olduğu düşünülürse kaplanacak olan odanın şekli ve boyutunda bazı kısıtlamalar olacaktır.

Bu problem için sadece a, b ve çift s=a.b tam sayı boyutlu dikdörtgen odalar düşünülecek.
"Boyut" kavramı ile odanın taban alanı kastediliyor ve -genelliği bozmadan- $a\le b$ koşulu veriliyor.

Tatami kaplarken izlenecek tek bir kural var: Dört farklı hasırın buluştuğu tek bir nokta bulunmamalı.
Örneğin 4x4 bir oda için aşağıdaki düzenleri ele alın:
Soldaki düzen kabul edilebilir ama sağdaki değil: x ile gösterilen nokta 4 tataminin buluştuğu bir nokta.

Bu kurala göre belli çift-boyutlu odalar tatami ile kaplanamaz: Bunlara tatami-serbest odalar diyoruz.
Ayrıca s boyutlu tatami-serbest odaların sayısını T(s) ile tanımlayalım.

En küçük tatami-serbest odanın boyutu s=70 ve boyut ölçüleri=7x10.
s=70 boyutlu tüm diğer odalar tatami ile kaplanabilir; bunlar 1x70, 2x35 ve 5x14.
Böylece T(70)=1 dir.

Benzer şekilde T(1320)=5 olduğu gösterilebilir, çünkü s=1320 boyutlu 5 adet tatami-serbest oda vardır: 20x66, 22x60, 24x55, 30x44 ve 33x40.
Aslında T(s)=5 olan s-boyutlu en küçük oda için s=1320 dir.

T(s)=200 olan s-boyutlu en küçük oda için s kaçtır?
Cevap: 85765680