Czy w kostce \(\displaystyle{ [0,1]^4}\) możemy zmieścić \(\displaystyle{ 18}\) punktów, tak żeby odległość między każdymi dwoma była przynajmniej \(\displaystyle{ 1}\)?
W przypadkach wymiarów \(\displaystyle{ n\leqslant 3}\) optymalną odpowiedzią jest \(\displaystyle{ 2^{n}}\).
Przypomniała mi się ta obserwacja, i nie wiem jak to jest w większej liczbie wymiarów.
Oczywiście, dla \(\displaystyle{ n=4}\), da się \(\displaystyle{ 17}\) punktów.
ile punktów mieści się w kostce
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
ile punktów mieści się w kostce
Od kilku dni usiłuję zliczać punkty kratowe w sympleksach (zaraz wkleję jakieś zadanie wynikające z tych poszukiwań) i zagadnienie pakowania punktów w kostkach kilka razy zaplątało się w rezultatach wyszukiwania: . Autorzy twierdzą, póki co można tylko 17. Do rozważań używają metryki Hamminga, która przypomina metrykę w sympleksach dla mnie nieco przydatniejszą.
-
Maciej87
- Użytkownik
- Posty: 377
- Rejestracja: 26 sty 2009, o 09:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
ile punktów mieści się w kostce
Publikacja z Twojego postu zawiera bardzo ciekawe odnośniki.
Oszacowania można uzyskać całkiem elementarnymi i eleganckimi sposobami.
Choć to będzie mocno odległe od optymalnej wartości i może trywialne, to zamieszczę to z uwagi na sam pomysł.
Dla krótkości oznaczymy badaną własność przez gwiazdkę
\(\displaystyle{ \star}\) Każde dwa punkty zbioru są odległe o przynajmniej \(\displaystyle{ 1}\)
Mamy
Lemat 1
Załóżmy, że pudełko wielowymiarowe zawiera \(\displaystyle{ 3}\) punkty o własności \(\displaystyle{ \star}\).
Wtedy jego wymiary \(\displaystyle{ w_i}\) spełniają własność
\(\displaystyle{ \sum\limits_{i=1}^{n}w_i^{2} \geqslant \frac{3}{2}}\)
Dowód
Dla liczb \(\displaystyle{ 0\leqslant x \leqslant y \leqslant z \leqslant w}\) mamy
\(\displaystyle{ (x-y)^2+(x-z)^2+(y-z)^2 \leqslant (0-y)^2+(0-z)^2+(y-z)^2 = z^2 + y^2+(y-z)^2 \leqslant 2z^2 \leqslant 2w^2}\).
Ważne jest oczywiście ograniczenie liczb \(\displaystyle{ x,y,z}\) a nie porządek.
Oznaczmy nasze punkty przez \(\displaystyle{ a,b,c}\). Rozpisując wszystkie odległości mamy
\(\displaystyle{ 3 \leqslant (a-b)^2+(a-c)^2+(b-c)^2}\) i aplikujemy poprzednią nierówność do każdej ze współrzędnych. \(\displaystyle{ \blacksquare}\)
Lemat 2
Załóżmy, że pudełko wielowymiarowe zawiera \(\displaystyle{ 4}\) punkty o własności \(\displaystyle{ \star}\).
Wtedy jego wymiary \(\displaystyle{ w_i}\) spełniają własność
\(\displaystyle{ \sum\limits_{i=1}^{n}w_i^{2} \geqslant \frac{3}{2}}\)
Dowód
Podobnie. \(\displaystyle{ \blacksquare}\)
Lemat 3
Załóżmy, że pudełko wielowymiarowe zawiera \(\displaystyle{ 5}\) punkty o własności \(\displaystyle{ \star}\).
Wtedy jego wymiary \(\displaystyle{ w_i}\) spełniają własność
\(\displaystyle{ \sum\limits_{i=1}^{n}w_i^{2} \geqslant \frac{5}{3}}\)
Podzielmy teraz kostkę \(\displaystyle{ [0,1]^4}\) na \(\displaystyle{ 2\cdot3\cdot 3=18}\) części, tak że każda jest pudełkiem o wymiarach \(\displaystyle{ \left(1,\frac{1}{2},\frac{1}{3},\frac{1}{3} \right)}\).
Suma kwadratów tych krawędzi jest mniejsza niż \(\displaystyle{ \frac{3}{2}}\), zatem- korzystając z lematu pierwszego- nasza kostka zawiera co najwyżej \(\displaystyle{ 2\cdot 18 = 36}\) punktów o własności \(\displaystyle{ \star}\).
Ta metoda- rozwijanie różnych wersji podobnych lematów i wykorzystywanie zasady szufladkowej jest niestety kiepska dla małych liczb- np. jak chcemy zbliżyć się do \(\displaystyle{ 17}\). Choćby same "teorioliczbowe" ograniczenia- wykonujemy podział i obracamy się wśród liczb o dużej ilości dzielników.
I pytanie, czy próbować robić drobniejszy podział- wtedy dostawać odpowiedniki lematów z małą liczbą punktów- czy grubszy, kiedy punktów będzie więcej, za to pudełek mniej.
W tych oszacowaniach zależy oczywiście na najwyższej stałej, czyli jak największej sumie kwadratów krawędzi- pozwala to użyć grubszego podziału.
I uwaga: To co tutaj napisałem, jest naprawdę kiepskie, bo przypuszcza się że dla \(\displaystyle{ 5}\) wymiarowej kostki optymalna ilość punktów to \(\displaystyle{ 34}\)
Natomiast z prac wynika, że sam pomysł nie jest głupi, i podobne lematy są stosowane żeby dojść do bardziej nietrywialnych wyników
Oszacowania można uzyskać całkiem elementarnymi i eleganckimi sposobami.
Choć to będzie mocno odległe od optymalnej wartości i może trywialne, to zamieszczę to z uwagi na sam pomysł.
Dla krótkości oznaczymy badaną własność przez gwiazdkę
\(\displaystyle{ \star}\) Każde dwa punkty zbioru są odległe o przynajmniej \(\displaystyle{ 1}\)
Mamy
Lemat 1
Załóżmy, że pudełko wielowymiarowe zawiera \(\displaystyle{ 3}\) punkty o własności \(\displaystyle{ \star}\).
Wtedy jego wymiary \(\displaystyle{ w_i}\) spełniają własność
\(\displaystyle{ \sum\limits_{i=1}^{n}w_i^{2} \geqslant \frac{3}{2}}\)
Dowód
Dla liczb \(\displaystyle{ 0\leqslant x \leqslant y \leqslant z \leqslant w}\) mamy
\(\displaystyle{ (x-y)^2+(x-z)^2+(y-z)^2 \leqslant (0-y)^2+(0-z)^2+(y-z)^2 = z^2 + y^2+(y-z)^2 \leqslant 2z^2 \leqslant 2w^2}\).
Ważne jest oczywiście ograniczenie liczb \(\displaystyle{ x,y,z}\) a nie porządek.
Oznaczmy nasze punkty przez \(\displaystyle{ a,b,c}\). Rozpisując wszystkie odległości mamy
\(\displaystyle{ 3 \leqslant (a-b)^2+(a-c)^2+(b-c)^2}\) i aplikujemy poprzednią nierówność do każdej ze współrzędnych. \(\displaystyle{ \blacksquare}\)
Lemat 2
Załóżmy, że pudełko wielowymiarowe zawiera \(\displaystyle{ 4}\) punkty o własności \(\displaystyle{ \star}\).
Wtedy jego wymiary \(\displaystyle{ w_i}\) spełniają własność
\(\displaystyle{ \sum\limits_{i=1}^{n}w_i^{2} \geqslant \frac{3}{2}}\)
Dowód
Podobnie. \(\displaystyle{ \blacksquare}\)
Lemat 3
Załóżmy, że pudełko wielowymiarowe zawiera \(\displaystyle{ 5}\) punkty o własności \(\displaystyle{ \star}\).
Wtedy jego wymiary \(\displaystyle{ w_i}\) spełniają własność
\(\displaystyle{ \sum\limits_{i=1}^{n}w_i^{2} \geqslant \frac{5}{3}}\)
Podzielmy teraz kostkę \(\displaystyle{ [0,1]^4}\) na \(\displaystyle{ 2\cdot3\cdot 3=18}\) części, tak że każda jest pudełkiem o wymiarach \(\displaystyle{ \left(1,\frac{1}{2},\frac{1}{3},\frac{1}{3} \right)}\).
Suma kwadratów tych krawędzi jest mniejsza niż \(\displaystyle{ \frac{3}{2}}\), zatem- korzystając z lematu pierwszego- nasza kostka zawiera co najwyżej \(\displaystyle{ 2\cdot 18 = 36}\) punktów o własności \(\displaystyle{ \star}\).
Ta metoda- rozwijanie różnych wersji podobnych lematów i wykorzystywanie zasady szufladkowej jest niestety kiepska dla małych liczb- np. jak chcemy zbliżyć się do \(\displaystyle{ 17}\). Choćby same "teorioliczbowe" ograniczenia- wykonujemy podział i obracamy się wśród liczb o dużej ilości dzielników.
I pytanie, czy próbować robić drobniejszy podział- wtedy dostawać odpowiedniki lematów z małą liczbą punktów- czy grubszy, kiedy punktów będzie więcej, za to pudełek mniej.
W tych oszacowaniach zależy oczywiście na najwyższej stałej, czyli jak największej sumie kwadratów krawędzi- pozwala to użyć grubszego podziału.
I uwaga: To co tutaj napisałem, jest naprawdę kiepskie, bo przypuszcza się że dla \(\displaystyle{ 5}\) wymiarowej kostki optymalna ilość punktów to \(\displaystyle{ 34}\)
Natomiast z prac wynika, że sam pomysł nie jest głupi, i podobne lematy są stosowane żeby dojść do bardziej nietrywialnych wyników