Συνδυαστική από IMO

#1

Έστω

ένα υποσύνολο του συνόλου $S = \{1,2,\ldots,1000000\}$ το οποίο περιέχει ακριβώς 101 στοιχεία. Να δειχθεί ότι υπάρχουν αριθμοί $t_1,\ldots,t_{100} \in S$ έτσι ώστε τα σύνολα $\displaystyle{A_j = \{x + t_j: x\in A\}}$ για $j=1,2,\ldots,100$ να είναι ξένα ανά δύο.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#2

Just do it.

nickthegreek · #3

Θα δώσω μια σκέψη στο όμορφο αυτό πρόβλημα. Ελπίζω αυτά που λέω βέβαια παρακάτω να μην είναι λανθασμένα.

Έστω $A=\begin{Bmatrix} a_1,a_2,...,a_{101} \end{Bmatrix}$ Θεωρούμε τα σύνολα (A_j), j=1,2,...,100

. Aυτά είναι της μορφής:

$A_1=\begin{Bmatrix} t_1+a_1,t_1+a_2,...,t_1+a_{101} \end{Bmatrix}$

$A_2=\begin{Bmatrix} t_2+a_1,t_2+a_2,...,t_2+a_{101} \end{Bmatrix}$

.....

$A_{100}=\begin{Bmatrix} t_{100}+a_1,t_{100}+a_2,...,t_{100}+a_{101} \end{Bmatrix}$

Θα χρησιμοποιήσουμε δύο λήμματα.

Λήμμα 1

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Λήμμα 2

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Οι διαφορές $\mid a_i-a_j\mid$ για $a_i \neq a_j$ είναι το πολύ $\binom {101}{2}=5050$ στο σύνολο. Έστω ότι οι διαφορές είναι $d_1,d_2,...,d_{5050}$ με $d_1<d_2<...<d_{5050}$

To ζητούμενο "μεταφράζεται" στο εξής:

"Να αποδείξετε ότι υπάρχουν $t_1,...,t_{100} \in S$ τέτοια ώστε $\mid t_k-t_l\mid \neq d_n, n=1,2,...,5050$ "

Έστω $t_1<t_2<...<t_{100}$ Θα δείξουμε μία μέθοδο επιλογής των $t_1,...,t_{100}$ . (Είναι στην ουσία η υπόδειξη του Δημήτρη, το just do it!)

Θεωρούμε το σύνολο $S=\begin{Bmatrix}1,2,...,1.000.000\end{Bmatrix}$ ως ένα ευθύγραμμο τμήμα πάνω στην γνωστή πραγματική γραμμή. Και τα στοιχεία του

είναι τα στοιχεία του ευθυγράμμου τμήματος με ακέραιες τετμημένες.

Θέτουμε t_1=1

και τοποθετούμε "μπάρες απαγόρευσης" (

) σε όλα τα σημεία του ευθυγράμμου τμήματος που απέχουν από το t_1

απόσταση ίση με d_n

για

Η διαδικασία επιλογής των αριθμών έχει ως εξής:

Ως αριθμό $t_{l+1}$ επιλέγουμε τον αριθμό που είναι όσο το δυνατόν πιο κοντά στον t_l

, αλλά δεν πέφτει πάνω σε κάποια "μπάρα απαγόρευσης". Έπειτα ξανατοποθετούμε άλλες 5050 μπάρες σε όλα τα σημεία του ευθυγράμμου τμήματος που έχουν απόσταση από το
$t_{l+1}$ ίση με d_n

για

και η διαδικασία συνεχίζεται..................

Με αυτήν την διαδικασία θα αποδείξουμε ότι είναι εφικτό να επιλέξουμε όλους τους $t_1,t_2,...,t_{100}$

Πράγματι, έστω ότι η διαδικασία σταματάει στον αριθμό $t_x, x\leq 99$ .Τότε έχουμε τοποθετήσει ήδη 5050x

μπάρες απαγόρευσης συν τους ήδη υπάρχοντες

αριθμούς

. Άρα έχουμε τοποθετήσει συνολικά 5051x

αριθμούς. Αφού η διαδικασία δεν μπορεί να συνεχιστεί άλλο, σημαίνει ότι όλοι οι αριθμοί από το

μέχρι και το 1.000.000

είναι κατειλημμένοι. Άρα $5051x>1.000.000\Rightarrow x>\frac{1.000.000}{5051}>99$ . Όμως εξ υποθέσεως $x\leq 99$ και καταλήγουμε σε άτοπο.

Φιλικά,
Νίκος

#4

Σωστά.

Συνδυαστική από IMO

Συνδυαστική από IMO

Re: Συνδυαστική από IMO

Re: Συνδυαστική από IMO

Re: Συνδυαστική από IMO

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