IMC 2001/2/3

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2001/2/3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Οκτ 17, 2012 10:04 pm

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


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2001/2/3

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Ιούλ 09, 2016 12:10 pm

Θα δείξω επαγωγικά ότι έχουμε το πολύ 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 όπου βάζω το -n στην θέση i. Είναι απλό ότι όλα τα εσωτερικά γινόμενα είναι αρνητικά.

\rule{500pt}{1pt}

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

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

\rule{500pt}{1pt}

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


Άβαταρ μέλους
silouan
Επιμελητής
Δημοσιεύσεις: 1303
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: IMC 2001/2/3

#3

Μη αναγνωσμένη δημοσίευση από silouan » Κυρ Ιούλ 10, 2016 1:52 am

Με αφορμή αυτό το θέμα ας δούμε και το παρεμφερές:
Αν S=\{x_1,...,x_N\} είναι ένα υποσύνολο της μοναδιαίας σφαίρας στον \mathbb{R}^n έτσι ώστε για κάθε i,j να ισχύει \|x_i-x_j\|\geq\sqrt{2}, τότε να δείξετε ότι N\leq 2n.


Σιλουανός Μπραζιτίκος
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης