IMC 2001/2/3

#1

Να βρεθεί ο μέγιστος αριθμός σημείων που μπορούν να τοποθετηθούν σε μια σφαίρα στο $\mathbb{R}^n$ ακτίνας

ώστε η απόσταση μετάξυ κάθε δύο σημείων να είναι αυστηρά μεγαλύτερη του $\sqrt{2}$ .

#2

Θα δείξω επαγωγικά ότι έχουμε το πολύ n+1

σημεία.

Αυτό είναι προφανές για n=1

αφού $\sqrt{2} > 1$ .

Έστω $x_1,\ldots,x_k$ τα σημεία και έστω $\mathbf{x}_1,\ldots,\mathbf{x}_k$ τα αντίστοιχα διανύσματα. Για $1 \leqslant i \leqslant k-1$ ορίζω

$\displaystyle{ \mathbf{y}_i = \mathbf{x}_i - (\mathbf{x_i}\cdot \mathbf{x}_k) \mathbf{x}_k}$ και $\displaystyle{ \hat{\mathbf{y}_i} = \frac{\mathbf{y}_i}{\mathbf{y}_i \cdot \mathbf{y}_i}}$

[Δηλαδή τα $\mathbf{y}_i$ είναι οι προβολές των $\mathbf{x}_i$ στο $\mathbf{x}_k$ .]

Αλγεβρικά είναι $\mathbf{y}_i \cdot \mathbf{x}_k = 0$ . Επίσης είναι $\mathbf{y}_i \cdot \mathbf{y}_i = \cdots = 1 - (\mathbf{x}_i \cdot \mathbf{x}_k)^2 > 0$ άρα το $\hat{\mathbf{y}_i}$ είναι καλώς ορισμένο.

Οπότε τα $\mathbf{y}_1,\ldots,\mathbf{y}_{k-1}$ είναι μοναδιαία διανύσματα σε ένα χώρο n-1

διαστάσεων. Επίσης έχουμε

$\displaystyle{ \mathbf{y}_i \cdot \mathbf{y}_j = \mathbf{x}_i \cdot \mathbf{x}_j -(\mathbf{x}_i \cdot \mathbf{x}_k)(\mathbf{x}_j \cdot \mathbf{x}_k) \leqslant \mathbf{x}_i \cdot \mathbf{x}_j < 0}$

Η τελευταία ανισότητα ισχύει επειδή

$\displaystyle{ 2 < \|\mathbf{x}_i - \mathbf{x}_j\|^2 = 2 - \mathbf{x}_i \cdot \mathbf{x}_j}$

Άρα είναι και $\displaystyle{ \hat{\mathbf{y}_i} \cdot \hat{\mathbf{y}_j} < 0}$ και άρα τα αντίστοιχα σημεία έχουν απόσταση μεγαλύτερη από $\sqrt{2}$ .

Άρα από την επαγωγική υπόθεση είναι $k-1 \leqslant n$ και άρα $k \leqslant n+1$ όπως ισχυριστήκαμε.

Μένει να δείξουμε την ύπαρξη τόσων σημείων.

Αρκεί να βρούμε n+1

διανύσματα (όχι απαραίτητα μοναδιαία) ώστε τα εσωτερικά τους γινόμενα ανά δύο να είναι αρνητικά. (Αφού τότε το ίδιο θα ισχύει και για τα μοναδιαία διανύσματα.) Παίρνω τα
$\displaystyle{ \mathbf{x}_0 = (1,\ldots,1)}$ και $\mathbf{x}_i = (1,\ldots,1,-n,1,\ldots,1)$ για $1 \leqslant i \leqslant n$ όπου βάζω το

στην θέση

. Είναι απλό ότι όλα τα εσωτερικά γινόμενα είναι αρνητικά.

$\rule{500pt}{1pt}$

Ας προσθέσω και την εξής γενίκευση:

Έστω n+k

σημεία στην μοναδιαία σφαίρα του $\mathbb{R}^n$ ώστε η απόσταση μεταξύ κάθε δύο σημείων να είναι το πολύ $\sqrt{2}$ . Τότε μπορώ να τα διαμερίσω σε

υποσύνολα ώστε σημεία που βρίσκονται σε διαφορετικά υποσύνολα να έχουν απόσταση ίση με $\sqrt{2}$ .

$\rule{500pt}{1pt}$

Έχουμε ακόμη κάποιες άλυτες ασκήσεις από παλιούς φοιτητικούς διαγωνισμούς. Στην δημόσια συζήτηση για τους φοιτητικούς διαγωνισμούς υπάρχουν πάνω πάνω αρχεία με μαζεμένες όσες ερωτήσεις έχουμε προτείνει από SEEMOUS, IMC, Vojtech Jarnik και Euler. Όσες είναι κοκκινισμένες περιμένουν λύση. Μερικές εξ αυτών δεν είναι δύσκολες.

#3

Με αφορμή αυτό το θέμα ας δούμε και το παρεμφερές:
Αν $S=\{x_1,...,x_N\}$ είναι ένα υποσύνολο της μοναδιαίας σφαίρας στον $\mathbb{R}^n$ έτσι ώστε για κάθε i,j

να ισχύει $\|x_i-x_j\|\geq\sqrt{2}$ , τότε να δείξετε ότι $N\leq 2n$ .

IMC 2001/2/3

IMC 2001/2/3

Re: IMC 2001/2/3

Re: IMC 2001/2/3

Μέλη σε σύνδεση