Prostokąty w kwadracie

[mol_ksiazkowy]

Czy istnieje najmniejszy kwadrat w którym można zmieścić wszystkie prostokąty o bokach \(\displaystyle{ \frac{1}{n}}\) i \(\displaystyle{ \frac{1}{n+1}}\) dla \(\displaystyle{ n=1, 2, 3, ...}\) ?
Nie mogą one zachodzić na siebie, a jedynie stykać się bokiem bądź wierzchołkiem.

[kruszewski]

Mam wrażenie, że nie uda się znaleźć takiego dokładnike wypełnionego kwadratu.
Problem nazwany plecakowym, a ciekawy rozdział-artykuł o upakowaniu można znaleźć w:
Matematyka współczesna - 12 esejów
Lynn Arthur Steen
część III
- Ronald L. Graham: Kombinatoryczna teoria szeregowania (przeł. Jerzy Kucharczyk)
(Miałem, pożyczyłem, przepadła)

Z recenzji tej książki napisanej przez Jędrka pomieszczonej w: ... -12-esejow

"Profesor Jan Węglarz z Politechniki Poznańskiej jest uważany za twórcę polskiej szkoły szeregowania..."

[kerajs]

Sądzę, że tu raczej chodzi o wykazanie czy istnieją takie \(\displaystyle{ n}\) , że wszystkich prostokątów nie da się upchać w kwadrat o boku \(\displaystyle{ 1}\) (wymiar tego kwadratu narzuca pierwszy prostokąt \(\displaystyle{ 1 \times \frac{1}{2}}\) ). Co prawda suma pól \(\displaystyle{ n}\) prostokątów wynosi \(\displaystyle{ 1- \frac{1}{n+1}}\) , jednak w praktyce może się okazać że upakowanie od pewnego \(\displaystyle{ n}\) nie będzie możliwe.

[Slup]

Niech \(\displaystyle{ \{R_k\}}\) będzie ciągiem prostokątów. Jeśli prostokąty \(\displaystyle{ \{R_k\}}\) są zawarte w kwadracie \(\displaystyle{ S}\) tak, że żadne dwa z nich nie mają przecinających się wnętrz, to powiemy, że ich rozmieszczenie w kwadracie \(\displaystyle{ S}\) jest dobre.

Fakt.
Załóżmy, że prostokąty \(\displaystyle{ \{R_k\}}\) dają się rozmieścić dobrze w pewnym kwadracie. Wówczas istnieje najmniejszy kwadrat, w którym te prostokąty dają się dobrze rozmieścić.
dowód (szkic).
Oznaczmy wierzchołki \(\displaystyle{ R_k = A_kB_kC_kD_k}\) dla wszystkich \(\displaystyle{ k}\).
Niech \(\displaystyle{ a}\) będzie kresem dolnym długości boków kwadratów takich, że można w nich rozmieścić dobrze te prostokąty. Istnieje wówczas ciąg liczbowy \(\displaystyle{ \{a_n\}}\), który jest malejący i o wyrazach większych od \(\displaystyle{ a}\) taki, że dla każdego \(\displaystyle{ n}\) w kwadracie \(\displaystyle{ S_n}\) o boku długości \(\displaystyle{ a_n}\) można dobrze rozmieścić prostokąty \(\displaystyle{ \{R_k\}}\). Umieśćmy kwadraty \(\displaystyle{ S_1}\),...,\(\displaystyle{ S_n}\),... w taki sposób, że

\(\displaystyle{ S_{n+1}\subseteq S_n\subseteq S_1}\)

dla każdego \(\displaystyle{ n}\). Dla ustalonego \(\displaystyle{ n}\) niech \(\displaystyle{ \{R_{n,k}\}}\) zadane przez \(\displaystyle{ R_{n,k} = A_{n,k}B_{n,k}C_{n,k}D_{n,k}}\) będzie dobrym rozmieszczeniem prostokątów \(\displaystyle{ \{R_k\}}\) w kwadracie \(\displaystyle{ S_n}\). Umawiamy się, że przystawanie \(\displaystyle{ R_k}\) do \(\displaystyle{ R_{n,k}}\) jest zadane przez

\(\displaystyle{ A_k\mapsto A_{n,k},\,B_k\mapsto B_{n,k},\,C_k\mapsto C_{n,k},\,D_k\mapsto D_{n,k}}\)

Rozpatrzmy teraz przestrzeń topologiczną \(\displaystyle{ X}\), która jest przeliczalnym produktem kopii przestrzeni zwartej \(\displaystyle{ \underbrace{S_1\times S_1\times S_1\times S_1}_{4\,razy}}\). Z Twierdzenia Tichonowa przestrzeń \(\displaystyle{ X}\) jest zwarta. Stąd z ciągu \(\displaystyle{ \{P_n\}_{n\geq 1}}\) punktów przestrzeni \(\displaystyle{ X}\) danego przez

\(\displaystyle{ P_n = \big(\left(A_{n,k},B_{n,k},C_{n,k},D_{n,k}\right)\big)_{k\geq 1} \in \prod_{k\geq 1}\left(\underbrace{S_1\times S_1\times S_1\times S_1}_{4\,razy}\right) = X}\)

można wybrać podciąg zbieżny. Bez zmniejszania ogólności można przyjąć, że już sam ciąg \(\displaystyle{ P_n}\) jest zbieżny. Zbieżność w produkcie to zbieżność po współrzędnych. Zatem dla każdego \(\displaystyle{ k}\) istnieją granice

\(\displaystyle{ \tilde{A}_k = \lim_{n\rightarrow +\infty} A_{n,k},\,\tilde{B}_k = \lim_{n\rightarrow +\infty} B_{n,k},\,\tilde{C}_k = \lim_{n\rightarrow +\infty} C_{n,k},\,\tilde{D}_k = \lim_{n\rightarrow +\infty} D_{n,k}}\)

w kwadracie \(\displaystyle{ S_1}\). Dalsza część będzie trochę szkicowa. Skoro prostokąt \(\displaystyle{ A_{n,k}B_{n,k}C_{n,k}D_{n,k}}\) jest przystający do \(\displaystyle{ R_k = A_kb_kC_kD_k}\) dla każdego \(\displaystyle{ n}\), to granica \(\displaystyle{ \tilde{A}_k\tilde{B}_k\tilde{C}_k\tilde{D}_k}\) jest prostokątem \(\displaystyle{ \tilde{R}_k}\) przystającym do \(\displaystyle{ R_k}\). Z faktu, że

\(\displaystyle{ A_{m,k},\,B_{m,k},\,C_{m,k},\,D_{m,k}\in S_{n}}\)

dla \(\displaystyle{ m\geq n}\) wynika, że

\(\displaystyle{ \tilde{A}_k,\,\tilde{B}_k,\,\tilde{C}_k,\,\tilde{D}_k \in \bigcap_{n\geq 1}S_n}\)

Ponadto prostokąty \(\displaystyle{ A_{n,k}B_{n,k}C_{n,k}D_{n,k}}\) oraz \(\displaystyle{ A_{n,l}B_{n,l}C_{n,l}D_{n,l}}\) nie mają wspólnych punktów wewnętrznych dla \(\displaystyle{ k\neq l}\), a więc graniczne prostokąty \(\displaystyle{ \tilde{A}_k\tilde{B}_k\tilde{C}_k\tilde{D}_k}\) oraz \(\displaystyle{ \tilde{A}_l\tilde{B}_l\tilde{C}_l\tilde{D}_l}\) nie mają wspólnych punktów wewnętrznych dla \(\displaystyle{ k\neq l}\). Stąd prostokąty \(\displaystyle{ \{\tilde{R}_k\}}\) tworzą dobre rozmieszczenie prostokątów \(\displaystyle{ \{R_k\}}\) w kwadracie

\(\displaystyle{ S = \bigcap_{n\geq 1} S_n}\)

który ma bok długości \(\displaystyle{ a}\).

Uwaga. Oczywiście ten Fakt da się uogólnić i zamiast prostokątów można wziąć zbiory regularne (czyli takie, które są domknięciami swoich wnętrz) oraz zwarte.

W każdym razie używając Faktu zadanie sprowadza się do alternatywy wykluczającej:

Istnieje najmniejszy kwadrat, w którym można dobrze umieścić prostokąty o bokach \(\displaystyle{ \frac{1}{n}}\) oraz \(\displaystyle{ \frac{1}{n+1}}\) dla \(\displaystyle{ n\geq 1}\) albo tego zbioru prostokątów nie da się umieścić w żadnym kwadracie.