Putnam 2017/A4
Συντονιστές: Demetres, silouan
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Putnam 2017/A4
Σε μια τάξη με δόθηκε ένα διαγώνισμα όπου οι δυνατές βαθμολογίες ήταν οι Κάθε μία από αυτές τις βαθμολογίες εμφανίστηκε τουλάχιστον μία φορά. Η μέση βαθμολογία ήταν ακριβώς Να δειχθεί ότι μπορούμε να χωρίσουμε τους μαθητές της τάξης σε δύο ίσες ομάδες των μαθητών με τέτοιο τρόπο ώστε στην κάθε ομάδα η μέση βαθμολογία να είναι ακριβώς
Λέξεις Κλειδιά:
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Παρατηρούμε ότι το άθροισμα όλων των βαθμών οφείλει να είναι άρτιος: αυτό προκύπτει από την και την συνεπαγόμενη διαιρετότητα του δια του . (Ο οφείλει να είναι πολλαπλάσιο του λόγω της , οπότε θέτοντας συμπεραίνουμε ότι ο οφείλει να είναι ακέραιος, άρα .)
Αν δεν μπορούμε να διαχωρίσουμε το σύνολο των μαθητών σε δύο υποομάδες με μαθητές η κάθε μία και ίσο άθροισμα βαθμών (άρα και μέσο όρο η κάθε μία), τότε υπάρχει μία ελάχιστη δυνατή διαφορά ανάμεσα σε δύο πλησιέστερες βαθμολογικά υποομάδες ... και, επειδή το άθροισμα όλων των βαθμών είναι άρτιος, . Ας είναι λοιπόν , τα αθροίσματα βαθμών των δύο υποομάδων μαθητών, με .
Αν υπάρχει 10 στην υποομάδα (με άθροισμα βαθμών) , τότε δεν μπορεί να υπάρχει 9 στην υποομάδα (με άθροισμα βαθμών) , καθώς σε μια τέτοια περίπτωση στέλνουμε το 10 της στην και το 9 της στην και μικραίνουμε κατά την διαφορά ανάμεσα στις και , κάτι αδύνατον κάτω από τις ως τώρα παραδοχές μας. (Αν τότε δημιουργούνται δύο υποομάδες με ίσες συνολικές βαθμολογίες, ενώ αν τότε δημιουργούνται δύο υποομάδες με διαφορά συνολικών βαθμολογιών μικρότερη του .) Αν λοιπόν υπάρχει 10 στην τότε όλα τα 9 βρίσκονται επίσης στην . Με ανάλογο συλλογισμό στην βρίσκονται και όλα τα 8, αλλά και όλα τα 7, κοκ Έχουμε καταλήξει σε άτοπο υποθέτοντας ότι στην υποομάδα υπάρχει μαθητής με βαθμό 10. Αναλόγως δεν μπορεί να υπάρχει μαθητής με βαθμό 9 στην , διότι τότε η οφείλει να περιέχει όλους τους βαθμούς από 8 και κάτω, κοκ
[Στον παραπάνω δια της εις άτοπον απαγωγής συλλογισμό χρησιμοποιήθηκε η υπόθεση ότι κάθε βαθμός εμφανίζεται μία τουλάχιστον φορά ... στην κατά κάθοδο σε κάθε βήμα. Για ένα αντιπαράδειγμα ας θεωρήσουμε μία τάξη μαθητών με βαθμούς 9, 9, 9, 9, 9, 9, 9, 5, 3, 3.]
Αν δεν μπορούμε να διαχωρίσουμε το σύνολο των μαθητών σε δύο υποομάδες με μαθητές η κάθε μία και ίσο άθροισμα βαθμών (άρα και μέσο όρο η κάθε μία), τότε υπάρχει μία ελάχιστη δυνατή διαφορά ανάμεσα σε δύο πλησιέστερες βαθμολογικά υποομάδες ... και, επειδή το άθροισμα όλων των βαθμών είναι άρτιος, . Ας είναι λοιπόν , τα αθροίσματα βαθμών των δύο υποομάδων μαθητών, με .
Αν υπάρχει 10 στην υποομάδα (με άθροισμα βαθμών) , τότε δεν μπορεί να υπάρχει 9 στην υποομάδα (με άθροισμα βαθμών) , καθώς σε μια τέτοια περίπτωση στέλνουμε το 10 της στην και το 9 της στην και μικραίνουμε κατά την διαφορά ανάμεσα στις και , κάτι αδύνατον κάτω από τις ως τώρα παραδοχές μας. (Αν τότε δημιουργούνται δύο υποομάδες με ίσες συνολικές βαθμολογίες, ενώ αν τότε δημιουργούνται δύο υποομάδες με διαφορά συνολικών βαθμολογιών μικρότερη του .) Αν λοιπόν υπάρχει 10 στην τότε όλα τα 9 βρίσκονται επίσης στην . Με ανάλογο συλλογισμό στην βρίσκονται και όλα τα 8, αλλά και όλα τα 7, κοκ Έχουμε καταλήξει σε άτοπο υποθέτοντας ότι στην υποομάδα υπάρχει μαθητής με βαθμό 10. Αναλόγως δεν μπορεί να υπάρχει μαθητής με βαθμό 9 στην , διότι τότε η οφείλει να περιέχει όλους τους βαθμούς από 8 και κάτω, κοκ
[Στον παραπάνω δια της εις άτοπον απαγωγής συλλογισμό χρησιμοποιήθηκε η υπόθεση ότι κάθε βαθμός εμφανίζεται μία τουλάχιστον φορά ... στην κατά κάθοδο σε κάθε βήμα. Για ένα αντιπαράδειγμα ας θεωρήσουμε μία τάξη μαθητών με βαθμούς 9, 9, 9, 9, 9, 9, 9, 5, 3, 3.]
τελευταία επεξεργασία από gbaloglou σε Κυρ Δεκ 10, 2017 11:37 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
ΕΙΚΑΖΩ ότι οποιαδήποτε τάξη με άρτιο αριθμό φοιτητών και άρτιο άθροισμα βαθμών, και στην οποία έχουν από τουλάχιστον μια φορά εμφανιστεί τουλάχιστον ΕΠΤΑ από τους βαθμούς 0-10, μπορεί να διαμερισθεί σε δύο ισοπληθείς υποομάδες με ίσο μέσο όρο βαθμών.
[Για ΕΞΙ βαθμούς υπάρχει το προφανές αντιπαράδειγμα {10, 8, 6, 4, 2, 0}.]
[Για ΕΞΙ βαθμούς υπάρχει το προφανές αντιπαράδειγμα {10, 8, 6, 4, 2, 0}.]
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Για να κάνω την παραπάνω εικασία πιο προσιτή, δίνω το παράδειγμα ΕΠΤΑ βαθμών {10, 8, 6, 6, 6, 6, 5, 5, 4, 2, 0, 0}, και τον διαμερισμό στις υποομάδες {10, 8, 6, 5, 0, 0} & {6, 6, 6, 5, 4, 2}, με μέσο όρο (και άθροισμα ) έκαστη: αναφερόμενος τώρα στον συλλογισμό που εφαρμόστηκε στην περίπτωση των ΕΝΔΕΚΑ βαθμών, θα μπορούσα να θεωρήσω = {10, 6, 5, 5, 4, 0}, = {8, 6, 6, 6, 2, 0}, με , , και να παρατηρήσω ότι μετά το 6 της ακολουθούν εκεί όλα τα 5 και όλα τα 4, έτσι ώστε να μην είναι δυνατή η ελάττωση της διαφοράς : το πρόβλημα είναι ότι υπάρχει ήδη άλλος διαμερισμός με , κλπ κλπ (Βλέπουμε δηλαδή ότι η ύπαρξη τριών διαδοχικών βαθμών, που εξασφαλίζεται από το πλήθος των υπαρκτών βαθμών (ΕΠΤΑ) στο σύνολο των δυνατών ΕΝΔΕΚΑ βαθμών (μέσω της αρχής της περιστερότρυπας), αφ' ενός μεν δεν σώζει τον συλλογισμό που εφαρμόστηκε στην περίπτωση του αρχικού προβλήματος, αφ' ετέρου δε επιτρέπει τον διαμερισμό σε δύο ισοπληθείς και βαθμολογικά ίσες υποομάδες.)gbaloglou έγραψε: ↑Σάβ Δεκ 09, 2017 7:23 pmΕΙΚΑΖΩ ότι οποιαδήποτε τάξη με άρτιο αριθμό φοιτητών και άρτιο άθροισμα βαθμών, και στην οποία έχουν από τουλάχιστον μια φορά εμφανιστεί τουλάχιστον ΕΠΤΑ από τους βαθμούς 0-10, μπορεί να διαμερισθεί σε δύο ισοπληθείς υποομάδες με ίσο μέσο όρο βαθμών.
[Για ΕΞΙ βαθμούς υπάρχει το προφανές αντιπαράδειγμα {10, 8, 6, 4, 2, 0}.]
Παραμένει ανοικτή η εικασία λοιπόν!
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Σε μία περαιτέρω απόπειρα 'δυναμικής κατανόησης' της εικασίας -- που αποκαλώ πλέον "Εικασία 7/11" (επηρεασμένος ίσως από την γνωστή αλυσίδα καταστημάτων )-- παραθέτω την εξής παρατήρηση (που ίσως βοηθήσει άλλους να την αποδείξουν):
Ας πούμε ότι έχουν δοθεί όλοι οι άρτιοι βαθμοί και ο . Βεβαίως ο αριθμός εμφανίσεων του οφείλει να είναι άρτιος. Θα μπορούσαμε να σκεφθούμε για τους άλλους βαθμούς ότι αν κάποιος από αυτούς εμφανίζεται πχ δύο φορές τότε μπορούμε, χάριν απλοποίησης της κατάστασης, να τον 'αφαιρέσουμε' από το πρόβλημα, αποδεικνύοντας ότι υπάρχει επιθυμητός διαμερισμός των βαθμών τέτοιος ώστε η κάθε μία από τις δύο ισόβαθμες υποομάδες να τον περιέχει ακριβώς μία φορά. Πειραματιζόμενος με τις 15 περιπτώσεις όπου δύο ακριβώς άρτιοι βαθμοί, αλλά και ο , εμφανίζονται δύο ακριβώς φορές, ενώ όλοι οι άλλοι άρτιοι βαθμοί ακριβώς μία φορά, διαπιστώνω ότι η παραπάνω 'απλοποίηση' ΔΕΝ είναι δυνατή σε 2 ακριβώς από τις 15 περιπτώσεις, {} (όπου όμως η Εικασία 7/11 ισχύει λόγω της ) και {} (όπου η Εικασία 7/11 ισχύει και πάλι λόγω της ). (Επισημαίνω και κάτι μάλλον προφανές: στις υπόλοιπες 13 περιπτώσεις άλλοτε υπάρχει λύση με κάθε υποομάδα να περιέχει ακριβώς ένα και άλλοτε όχι.)
[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {, , ... , }, για παράδειγμα).]
Ας πούμε ότι έχουν δοθεί όλοι οι άρτιοι βαθμοί και ο . Βεβαίως ο αριθμός εμφανίσεων του οφείλει να είναι άρτιος. Θα μπορούσαμε να σκεφθούμε για τους άλλους βαθμούς ότι αν κάποιος από αυτούς εμφανίζεται πχ δύο φορές τότε μπορούμε, χάριν απλοποίησης της κατάστασης, να τον 'αφαιρέσουμε' από το πρόβλημα, αποδεικνύοντας ότι υπάρχει επιθυμητός διαμερισμός των βαθμών τέτοιος ώστε η κάθε μία από τις δύο ισόβαθμες υποομάδες να τον περιέχει ακριβώς μία φορά. Πειραματιζόμενος με τις 15 περιπτώσεις όπου δύο ακριβώς άρτιοι βαθμοί, αλλά και ο , εμφανίζονται δύο ακριβώς φορές, ενώ όλοι οι άλλοι άρτιοι βαθμοί ακριβώς μία φορά, διαπιστώνω ότι η παραπάνω 'απλοποίηση' ΔΕΝ είναι δυνατή σε 2 ακριβώς από τις 15 περιπτώσεις, {} (όπου όμως η Εικασία 7/11 ισχύει λόγω της ) και {} (όπου η Εικασία 7/11 ισχύει και πάλι λόγω της ). (Επισημαίνω και κάτι μάλλον προφανές: στις υπόλοιπες 13 περιπτώσεις άλλοτε υπάρχει λύση με κάθε υποομάδα να περιέχει ακριβώς ένα και άλλοτε όχι.)
[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {, , ... , }, για παράδειγμα).]
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Για (ελάχιστο δυνατό) έχουμε ήδη το αντιπαράδειγμα {} ... που πάντως είναι το μόνο δυνατό στην κατηγορία του*.gbaloglou έγραψε: ↑Τρί Δεκ 26, 2017 11:56 pm[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {, , ... , }, για παράδειγμα).]
... Είναι λοιπόν αρκετά λογικό να αναμένει κανείς ότι ένα αντιπαράδειγμα για (αρχική εικασία 7/11) είναι απλώς θέμα χρόνου και προσπάθειας ... χωρίς φυσικά να αποκλείεται η πιθανότητα εκπλήξεων, μεγαλύτερου 'βάθους' του προβλήματος, κλπ κλπ
*Για οι 'βασικές', μη τετριμμένες βαθμολογικές καταστάσεις που πληρούν τις συνθήκες της εικασίας -- αρτιότητα αριθμού μαθητών και αρτιότητα αθροίσματος βαθμών -- είναι (νομίζω) οι {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}.
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Ήδη για και για βρίσκω ανάλογα αντιπαραδείγματα, {} και {}gbaloglou έγραψε: ↑Πέμ Δεκ 28, 2017 11:00 pmΓια (ελάχιστο δυνατό) έχουμε ήδη το αντιπαράδειγμα {} ... που πάντως είναι το μόνο δυνατό στην κατηγορία του*.gbaloglou έγραψε: ↑Τρί Δεκ 26, 2017 11:56 pm[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {, , ... , }, για παράδειγμα).]
... Είναι λοιπόν αρκετά λογικό να αναμένει κανείς ότι ένα αντιπαράδειγμα για (αρχική εικασία 7/11) είναι απλώς θέμα χρόνου και προσπάθειας ... χωρίς φυσικά να αποκλείεται η πιθανότητα εκπλήξεων, μεγαλύτερου 'βάθους' του προβλήματος, κλπ κλπ
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Putnam 2017/A4
Δεν ισχύει η εικασία. Ένα αντιπαράδειγμα είναι το . Το συνολικό άθροισμα είναι οπότε κάθε υποσύνολο θα έπρεπε να έχει άθροισμα . Κάθε υποσύνολο θα έχει αριθμούς. Άρα ένα από αυτά θα έχει τουλάχιστον από τους και άρα άθροισμα τουλάχιστον , άτοπο.
Πιθανώς όμως η εικασία να ισχύει για μεγάλα .
Πιθανώς όμως η εικασία να ισχύει για μεγάλα .
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Δημήτρη πολύ ωραία, έψαχνα και εγώ για κάποιο 'ανισόρροπο' αντιπαράδειγμα (με αριθμούς προς τα δύο άκρα, όπως αυτά που είχα δώσει για ) αλλά δεν το βρήκα ... και όσο δεν το έβρισκα ... τόσο υποπτευόμουν και εγώ κάτι καλό για μεγάλαDemetres έγραψε: ↑Κυρ Δεκ 31, 2017 10:53 amΔεν ισχύει η εικασία. Ένα αντιπαράδειγμα είναι το . Το συνολικό άθροισμα είναι οπότε κάθε υποσύνολο θα έπρεπε να έχει άθροισμα . Κάθε υποσύνολο θα έχει αριθμούς. Άρα ένα από αυτά θα έχει τουλάχιστον από τους και άρα άθροισμα τουλάχιστον , άτοπο.
Πιθανώς όμως η εικασία να ισχύει για μεγάλα .
[Αν θέλει να βοηθήσει κανείς που ξέρει δυο πράγματα από προγραμματισμό: αρκεί να εξεταστούν οι περιπτώσεις (για , ...) όπου από τους αριθμούς {} εμφανίζονται μία ή δύο φορές ο καθένας (με τέτοιο τρόπο ώστε και το πλήθος και το άθροισμα τους να είναι άρτιο).]
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Re: Putnam 2017/A4
Για n = 2, όντως είναι μια μοναδική περίπτωση: { 4, 4, 3, 1, 0, 0 }
Για n = 3: { 6, 6, 5, 2, 1, 0 } και { 6, 5, 4, 1, 0, 0 }
Για n = 4: { 8, 8, 7, 3, 2, 1, 1, 0 }, { 8, 7, 7, 6, 5, 1, 0, 0 }, { 8, 7, 6, 2, 1, 0 } και { 8, 6, 5, 3, 2, 0 }
Για n = 5: { 10, 9, 8, 3, 2, 1, 1, 0 } και { 10, 9, 9, 8, 7, 2, 1, 0 }
Για n = 6: { 12, 11, 11, 10, 9, 3, 2, 1, 1, 0 } (μοναδικό)
Για n = 7, 8 και 9 θα σας απαντήσω αύριο.
Για n = 10 το κόστος υπολογισμού ανέρχεται σε 1000€ συν ΦΠΑ 24%
Για n = 3: { 6, 6, 5, 2, 1, 0 } και { 6, 5, 4, 1, 0, 0 }
Για n = 4: { 8, 8, 7, 3, 2, 1, 1, 0 }, { 8, 7, 7, 6, 5, 1, 0, 0 }, { 8, 7, 6, 2, 1, 0 } και { 8, 6, 5, 3, 2, 0 }
Για n = 5: { 10, 9, 8, 3, 2, 1, 1, 0 } και { 10, 9, 9, 8, 7, 2, 1, 0 }
Για n = 6: { 12, 11, 11, 10, 9, 3, 2, 1, 1, 0 } (μοναδικό)
Για n = 7, 8 και 9 θα σας απαντήσω αύριο.
Για n = 10 το κόστος υπολογισμού ανέρχεται σε 1000€ συν ΦΠΑ 24%
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Πολύ ενδιαφέρουσα, αν όχι πολλά υποσχόμενη, η μείωση των αντιπαραδειγμάτων ύστερα από το -- αγωνιούμε (και ευχαριστούμε)!
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Re: Putnam 2017/A4
Για n = 7 και n = 8 δεν βρέθηκε τίποτα. Η περίπτωση n = 9 θα είναι έτοιμη μάλλον αύριο αλλά μέχρι στιγμής δεν έχει δώσει κάτι.
Όπως ειπώθηκε παραπάνω, πιστεύω ότι όσο μεγαλώνει το n δίνονται περισσότερες δυνατότητες συνδυασμών και πιστεύω ότι δεν θα βρεθεί κάτι, αλλά η απόδειξη μου φαίνεται δύσκολη. Αυτό που έχει πλάκα είναι η συμμετρία που παρουσιάζουν οι περιπτώσεις 2, 3, 4, 5 και 6: 1, 2, 4, 2, 1
Όπως ειπώθηκε παραπάνω, πιστεύω ότι όσο μεγαλώνει το n δίνονται περισσότερες δυνατότητες συνδυασμών και πιστεύω ότι δεν θα βρεθεί κάτι, αλλά η απόδειξη μου φαίνεται δύσκολη. Αυτό που έχει πλάκα είναι η συμμετρία που παρουσιάζουν οι περιπτώσεις 2, 3, 4, 5 και 6: 1, 2, 4, 2, 1
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Putnam 2017/A4
Όπως με πληροφορεί ο Πάνος, δεν υπάρχει αντιπαράδειγμα ούτε για , από εκεί και πέρα η αναζήτηση χωρίς κάποιες νέες ιδέες θα ήταν απαγορευτικά χρονοβόρα.
Ας επισημάνω κάποια πράγματα για τα αντιπαραδείγματα που έχουμε βρει: ουσιαστικά δεν είναι δέκα αλλά επτά, καθώς κάποια από αυτά είναι 'δυϊκά' το ένα του άλλου, με την έννοια ότι αν το {Χi} είναι αντιπαράδειγμα τότε και το {2n-Χi} είναι αντιπαράδειγμα. (Βεβαίως κάποια αντιπαραδείγματα είναι δυϊκά του εαυτού τους, όπως το {4, 4, 3, 1, 0, 0} (για ) και το {12, 11, 11, 10, 9, 3, 2, 1, 1, 0} (για ).) Έτσι μπορούμε να πούμε ότι είχα ουσιαστικά βρει όλα τα αντιπαραδείγματα για (καθώς τα {6, 6, 5, 2, 1, 0} και {6, 5, 4, 1, 0, 0} είναι δυϊκά το ένα του άλλου), ενώ ο Δημήτρης είχε ουσιαστικά βρει όλα τα αντιπαραδείγματα για (καθώς τα {10, 9, 8, 3, 2, 1, 1, 0} και {10, 9, 9, 8, 7, 2, 1, 0} είναι δυϊκά το ένα του άλλου).
Δεν ξέρω πόσο θα βοηθούσε αυτό στην αναζήτηση (απόδειξης μη ύπαρξης) 'υψηλοτέρων' αντιπαραδειγμάτων με το χέρι, παραθέτω όμως εδώ (ακολουθώντας την βασική ιδέα της επίλυσης του προβλήματος Α4) τις αναλύσεις του καθενός από τα επτά αντιπαραδείγματα σε δύο υποομάδες με διαφορά αθροισμάτων (παρατηρώντας ότι η χαμηλότερη υποομάδα δεν μπορεί να περιέχει μέλος της υψηλότερης υποομάδας μειωμένο κατά ): , , , , , , .
Ας επισημάνω κάποια πράγματα για τα αντιπαραδείγματα που έχουμε βρει: ουσιαστικά δεν είναι δέκα αλλά επτά, καθώς κάποια από αυτά είναι 'δυϊκά' το ένα του άλλου, με την έννοια ότι αν το {Χi} είναι αντιπαράδειγμα τότε και το {2n-Χi} είναι αντιπαράδειγμα. (Βεβαίως κάποια αντιπαραδείγματα είναι δυϊκά του εαυτού τους, όπως το {4, 4, 3, 1, 0, 0} (για ) και το {12, 11, 11, 10, 9, 3, 2, 1, 1, 0} (για ).) Έτσι μπορούμε να πούμε ότι είχα ουσιαστικά βρει όλα τα αντιπαραδείγματα για (καθώς τα {6, 6, 5, 2, 1, 0} και {6, 5, 4, 1, 0, 0} είναι δυϊκά το ένα του άλλου), ενώ ο Δημήτρης είχε ουσιαστικά βρει όλα τα αντιπαραδείγματα για (καθώς τα {10, 9, 8, 3, 2, 1, 1, 0} και {10, 9, 9, 8, 7, 2, 1, 0} είναι δυϊκά το ένα του άλλου).
Δεν ξέρω πόσο θα βοηθούσε αυτό στην αναζήτηση (απόδειξης μη ύπαρξης) 'υψηλοτέρων' αντιπαραδειγμάτων με το χέρι, παραθέτω όμως εδώ (ακολουθώντας την βασική ιδέα της επίλυσης του προβλήματος Α4) τις αναλύσεις του καθενός από τα επτά αντιπαραδείγματα σε δύο υποομάδες με διαφορά αθροισμάτων (παρατηρώντας ότι η χαμηλότερη υποομάδα δεν μπορεί να περιέχει μέλος της υψηλότερης υποομάδας μειωμένο κατά ): , , , , , , .
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 3 επισκέπτες