Pengepakan dalam domain seragam
Diberikan $N$ poin $X:=(x_i)_{i \in \{1,..,N\}}$, sekarang kita mendefinisikan fungsi skor $S:X \rightarrow \mathbb{N}$ itu adalah $S(X)= \sum_{i=1}^N S(x_i)$ dimana skornya $S(x_i)$ adalah
$$S(x_i) = 2* \vert \{x_j; \vert x_i-x_j \vert \in [1,2]\} \vert+ \vert \{x_j; \vert x_i-x_j \vert \in [2,3]\} \vert$$ dimana $\vert \bullet \vert$menunjukkan kardinalitas himpunan. Selain itu, kami membutuhkan itu untuk semua$i\neq j$ kita punya $\vert x_i-x_j \vert \ge \frac{1}{2}.$
Pertanyaan: Apakah benar bahwa konfigurasi $N$ poin dengan skor semaksimal mungkin ada dalam domain diameter $c\sqrt{N}$ untuk beberapa c tetap?
Jawaban
Berikut di bawah ini adalah jawaban baru untuk pertanyaan yang dimodifikasi, yang kami asumsikan sebagai tambahan $|x_i-x_j|\ge 1$ (mungkin orang bisa bertanya $|x_i-x_j|\ge 1-\varepsilon$ cukup kecil $\varepsilon$). Saya ingin mengusulkan solusi positif dari masalah ini modulo tebakan berikut, yang, saya harap, benar.
Tebak. Pertimbangkan kisi segitiga sama sisi$E$ dengan jarak $1$di antara titik-titik yang bertetangga. Lalu ada tepatnya$18$ poin pada jarak paling banyak $2$ dari yang diberikan, dan $36$ pada jarak paling jauh $3$. Jadi skor setiap poin adalah$54=2*18+(36-18)$. Saya kira, itu untuk set apa pun$X$ sedemikian rupa sehingga setidaknya dua titik berada pada jarak $1$, di tertusuk $2$-sekitar dari titik mana pun $x\in X$ ada paling banyak $18$ poin dari $X$. Saya kira hal yang sama berlaku untuk poin jarak paling banyak$3$. Jika ini benar maka kita memiliki konsekuensi berikut: untuk set apa pun$X$ memuaskan $|x_i-x_j|\ge 1$ kita punya $S(x_i)\le 54 $.
Jadi mulai sekarang kami berasumsi bahwa tebakannya benar, atau kami bekerja dengan satu set$X$ sedemikian rupa sehingga setiap poin dari set ini memiliki skor paling banyak $54$.
Saya akan membuktikan bahwa dalam kondisi seperti itu konstanta $c$ ada.
Bukti. Perhatikan pertama-tama bahwa kita selalu dapat membuat satu set$X$ dengan $N$ poin, sehingga skor $X$ adalah $54N-10^{10}\sqrt{N}$. Himpunan seperti itu dapat diberikan dengan cara berpotongan$E$dengan cakram dengan radius yang sesuai. (seseorang dapat mengambil konstanta yang lebih kecil dari$10^{10}$, tapi tidak masalah).
Asumsikan dengan kontradiksi, bahwa kami membangun satu set $X$ memaksimalkan skor sehingga diameternya lebih dari $10^{10^{10}}\sqrt{N}$. Ambil gabungan cakram radius$3$ di sekitar semua poin $X$, dan menunjukkan set ini dengan $U_3$. Sangat mudah untuk melihatnya$U_3$terhubung. Memang, jika tidak, kita dapat menerjemahkan secara paralel komponen yang terhubung dengan mendorong satu sama lain dan meningkatkan skor dengan cara ini$X$. Jadi, karena diameternya$X$ setidaknya $10^{10^{10}}\sqrt{N}$, keliling dari batas luar $U_3$ setidaknya $10^{10^{10}}\sqrt{N}$. Kami akan mengatakan itu sebagai poin$X$ berkontribusi pada batas luar $U_3$ jika jarak $3$dari itu. Sangat mudah untuk melihat bahwa jumlah poin$X$ berkontribusi pada batas luar setidaknya $10^{(10^{10}-2)}\sqrt{N}$ (karena panjang jari-jari $3$ lingkaran adalah $<100$). Pengamatan terakhir adalah titik mana pun$x$ dari $X$ yang berkontribusi pada batas memiliki skor kurang dari $54$. Ini karena radius cakram$3$ sekitar $x$ memiliki sub-wilayah yang besar, di mana titik-titik $X$ tidak bisa berbohong (memang, ambil satu poin $y\in \partial U_3$ di kejauhan $3$ dari $x$, maka tidak ada gunanya jarak kurang dari $3$ dari $y$ terletak di $X$). Akhirnya, dengan mempertimbangkan tebakan dan fakta bahwa skor$X$ setidaknya harus $54N-10^{10}\sqrt{N}$, kami mendapatkan kontradiksi.
Jawaban lama
Mari pertimbangkan dua variasi dari pertanyaan ini. Dalam kedua kasus, jawabannya adalah ya. Dalam kasus pertama$X$ adalah bagian mana pun dari $\mathbb R^2$ di bagian kedua, ini adalah bagian dari $\mathbb Z^2$.
1 Kami berasumsi pertama itu$X$ adalah bagian mana pun dari $\mathbb R^2$. Dalam kasus seperti itu, set dengan skor semaksimal mungkin memiliki diameter paling banyak$6$. Biar saya buktikan. Mari kita pertama membangun satu set dengan skor secara aproksimasi$\frac{5}{3}N^2$. Untuk melakukan ini kami menempatkan$N/6$ menunjuk pada setiap simpul dari segi enam beraturan dengan panjang sisi $1$.
Sekarang, misalkan kita memiliki himpunan dengan skor maksimal dan anggap diameternya lebih dari $6$. Kami akan membangun satu set dengan skor lebih besar yang akan memberi kami kontradiksi.
Jadi, misalkan $X$ memiliki dua poin $x_i, x_j$ seperti yang $|x_i-x_j|>6$. Mari kita ambil radius dua cakram$3$di sekitar kedua titik. Salah satunya berisi paling banyak$N/2$ poin, yang artinya $S(x_i)$ atau $S(x_j)$ paling banyak $N$. Tanpa kehilangan asumsi umum$S(x_i)\le N$. Di sisi lain, kami tahu itu$S(X)\ge \frac{5 N^2}{3}$. Jadi, ada benarnya$x_k$ seperti yang $S(x_k)\ge\frac{5}{3}N$. Pindah$x_i$ di tempat $x_k$, ini akan meningkatkan skor $S(X)$. Kontradiksi.
2 Berikut ini hanyalah sketsa bukti. Kami berasumsi$X\subset \mathbb Z^2$. Dalam kasus seperti itu setiap poin$x_i$ berkontribusi paling banyak $2*8+20=36$ ke jumlah $S(X)$. Memang ada$8$ poin integer paling banyak pada jarak $2$ dari yang diberikan, dan $20$ pada jarak masuk $[2,3]$. Dari sini orang dapat menyimpulkan jawaban dengan menerapkan ketidaksamaan isomperietrik ke himpunan yang merupakan penyatuan$2\times 2$ kotak dengan pusat di titik $X$. Saya dapat memberikan detail lebih lanjut, jika Anda mau.