En shejk har ett slott som ser ut som en 6×6-kvadrat indelad i 1×1-rum. I mitten av varje vägg finns en dörr mellan rummen. Shejken ger order till hovbyggaren att ta bort några väggar, så att det bara bildas rum av storleken 2×1, inga nya dörrar tillkommer och att man som mest ska behöva gå genom N dörrar för att gå från ett rum till ett annat.
Vilket är det minsta möjliga värdet på N så att alla shejkens önskemål fortfarande går att uppfylla?
Ett möjligt värde på N är 5, då kan hovbyggaren uppfylla önskemålen som på bilden nedan. Till nåt av rummet i mittenkvadraten kan man alltid ta sig på två steg, så mellan vilka som helst två rum kan man gå på 2+1+2 steg (ett steg för att eventuellt gå emellan mittenrummen).
Varför kan inte N vara lika med 4 eller mindre? Låt oss se hur många steg som krävs för att ta sig från ett hörn till det motsatta med hjälp av 2×1-rum. Man behöver totalt ta sig t.ex. 5 steg uppåt och 5 åt höger, vilket är 10 steg totalt. Varje 2×1-rum gör max 1 sådant steg ”gratis” (då en dörr inuti rummet försvinner).
Men om man går igenom 4 dörrar eller färre betyder det att man rör sig genom 5 rum eller färre. Det innebär att man gör som mest 4 vanliga steg (genom dörrar) plus 5 gratissteg (inuti rummen), vilket som mest är 9 steg. På inget vis kan man alltså ta sig från ett hörn till motsatt på 4 eller färre dörrar.
