Μέγιστο πλήθος αθροισμάτων

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #1

Δίνονται

πραγματικοί $x_i\geq 1$
Σχηματίζουμε όλα τα δυνατά αθροίσματα $\sum_{i=1}^{n}\varepsilon _ix_i$ όπου είναι $\varepsilon _i=\pm 1$
Πόσα το πολύ από αυτά μπορούν να βρίσκονται σε ένα διάστημα μήκους

το οποίο δεν περιέχει τουλάχιστον το ένα άκρο του ;

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #2

Επαναφορά.

abfx · #3

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: ↑
Πέμ Νοέμ 14, 2024 8:39 am
Δίνονται πραγματικοί $x_i\geq 1$
Σχηματίζουμε όλα τα δυνατά αθροίσματα $\sum_{i=1}^{n}\varepsilon _ix_i$ όπου είναι $\varepsilon _i=\pm 1$
Πόσα το πολύ από αυτά μπορούν να βρίσκονται σε ένα διάστημα μήκους το οποίο δεν περιέχει τουλάχιστον το ένα άκρο του ;

Καλησπέρα, μια λύση εκτός φακέλου (μάλλον).

Για $A\subseteq \{1,2,\ldots , n\}$ συμβολίζω με s(A)

το άθροισμα $\displaystyle \sum_{i\in A}x_i -\sum_{i\notin A}x_i$ όπου $x_1,\ldots ,x_n$ όπως στην εκφώνηση.

Έστω $A_1,A_2,\ldots , A_k \subseteq \{1,2,\ldots , n\}$ συλλογή διαφορετικών ανά δύο συνόλων τέτοια ώστε:

$s(A_1),\ldots , s(A_k) \in I$ , όπου

διάστημα όπως στην εκφώνηση. Αν τώρα είχαμε $A_r \subseteq A_l$ για κάποια $r \neq l$ , τότε:

$\displaystyle s(A_l)-s(A_r)=2 \sum_{i\in A_l \setminus A_r} x_i \geq 2$ , άτοπο. Επομένως από εδώ έχουμε ότι $\displaystyle k\leq \binom{n}{\lfloor n/2 \rfloor}$ .

Κατασκευάζουμε τώρα $x_1,\ldots , x_n$ ως εξής: Επειδή το $\mathbb R$ είναι άπειρης διάστασης διανυσματικός χώρος

πάνω από το $\mathbb Q$ , υπάρχουν $\delta_1,\ldots , \delta _n >0$ γραμμικά ανεξάρτητα πάνω από το $\mathbb Q$ .

Τα επιλέγουμε αρκετά μικρά (ώστε $\delta_1+\ldots + \delta_n <1 \text{ }(*)$ ).

Θεωρούμε $x_i=1+\delta_i$ . Τότε, για $A\subseteq \{1,2,\ldots , n\}$ με $\displaystyle|A|=\lfloor n/2 \rfloor$ , έχουμε

$\displaystyle s(A)=a+\sum_{i\in A}\delta_i -\sum_{i\notin A}\delta_i$ όπου a=0

ή

αναλόγως.

Εξαιτίας της γραμμικής ανεξαρτησίας και λόγω της (*)

θα ισχύει $\displaystyle |\{s(A): |A|=\lfloor n/2 \rfloor\}\cap (a-1,a+1)|=\binom{n}{\lfloor n/2 \rfloor}$

οπότε έχουμε ότι $\displaystyle \binom{n}{\lfloor n/2 \rfloor}$ είναι το ζητούμενο μέγιστο πλήθος αθροισμάτων.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #4

abfx έγραψε: ↑
Τρί Νοέμ 26, 2024 11:16 pm

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: ↑
Πέμ Νοέμ 14, 2024 8:39 am
Δίνονται πραγματικοί $x_i\geq 1$
Σχηματίζουμε όλα τα δυνατά αθροίσματα $\sum_{i=1}^{n}\varepsilon _ix_i$ όπου είναι $\varepsilon _i=\pm 1$
Πόσα το πολύ από αυτά μπορούν να βρίσκονται σε ένα διάστημα μήκους το οποίο δεν περιέχει τουλάχιστον το ένα άκρο του ;
Καλησπέρα, μια λύση εκτός φακέλου (μάλλον).

Για $A\subseteq \{1,2,\ldots , n\}$ συμβολίζω με το άθροισμα $\displaystyle \sum_{i\in A}x_i -\sum_{i\notin A}x_i$ όπου $x_1,\ldots ,x_n$ όπως στην εκφώνηση.

Έστω $A_1,A_2,\ldots , A_k \subseteq \{1,2,\ldots , n\}$ συλλογή διαφορετικών ανά δύο συνόλων τέτοια ώστε:

$s(A_1),\ldots , s(A_k) \in I$ , όπου διάστημα όπως στην εκφώνηση. Αν τώρα είχαμε $A_r \subseteq A_l$ για κάποια $r \neq l$ , τότε:

$\displaystyle s(A_l)-s(A_r)=2 \sum_{i\in A_l \setminus A_r} x_i \geq 2$ , άτοπο. Επομένως από εδώ έχουμε ότι $\displaystyle k\leq \binom{n}{\lfloor n/2 \rfloor}$ .

Κατασκευάζουμε τώρα $x_1,\ldots , x_n$ ως εξής: Επειδή το $\mathbb R$ είναι άπειρης διάστασης διανυσματικός χώρος

πάνω από το $\mathbb Q$ , υπάρχουν $\delta_1,\ldots , \delta _n >0$ γραμμικά ανεξάρτητα πάνω από το $\mathbb Q$ .

Τα επιλέγουμε αρκετά μικρά (ώστε $\delta_1+\ldots + \delta_n <1 \text{ }(*)$ ).

Θεωρούμε $x_i=1+\delta_i$ . Τότε, για $A\subseteq \{1,2,\ldots , n\}$ με $\displaystyle|A|=\lfloor n/2 \rfloor$ , έχουμε

$\displaystyle s(A)=a+\sum_{i\in A}\delta_i -\sum_{i\notin A}\delta_i$ όπου ή αναλόγως.

Εξαιτίας της γραμμικής ανεξαρτησίας και λόγω της θα ισχύει $\displaystyle |\{s(A): |A|=\lfloor n/2 \rfloor\}\cap (a-1,a+1)|=\binom{n}{\lfloor n/2 \rfloor}$

οπότε έχουμε ότι $\displaystyle \binom{n}{\lfloor n/2 \rfloor}$ είναι το ζητούμενο μέγιστο πλήθος αθροισμάτων.

Πράγματι η λύση βασίζεται στο Θεώρημα του Sperner1928.
Το αν αυτό είναι εντός της ύλης των Μαθηματικών Διαγωνισμών δεν ξέρω.Κατάλληλος για να απαντήσει πιστεύω ότι είναι ο Σιλουανός ο Αχιλλέας κλπ.
Το πιο πάνω είναι αποτέλεσμα του Erdos (1945) το οποίο το έχει γενικεύσει και για διαστήματα μήκους 2r.Να σημειώσω ότι η αρχική απόδειξη του θεωρήματος του Sperner ήταν πολύ πολύπλοκη.Αυτή που κυκλοφορεί τώρα οφείλεται στον Lubell1966.
Να σημειώσω ότι το 1943 οι Littlewood και Offord είχαν διατυπώσει ανάλογο αποτέλεσμα για μιγαδικούς και δίσκους και το είχαν αποδείξει χωρίς το θεώρημα του Sperner.Ο Erdos (1945) το βελτίωσε χρησιμοποιώντας το θεώρημα του Sperner.

Το ότι το μέγιστο πιάνεται μπορούμε να το δούμε πολύ πιο εύκολα παίρνοντας x_i=1

και διάστημα το (-1,1].
Νομίζω ότι εσύ έχεις προσπαθήσει να πιάσεις το μέγιστο για οποιοδήποτε διάστημα.
Η έχεις τυπογραφικό η αλλιώς δεν βλέπω πως ισχύει η απόδειξη σου.

abfx · #5

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: ↑
Τετ Νοέμ 27, 2024 8:21 pm
Το ότι το μέγιστο πιάνεται μπορούμε να το δούμε πολύ πιο εύκολα παίρνοντας και διάστημα το (-1,1].
Νομίζω ότι εσύ έχεις προσπαθήσει να πιάσεις το μέγιστο για οποιοδήποτε διάστημα.
Η έχεις τυπογραφικό η αλλιώς δεν βλέπω πως ισχύει η απόδειξη σου.

Καλησπέρα σας,

Δεν προσπάθησα να πιάσω το μέγιστο για οποιοδήποτε διάστημα. Το διάστημα που πήρα ήταν το (-2,0)

, αν

περιττός και (-1,1)

, αν

άρτιος, όπως φαίνεται εδώ:

abfx έγραψε: ↑
Τρί Νοέμ 26, 2024 11:16 pm
... θα ισχύει $\displaystyle |\{s(A): |A|=\lfloor n/2 \rfloor\}\cap (a-1,a+1)|=\binom{n}{\lfloor n/2 \rfloor}$ ...

Τα επιπλέον βήματα τα έκανα ώστε να φανεί και το ελαφρώς ισχυρότερο από το ζητούμενο, ότι μπορούμε να πάρουμε όλα τα αθροίσματα να είναι διαφορετικά ανά δύο, όπως πάλι φαίνεται στην παραπάνω ισότητα (στη περίπτωση x_i=1

τα αθροίσματα που πέφτουν στο (-1,1]

είναι όλα ακριβώς

(αν

άρτιος) ή

(αν

περιττός)).

Εννοείται αν θέλετε να εξηγήσω κάτι πιο αναλυτικά, θα χαρώ να το κάνω.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #6

abfx έγραψε: ↑
Τετ Νοέμ 27, 2024 9:52 pm

Εννοείται αν θέλετε να εξηγήσω κάτι πιο αναλυτικά, θα χαρώ να το κάνω.

Δεν χρειάζεται να εξηγήσεις κάτι.
Τις εξηγήσεις τις έδωσες.

Μέγιστο πλήθος αθροισμάτων

Μέγιστο πλήθος αθροισμάτων

Re: Μέγιστο πλήθος αθροισμάτων

Re: Μέγιστο πλήθος αθροισμάτων

Re: Μέγιστο πλήθος αθροισμάτων

Re: Μέγιστο πλήθος αθροισμάτων

Re: Μέγιστο πλήθος αθροισμάτων

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