Προβλήματα Μαθηματικών

1 Ιουλίου, 2015

Εδώ ο κόσμος χάνεται…

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 7:44 μμ

… και εμείς υπολογίζουμε αθροίσματα!!!     Αν οι αριθμοί x_1,x_2,\dots,x_n έχουν άθροισμα μηδέν και είναι όλοι απόλυτα φραγμένοι από μια θετική σταθερά c, τότε υπάρχει αναδιάταξη x_1=x_{k_1},x_{k_2},\dots,x_{k_n} τέτοια ώστε  \displaystyle\left|\sum_{j\leq i} x_{k_j}\right|\leq c για κάθε i. Το πρόβλημα πρότεινε ο Κωνσταντίνος Κουρουζίδης.

17 Σχόλια »

  1. Μια μικρή τροποποίηση στη σημειογραφία: Να συμβολίσουμε την αναδιάταξη, \kappa= x_{k(1)},x_{k(2)},\dots,x_{k(n)}. Η πρόταση ισχύει, οποτεδήποτε δοθέντων των αριθμών x_1,x_2,\dots,x_{k_n} πάρουμε \kappa(1)=1 στην αναδιάταξη μας. Υπάρχει αναδιάταξη δηλαδή, έστω και αν αφήσουμε τον πρώτο όρο στην ίδια θέση.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 1 Ιουλίου, 2015 @ 9:38 μμ

  2. Δοθέντων των αριθμών x_1,x_2, \dots, x_n (διόρθωση ορθογραφικού)

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 1 Ιουλίου, 2015 @ 9:42 μμ

  3. Αν κατάλαβα καλά τι ζητάμε, νομίζω ότι μια τέτοια διάταξη πρακτικά θα μπορούσε να κατασκευαστεί ως εξής:
    Χωρίζουμε τους αριθμούς χ1, χ2, … , χη σε θετικούς και αρνητικούς. Αν ανάμεσά τους υπάρχουν και αριθμοί ίσοι με 0, η θέση τους μπορεί να βρίσκεται οπουδήποτε στη διάταξη. Ας υποθέσουμε λοιπόν ότι, μεταξύ των αριθμών, υπάρχουν ένας τουλάχιστον θετικός και ένας τουλάχιστον αρνητικός.
    Επιλέγουμε για την πρώτη θέση έναν οποιονδήποτε αριθμό Χ1 (ή αφήνουμε τον αριθμό που ήταν πρώτος και στην αρχική διάταξη). Χ.Β.Γ. έστω 0 ≤ Χ1 ≤ c.
    Επιλέγουμε για τις επόμενες θέσεις έναν ή περισσότερους αρνητικούς αριθμούς αθροίσματος Α1, έτσι ώστε να είναι: -c ≤ Χ1+Α1≤ 0. Η σειρά μεταξύ των αριθμών – όρων του αθροίσματος Α1 είναι αδιάφορη.
    Επιλέγουμε για τις επόμενες θέσεις έναν ή περισσότερους θετικούς αριθμούς αθροίσματος Α2, τέτοιους ώστε να είναι: 0 ≤ Χ1+Α1+Α2 ≤ c. Η σειρά μεταξύ των αριθμών – όρων του αθροίσματος Α2 είναι αδιάφορη.
    Συνεχίζουμε εναλλάξ με τον ίδιο τρόπο, μέχρι να τελειώσουν οι αριθμοί, οπότε και Χ1+Α1+Α2+..+Αν = 0.
    Έτσι, τα προοδευτικά αλγεβρικά αθροίσματα των αριθμών της διάταξης, ξεκινώντας από την πρώτη θέση και φτάνοντας μέχρι οποιαδήποτε επόμενη, παραμένουν πάντα εντός του διαστήματος [-c,c].

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 15 Ιουλίου, 2015 @ 12:30 μμ

  4. Σωστός ο αλγόριθμος εύρεσης επιθυμητής αναδιάταξης. Πρέπει να αποδείξουμε γιατί δουλεύει όμως. Μπορούμε να το κάνουμε αυτό χρησιμοποιώντας επαγωγή στα μερικά αθροίσματα. Αν έχουμε ήδη χρησιμοποιήσει μέχρι κάποιο στάδιο αριθμούς:
    K_{j-1}=\{x_{k_1},x_{k_2},\dots,x_{k_{j-1}}\}, που ικανοποιούν |S_{j-1}| \leq c, όπου S_{j-1}=\sum_{i=1}^{j-1}x_{k_{i}}, τότε μπορούμε πάντοτε να επιλέξουμε x_{k_{j}}, έτσι ώστε |S_{j}| \leq c.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 15 Ιουλίου, 2015 @ 2:22 μμ

  5. Ο παραπάνω ισχυρισμός χρειάζεται απόδειξη.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 15 Ιουλίου, 2015 @ 2:25 μμ

  6. Κωνσταντίνε, θα προσπαθήσω να το διατυπώσω όπως το αντιλαμβάνομαι διαισθητικά, αφήνοντας κατά μέρος την επαγωγή που προτείνεις:
    Ο αλγόριθμος νομίζω πως δουλεύει διότι κάθε αριθμός χ1, χ2,..,χn βρίσκεται εξ ορισμού εντός του διαστήματος [-c,c], ενώ το προοδευτικό άθροισμα των αριθμών που έχουν τοποθετηθεί σε κάθε βήμα στη διάταξη είναι ακριβώς αντίθετο του αθροίσματος των αριθμών που δεν έχουν ακόμα τοποθετηθεί, δεδομένου ότι χ1+χ2+..+χη = 0, εξ ορισμού επίσης.
    Αν επομένως το ‘τοποθετημένο’ άθροισμα σε οποιοδήποτε βήμα του αλγορίθμου βρίσκεται στο ένα μισό (στη μεριά του + ή τη μεριά του -) του διαστήματος [-c,c], τότε το ΄μη τοποθετημένο’ άθροισμα θα βρίσκεται στην ακριβώς συμμετρική θέση στην άλλη μεριά. Αναγκαστικά, νομίζω ότι μέχρι να τελειώσουν οι αριθμοί, θα υπάρχει πάντα ένας τουλάχιστον ή ένα μπλοκ μη τοποθετημένων αριθμών, που μπορούν στο επόμενο βήμα να ανατρέπουν, εντός των ορίων του [-c,c] και να ισορροπούν / μηδενίζουν τελικά τη ζυγαριά του προοδευτικού αθροίσματος.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 15 Ιουλίου, 2015 @ 3:42 μμ

  7. Σωστή η απόδειξη. Η συνθήκη \sum\limits_{i=1}^n{x_{i}}=0, είναι ικανή αλλά όχι αναγκαία. Μπορούμε να δείξουμε το ισχυρότερο, ότι αρκεί \sum\limits_{i=1}^n{x_{i}} \leq c, για να υπάρχει η επιθυμητή αναδιάταξη;

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 15 Ιουλίου, 2015 @ 4:27 μμ

  8. Στο νέο ερώτημα, εννοείται ότι όλοι οι αριθμοί παραμένουν απόλυτα φραγμένοι από μια σταθερά που επιλέγουμε πάντοτε να είναι c=\max\{|x_{1}|,|x_{2}|,\ldots,|x_{n}|\}.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 15 Ιουλίου, 2015 @ 4:48 μμ

  9. Νομίζω ότι η συνθήκη Σxi ≤ c δεν αρκεί, αν συμβαίνει να είναι και Σxi ≤ -c.
    Εκτός κι αν εννοείς ότι η νέα συνθήκη είναι η │Σxi│ ≤ c.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 17 Ιουλίου, 2015 @ 12:57 μμ

  10. Έχεις δίκαιο Θανάση. Η απόλυτη τιμή του όλου αθροίσματος να φράσσεται από το c. Έχω μια απόδειξη βασισμένη στην επαγωγή που αναφέρω στο 4. Νομίζω μπορεί να αποδειχθεί και με γενίκευση της δικής σου προσέγγισης αν και πιστεύω είναι δύσκολο να είναι κανείς ακριβής-καλά περιγραφικός με αυτό το πρόβλημα χρησιμοποιώντας τη μέθοδο αυτή.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 17 Ιουλίου, 2015 @ 1:51 μμ

  11. Εντάξει Κωνσταντίνε, είμαστε σύμφωνοι. Ναι, νομίζω ότι η ίδια διαισθητική προσέγγιση θα δούλευε κι εδώ: φορτώνουμε εναλλάξ πακέτα θετικών και αρνητικών αριθμών όσο γίνεται μεγαλύτερου απόλυτου αθροίσματος κάθε φορά, αλλά πάντα κρατώντας το τοποθετημένο άθροισμα εντός του διαστήματος [-c,c], μέχρι να μας τελειώσουν οι αριθμοί.
    Δεν θα κουράσω όμως άλλο με λεπτομέρειες και θα περιμένω να δω, από εσένα ή κάποιον άλλο φίλο, την αυστηρή επαγωγική απόδειξη.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 17 Ιουλίου, 2015 @ 2:16 μμ

  12. Ας την δούμε. Αν x_{i} \in \mathbb{R}, |x_{i}| \leq c, και \left|\sum_{i=1}^{n}x_{i}\right| \leq c, τότε υπάρχει αναδιάταξη k, τέτοια ώστε x_{k_{1}}=x_1 και
    \displaystyle\left|\sum_{i \leq j}x_{k_i}\right| \leq c, για κάθε 1 \leq j \leq n. Απόδειξη πάνω στο στάδιο των μερικών αθροισμάτων j. Χωρίς βλάβη μπορούμε να υποθέσουμε ότι
    0 \leq \left|\sum_{i=1}^{n}x_{i}\right|:=S_{n} \leq c, ειδάλλως αντιστρέφουμε τα πρόσημα όλων των x_{i}. Για j=1, παίρνουμε απλά τον πρώτο όρο στη λίστα των αριθμών που έχουμε, να είναι ο πρώτος όρος στην αναδιάταξή μας και η πρόταση ισχύει βεβαίως. Αρκεί να δείξουμε ότι αν έχουμε ήδη επιλέξει: K_{j-1}=\{x_{k_1},x_{k_2},\dots,x_{k_{j-1}}\}, αναδιατεταγμένους αριθμούς δηλαδή από τη λίστα μας που ικανοποιούν |S_{j-1}| \leq c, όπου S_{j-1}=\sum_{i=1}^{j-1}x_{k_{i}}, τότε μπορούμε πάντοτε να επιλέξουμε x_{k_{j}}, έτσι ώστε |S_{j}| \leq c. Ας ονομάσουμε το x_{\alpha} «ελεύθερον» (είναι ένα από τα x_i) εάν x_{\alpha} \notin K_{j-1}. Επιλέγουμε x_{k_{j}} με τον ακόλουθο κανόνα:
    (1) Εάν S_{j-1} \geq 0 και υπάρχει ελεύθερον x_{\alpha} \leq 0, θέτουμε x_{k_j}=x_{\alpha}. Δουλεύει αφού S_{j-1}+x_{\alpha} \geq S_{j-1}-c \geq -c.
    (2) Εάν S_{j-1} \geq 0 και όλα τα ελεύθερα x_{\alpha} είναι θετικά, μπορούμε να επιλέξουμε οποιοδήποτε, αφού S_{j-1}+x_{\alpha} \leq S_n \leq c.
    (3) Εάν S_{j-1}<0 και υπάρχει ελεύθερον x_{\alpha} \geq 0, θέτουμε x_{k_j}=x_{\alpha}. Δουλεύει αφού S_{j-1}+x_{\alpha} \leq S_{j-1}+c \leq c.
    Μένει να παρατηρήσουμε ότι στην περίπτωση S_{j-1}<0 με όλα ελεύθερα x_{\alpha} < 0 (να είναι όλα αρνητικά), είναι αδύνατον από την υπόθεση που κάναμε αρχικά S_{n} \geq 0.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 17 Ιουλίου, 2015 @ 3:40 μμ

  13. Στην υπόθεση, χωρίς βλάβη για το S_n, δεν έπρεπε να βάλω απόλυτες τιμές.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 17 Ιουλίου, 2015 @ 4:21 μμ

  14. Ευχαριστώ Κωνσταντίνε, εξαιρετική (και ομολογώ καθόλου κουραστική) η απόδειξή σου!

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 17 Ιουλίου, 2015 @ 4:23 μμ

  15. Δεν είναι δική μου.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 17 Ιουλίου, 2015 @ 4:32 μμ

  16. Σε τιμά να το λες! Υπάρχει μήπως τίποτε δικό μας; 🙂 Την παρουσίασες πάντως άψογα, κατά τη γνώμη μου.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — 17 Ιουλίου, 2015 @ 4:44 μμ

  17. Αυτή η άσκηση είναι το λήμμα 3.1 που βρίσκεται στο άρθρο του οποίου η διεύθυνση-link είναι στο πρόβλημα: Διάσπαση ακολουθίας.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — 14 Φεβρουαρίου, 2019 @ 10:15 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.