Pokrycie szachownicy.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Pokrycie szachownicy.
Dla jakich naturalnych \(\displaystyle{ n}\) można szachownicę \(\displaystyle{ (4n+2) \times (4n+2)}\) w całości pokryć \(\displaystyle{ (2n+1)^2}\) kamieniami o wymiarach \(\displaystyle{ 4 \times 1}\) ?
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: Pokrycie szachownicy.
Rozpatrzmy rodzinę funkcji
\(\displaystyle{ f_{\alpha, \beta}(x,y) = \cos\left(2\pi\cdot x + \alpha\right)\cos\left(2\pi\cdot y + \beta\right)}\)
zależną od parametrów \(\displaystyle{ \alpha, \beta \in \mathbb{R}}\). Niech \(\displaystyle{ [a, b]\times [c, d]\subseteq \mathbb{R}^2}\) będzie prostokątem. Wówczas
\(\displaystyle{ I(\alpha, \beta) = \int_c^d\int_a^bf_{\alpha, \beta}(x, y)dxdy = \int_c^d\int_a^b\cos\left(2\pi \cdot x + \alpha\right)\cos\left(2\pi\cdot y + \beta\right)dxdy =}\)
\(\displaystyle{ = \bigg(\int_a^b\cos\left(2\pi \cdot x + \alpha\right)dx\bigg)\cdot \bigg(\int_c^d\cos\left(2\pi \cdot y + \beta\right)dy\bigg) =}\)
\(\displaystyle{ = \frac{1}{4\pi^2}\cdot \bigg(\sin\left(2\pi b + \alpha\right) - \sin\left(2\pi a + \alpha\right)\bigg)\cdot \bigg(\sin\left(2\pi d + \beta\right) - \sin\left(2\pi c + \beta\right)\bigg) =}\)
\(\displaystyle{ =\frac{1}{\pi^2}\cos\left(\pi(a + b) +\alpha\right)\sin\left(\pi( b - a)\right)\cos\left(\pi(c + d) +\alpha\right)\sin\left(\pi( d - c)\right)}\)
Zapiszmy
\(\displaystyle{ I_{a,b}(\alpha) = \cos\left( \pi(a + b) +\alpha\right)\sin\left( \pi( b - a)\right)}\)
oraz
\(\displaystyle{ I_{c,d}(\beta) = \cos\left( \pi(c + d) +\alpha\right)\sin\left( \pi( d - c)\right)}\)
Wówczas:
1. \(\displaystyle{ I_{a,b}(\alpha)=0}\) dla każdego \(\displaystyle{ \alpha \in \mathbb{R}}\) wtedy i tylko wtedy, gdy \(\displaystyle{ b-a\in \mathbb{Z}}\).
2. Analogicznie \(\displaystyle{ I_{c,d}(\beta)=0}\) dla każdego \(\displaystyle{ \beta\in \RR}\) wtedy i tylko wtedy, gdy \(\displaystyle{ d-c\in \mathbb{Z}}\).
3. Ponadto \(\displaystyle{ I(\alpha, \beta) = \frac{1}{\pi^2}\cdot I_{a,b}(\alpha)\cdot I_{c,d}(\beta)}\).
Stąd płynie następujący:
Wniosek.
Ustalmy prostokąt \(\displaystyle{ R = [a, b]\times [c, d]}\) zawarty w \(\displaystyle{ \mathbb{R}^2}\). Wówczas
\(\displaystyle{ \int_R f_{\alpha, \beta}(x , y)dxdy = 0}\)
dla wszystkich \(\displaystyle{ \alpha, \beta \in \mathbb{R}}\) wtedy i tylko wtedy, gdy \(\displaystyle{ b-a\in \mathbb{Z}}\) lub \(\displaystyle{ d-c\in \mathbb{Z}}\).
Niech teraz \(\displaystyle{ R}\) będzie dowolnym prostokątem o bokach równoległych od osi współrzędnych i załóżmy, że został on rozłożony na sumę rozłączną prostokątów \(\displaystyle{ \{R_n\}_{n\in \mathbb{N}}}\) o bokach równoległych do osi współrzędnych oraz takich, że dla każdego \(\displaystyle{ n}\) prostokąt \(\displaystyle{ R_n}\) ma bok o długości będącej liczbą całkowitą. Wówczas dla dowolnych \(\displaystyle{ \alpha, \beta\in \mathbb{R}}\) mamy
\(\displaystyle{ \int_Rf_{\alpha, \beta}(x,y)dxdy = \sum_{n=1}^{+\infty}\int_{R_i}f_{\alpha,\beta}(x,y)dxdy = 0}\)
na mocy twr. Lebesgue'a o zbieżności zmajoryzowanej. Zatem z Wniosku wynika, że \(\displaystyle{ R}\) ma jeden z boków o długości całkowitej.
W szczególności dla \(\displaystyle{ n\in \mathbb{N}}\) nie ma pokrycia szachownicy
\(\displaystyle{ \left(n+\frac{1}{2}\right)\times \left(n+\frac{1}{2}\right)}\)
prostokątami typu \(\displaystyle{ 1 \times \frac{1}{4}}\), co rozwiązuje problem kerajsa. Zresztą modyfikacja powyższego rozumowania pozwala pewnie rozwiązać większość problemów typu "pokrywamy szachownice prostokątami".
\(\displaystyle{ f_{\alpha, \beta}(x,y) = \cos\left(2\pi\cdot x + \alpha\right)\cos\left(2\pi\cdot y + \beta\right)}\)
zależną od parametrów \(\displaystyle{ \alpha, \beta \in \mathbb{R}}\). Niech \(\displaystyle{ [a, b]\times [c, d]\subseteq \mathbb{R}^2}\) będzie prostokątem. Wówczas
\(\displaystyle{ I(\alpha, \beta) = \int_c^d\int_a^bf_{\alpha, \beta}(x, y)dxdy = \int_c^d\int_a^b\cos\left(2\pi \cdot x + \alpha\right)\cos\left(2\pi\cdot y + \beta\right)dxdy =}\)
\(\displaystyle{ = \bigg(\int_a^b\cos\left(2\pi \cdot x + \alpha\right)dx\bigg)\cdot \bigg(\int_c^d\cos\left(2\pi \cdot y + \beta\right)dy\bigg) =}\)
\(\displaystyle{ = \frac{1}{4\pi^2}\cdot \bigg(\sin\left(2\pi b + \alpha\right) - \sin\left(2\pi a + \alpha\right)\bigg)\cdot \bigg(\sin\left(2\pi d + \beta\right) - \sin\left(2\pi c + \beta\right)\bigg) =}\)
\(\displaystyle{ =\frac{1}{\pi^2}\cos\left(\pi(a + b) +\alpha\right)\sin\left(\pi( b - a)\right)\cos\left(\pi(c + d) +\alpha\right)\sin\left(\pi( d - c)\right)}\)
Zapiszmy
\(\displaystyle{ I_{a,b}(\alpha) = \cos\left( \pi(a + b) +\alpha\right)\sin\left( \pi( b - a)\right)}\)
oraz
\(\displaystyle{ I_{c,d}(\beta) = \cos\left( \pi(c + d) +\alpha\right)\sin\left( \pi( d - c)\right)}\)
Wówczas:
1. \(\displaystyle{ I_{a,b}(\alpha)=0}\) dla każdego \(\displaystyle{ \alpha \in \mathbb{R}}\) wtedy i tylko wtedy, gdy \(\displaystyle{ b-a\in \mathbb{Z}}\).
2. Analogicznie \(\displaystyle{ I_{c,d}(\beta)=0}\) dla każdego \(\displaystyle{ \beta\in \RR}\) wtedy i tylko wtedy, gdy \(\displaystyle{ d-c\in \mathbb{Z}}\).
3. Ponadto \(\displaystyle{ I(\alpha, \beta) = \frac{1}{\pi^2}\cdot I_{a,b}(\alpha)\cdot I_{c,d}(\beta)}\).
Stąd płynie następujący:
Wniosek.
Ustalmy prostokąt \(\displaystyle{ R = [a, b]\times [c, d]}\) zawarty w \(\displaystyle{ \mathbb{R}^2}\). Wówczas
\(\displaystyle{ \int_R f_{\alpha, \beta}(x , y)dxdy = 0}\)
dla wszystkich \(\displaystyle{ \alpha, \beta \in \mathbb{R}}\) wtedy i tylko wtedy, gdy \(\displaystyle{ b-a\in \mathbb{Z}}\) lub \(\displaystyle{ d-c\in \mathbb{Z}}\).
Niech teraz \(\displaystyle{ R}\) będzie dowolnym prostokątem o bokach równoległych od osi współrzędnych i załóżmy, że został on rozłożony na sumę rozłączną prostokątów \(\displaystyle{ \{R_n\}_{n\in \mathbb{N}}}\) o bokach równoległych do osi współrzędnych oraz takich, że dla każdego \(\displaystyle{ n}\) prostokąt \(\displaystyle{ R_n}\) ma bok o długości będącej liczbą całkowitą. Wówczas dla dowolnych \(\displaystyle{ \alpha, \beta\in \mathbb{R}}\) mamy
\(\displaystyle{ \int_Rf_{\alpha, \beta}(x,y)dxdy = \sum_{n=1}^{+\infty}\int_{R_i}f_{\alpha,\beta}(x,y)dxdy = 0}\)
na mocy twr. Lebesgue'a o zbieżności zmajoryzowanej. Zatem z Wniosku wynika, że \(\displaystyle{ R}\) ma jeden z boków o długości całkowitej.
W szczególności dla \(\displaystyle{ n\in \mathbb{N}}\) nie ma pokrycia szachownicy
\(\displaystyle{ \left(n+\frac{1}{2}\right)\times \left(n+\frac{1}{2}\right)}\)
prostokątami typu \(\displaystyle{ 1 \times \frac{1}{4}}\), co rozwiązuje problem kerajsa. Zresztą modyfikacja powyższego rozumowania pozwala pewnie rozwiązać większość problemów typu "pokrywamy szachownice prostokątami".
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Pokrycie szachownicy.
O wiele prościej:
Rozważmy kwadratową szachownicę o boku \(\displaystyle{ 4n+2}\). Każde pole ma swoją parę współrzędnych \(\displaystyle{ (k, \ell) \in \{ 1, \ldots, 4n+2 \}^2}\). W pole o współrzędnych \(\displaystyle{ (k, \ell)}\) wpiszmy liczbę \(\displaystyle{ (k+\ell) \bmod{4}}\) ze zbioru \(\displaystyle{ \{ 0, 1, 2, 3 \}}\). Wtedy każdy prostokąt o wymiarach \(\displaystyle{ 4 \times 1}\) zawiera po jednej z każdej z tych liczb.
Łatwo przykryć część szachownicy kostkami \(\displaystyle{ 4 \times 1}\) tak, by pozostał kwadrat wielkości \(\displaystyle{ 2 \times 2}\) odpowiadający współrzędnym \(\displaystyle{ \{ 1, 2 \}^2}\). W takim kwadracie są dwie trójki i żadnej jedynki, a ponieważ przykrywanie części szachownicy kostkami \(\displaystyle{ 4 \times 1}\) nie zmienia bilansu, zatem na pełnej szachownicy również musi być więcej trójek niż jedynek.
Gdyby jednak szachownicę dało się przykryć takimi kostkami, to trójek musiałoby być tyle samo co jedynek, a więc takie przykrycie jest niemożliwe.
Rozważmy kwadratową szachownicę o boku \(\displaystyle{ 4n+2}\). Każde pole ma swoją parę współrzędnych \(\displaystyle{ (k, \ell) \in \{ 1, \ldots, 4n+2 \}^2}\). W pole o współrzędnych \(\displaystyle{ (k, \ell)}\) wpiszmy liczbę \(\displaystyle{ (k+\ell) \bmod{4}}\) ze zbioru \(\displaystyle{ \{ 0, 1, 2, 3 \}}\). Wtedy każdy prostokąt o wymiarach \(\displaystyle{ 4 \times 1}\) zawiera po jednej z każdej z tych liczb.
Łatwo przykryć część szachownicy kostkami \(\displaystyle{ 4 \times 1}\) tak, by pozostał kwadrat wielkości \(\displaystyle{ 2 \times 2}\) odpowiadający współrzędnym \(\displaystyle{ \{ 1, 2 \}^2}\). W takim kwadracie są dwie trójki i żadnej jedynki, a ponieważ przykrywanie części szachownicy kostkami \(\displaystyle{ 4 \times 1}\) nie zmienia bilansu, zatem na pełnej szachownicy również musi być więcej trójek niż jedynek.
Gdyby jednak szachownicę dało się przykryć takimi kostkami, to trójek musiałoby być tyle samo co jedynek, a więc takie przykrycie jest niemożliwe.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Pokrycie szachownicy.
Albo zamiast numerować pola można szachownicę pomalować (jej kolejne skośne) czterema kolorami. Okaże się że pól w kolorze przekątnej jest o jedno więcej niż w skośnych do tej przekątnej przylegających, i o dwa więcej niż w czwartym kolorze.
Może teraz będzie łatwiej rozwiązać 442143.htm ?
Może teraz będzie łatwiej rozwiązać 442143.htm ?
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: Pokrycie szachownicy.
Przepraszam, ale podam jeszcze jedno rozwiązanie.
Szachownicę \(\displaystyle{ S}\) o rozmiarach \(\displaystyle{ (4n + 2)\times (4n + 2)}\) pokrywamy kwadratami o wymiarach \(\displaystyle{ 2\times 2}\). Tych kwadratów jest \(\displaystyle{ (2n + 1)^2}\). Kwadraty malujemy naprzemiennie (jak to na szachownicy) na czarno i biało. Wówczas
\(\displaystyle{ \mbox{pole białego obszaru }S - \mbox{pole czarnego obszaru }S\neq 0}\)
co wynika stąd, że kwadratów \(\displaystyle{ 2\times 2}\) jest nieparzyście wiele. Z drugiej strony jeśli mamy kamień \(\displaystyle{ R}\) o rozmiarach \(\displaystyle{ 4\times 1}\) rozmieszczony na szachownicy, to
\(\displaystyle{ \mbox{pole białego obszaru }R - \mbox{pole czarnego obszaru }R = 0}\)
Stąd podane pokrycie nie istnieje.
Czy zadanie 442143.htm ma zgrabne rozwiązanie?
Szachownicę \(\displaystyle{ S}\) o rozmiarach \(\displaystyle{ (4n + 2)\times (4n + 2)}\) pokrywamy kwadratami o wymiarach \(\displaystyle{ 2\times 2}\). Tych kwadratów jest \(\displaystyle{ (2n + 1)^2}\). Kwadraty malujemy naprzemiennie (jak to na szachownicy) na czarno i biało. Wówczas
\(\displaystyle{ \mbox{pole białego obszaru }S - \mbox{pole czarnego obszaru }S\neq 0}\)
co wynika stąd, że kwadratów \(\displaystyle{ 2\times 2}\) jest nieparzyście wiele. Z drugiej strony jeśli mamy kamień \(\displaystyle{ R}\) o rozmiarach \(\displaystyle{ 4\times 1}\) rozmieszczony na szachownicy, to
\(\displaystyle{ \mbox{pole białego obszaru }R - \mbox{pole czarnego obszaru }R = 0}\)
Stąd podane pokrycie nie istnieje.
Czy zadanie 442143.htm ma zgrabne rozwiązanie?
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Pokrycie szachownicy.
Nie wiem.
Było ono (podobnie jak problemiki geometryczne: https://www.matematyka.pl/viewtopic.php?f=54&t=442179, https://www.matematyka.pl/viewtopic.php?f=110&t=441897 i https://www.matematyka.pl/viewtopic.php?f=110&t=441842 ) pomyślane jako łamigłówka na wakacyjną nudę, ale najwidoczniej forumowicze mieli ciekawsze zajęcia.
Przepraszam za tak późną odpowiedź, ale dopiero dzisiaj się zorientowałem iż dopisałeś kolejny post w tym temacie.