Putnam 2017/A4

Συντονιστές: Demetres, silouan

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

Putnam 2017/A4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Δεκ 06, 2017 10:14 am

Σε μια τάξη με 2N δόθηκε ένα διαγώνισμα όπου οι δυνατές βαθμολογίες ήταν οι 0,1,\dots,10. Κάθε μία από αυτές τις βαθμολογίες εμφανίστηκε τουλάχιστον μία φορά. Η μέση βαθμολογία ήταν ακριβώς 7.4. Να δειχθεί ότι μπορούμε να χωρίσουμε τους μαθητές της τάξης σε δύο ίσες ομάδες των N μαθητών με τέτοιο τρόπο ώστε στην κάθε ομάδα η μέση βαθμολογία να είναι ακριβώς 7.4.



Λέξεις Κλειδιά:
Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#2

Μη αναγνωσμένη δημοσίευση από gbaloglou » Παρ Δεκ 08, 2017 11:06 am

Παρατηρούμε ότι το άθροισμα S όλων των βαθμών οφείλει να είναι άρτιος: αυτό προκύπτει από την S/2N=7,4 και την συνεπαγόμενη διαιρετότητα του N δια του 5. (Ο N οφείλει να είναι πολλαπλάσιο του 5 λόγω της S=14,8N, οπότε θέτοντας N=5m+k συμπεραίνουμε ότι ο 0,8k οφείλει να είναι ακέραιος, άρα k=0.)

Αν δεν μπορούμε να διαχωρίσουμε το σύνολο των μαθητών σε δύο υποομάδες με N μαθητές η κάθε μία και ίσο άθροισμα βαθμών (άρα και μέσο όρο 7,4 η κάθε μία), τότε υπάρχει μία ελάχιστη δυνατή διαφορά d ανάμεσα σε δύο πλησιέστερες βαθμολογικά υποομάδες ... και, επειδή το άθροισμα όλων των βαθμών είναι άρτιος, d\geq2. Ας είναι λοιπόν A, B τα αθροίσματα βαθμών των δύο υποομάδων μαθητών, με A-B=d\geq2.

Αν υπάρχει 10 στην υποομάδα (με άθροισμα βαθμών) A, τότε δεν μπορεί να υπάρχει 9 στην υποομάδα (με άθροισμα βαθμών) B, καθώς σε μια τέτοια περίπτωση στέλνουμε το 10 της A στην B και το 9 της B στην A και μικραίνουμε κατά 2 την διαφορά ανάμεσα στις A και B, κάτι αδύνατον κάτω από τις ως τώρα παραδοχές μας. (Αν d=2 τότε δημιουργούνται δύο υποομάδες με ίσες συνολικές βαθμολογίες, ενώ αν d>2 τότε δημιουργούνται δύο υποομάδες με διαφορά συνολικών βαθμολογιών μικρότερη του d.) Αν λοιπόν υπάρχει 10 στην A τότε όλα τα 9 βρίσκονται επίσης στην A. Με ανάλογο συλλογισμό στην A βρίσκονται και όλα τα 8, αλλά και όλα τα 7, κοκ Έχουμε καταλήξει σε άτοπο υποθέτοντας ότι στην υποομάδα A υπάρχει μαθητής με βαθμό 10. Αναλόγως δεν μπορεί να υπάρχει μαθητής με βαθμό 9 στην A, διότι τότε η A οφείλει να περιέχει όλους τους βαθμούς από 8 και κάτω, κοκ

[Στον παραπάνω δια της εις άτοπον απαγωγής συλλογισμό χρησιμοποιήθηκε η υπόθεση ότι κάθε βαθμός εμφανίζεται μία τουλάχιστον φορά ... στην κατά 1 κάθοδο σε κάθε βήμα. Για ένα αντιπαράδειγμα ας θεωρήσουμε μία τάξη 10 μαθητών με βαθμούς 9, 9, 9, 9, 9, 9, 9, 5, 3, 3.]
τελευταία επεξεργασία από gbaloglou σε Κυρ Δεκ 10, 2017 11:37 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7575
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Putnam 2017/A4

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Δεκ 08, 2017 2:21 pm

Ωραία. Για προφανείς λόγους αυτή η μέθοδος ονομάζεται διακριτή συνέχεια.


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#4

Μη αναγνωσμένη δημοσίευση από gbaloglou » Σάβ Δεκ 09, 2017 7:23 pm

ΕΙΚΑΖΩ ότι οποιαδήποτε τάξη με άρτιο αριθμό φοιτητών και άρτιο άθροισμα βαθμών, και στην οποία έχουν από τουλάχιστον μια φορά εμφανιστεί τουλάχιστον ΕΠΤΑ από τους βαθμούς 0-10, μπορεί να διαμερισθεί σε δύο ισοπληθείς υποομάδες με ίσο μέσο όρο βαθμών.

[Για ΕΞΙ βαθμούς υπάρχει το προφανές αντιπαράδειγμα {10, 8, 6, 4, 2, 0}.]


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#5

Μη αναγνωσμένη δημοσίευση από gbaloglou » Τετ Δεκ 13, 2017 1:17 pm

gbaloglou έγραψε:
Σάβ Δεκ 09, 2017 7:23 pm
ΕΙΚΑΖΩ ότι οποιαδήποτε τάξη με άρτιο αριθμό φοιτητών και άρτιο άθροισμα βαθμών, και στην οποία έχουν από τουλάχιστον μια φορά εμφανιστεί τουλάχιστον ΕΠΤΑ από τους βαθμούς 0-10, μπορεί να διαμερισθεί σε δύο ισοπληθείς υποομάδες με ίσο μέσο όρο βαθμών.

[Για ΕΞΙ βαθμούς υπάρχει το προφανές αντιπαράδειγμα {10, 8, 6, 4, 2, 0}.]
Για να κάνω την παραπάνω εικασία πιο προσιτή, δίνω το παράδειγμα ΕΠΤΑ βαθμών {10, 8, 6, 6, 6, 6, 5, 5, 4, 2, 0, 0}, και τον διαμερισμό στις υποομάδες {10, 8, 6, 5, 0, 0} & {6, 6, 6, 5, 4, 2}, με μέσο όρο 4,83... (και άθροισμα 29) έκαστη: αναφερόμενος τώρα στον συλλογισμό που εφαρμόστηκε στην περίπτωση των ΕΝΔΕΚΑ βαθμών, θα μπορούσα να θεωρήσω A = {10, 6, 5, 5, 4, 0}, B = {8, 6, 6, 6, 2, 0}, με A=30, B=28, και να παρατηρήσω ότι μετά το 6 της A ακολουθούν εκεί όλα τα 5 και όλα τα 4, έτσι ώστε να μην είναι δυνατή η ελάττωση της διαφοράς A-B: το πρόβλημα είναι ότι υπάρχει ήδη άλλος διαμερισμός με A-B=0, κλπ κλπ (Βλέπουμε δηλαδή ότι η ύπαρξη τριών διαδοχικών βαθμών, που εξασφαλίζεται από το πλήθος των υπαρκτών βαθμών (ΕΠΤΑ) στο σύνολο των δυνατών ΕΝΔΕΚΑ βαθμών (μέσω της αρχής της περιστερότρυπας), αφ' ενός μεν δεν σώζει τον συλλογισμό που εφαρμόστηκε στην περίπτωση του αρχικού προβλήματος, αφ' ετέρου δε επιτρέπει τον διαμερισμό σε δύο ισοπληθείς και βαθμολογικά ίσες υποομάδες.)

Παραμένει ανοικτή η εικασία λοιπόν!


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#6

Μη αναγνωσμένη δημοσίευση από gbaloglou » Τρί Δεκ 26, 2017 11:56 pm

Σε μία περαιτέρω απόπειρα 'δυναμικής κατανόησης' της εικασίας -- που αποκαλώ πλέον "Εικασία 7/11" (επηρεασμένος ίσως από την γνωστή αλυσίδα καταστημάτων :) )-- παραθέτω την εξής παρατήρηση (που ίσως βοηθήσει άλλους να την αποδείξουν):

Ας πούμε ότι έχουν δοθεί όλοι οι άρτιοι βαθμοί και ο 3. Βεβαίως ο αριθμός εμφανίσεων του 3 οφείλει να είναι άρτιος. Θα μπορούσαμε να σκεφθούμε για τους άλλους βαθμούς ότι αν κάποιος από αυτούς εμφανίζεται πχ δύο φορές τότε μπορούμε, χάριν απλοποίησης της κατάστασης, να τον 'αφαιρέσουμε' από το πρόβλημα, αποδεικνύοντας ότι υπάρχει επιθυμητός διαμερισμός των βαθμών τέτοιος ώστε η κάθε μία από τις δύο ισόβαθμες υποομάδες να τον περιέχει ακριβώς μία φορά. Πειραματιζόμενος με τις 15 περιπτώσεις όπου δύο ακριβώς άρτιοι βαθμοί, αλλά και ο 3, εμφανίζονται δύο ακριβώς φορές, ενώ όλοι οι άλλοι άρτιοι βαθμοί ακριβώς μία φορά, διαπιστώνω ότι η παραπάνω 'απλοποίηση' ΔΕΝ είναι δυνατή σε 2 ακριβώς από τις 15 περιπτώσεις, {10, 8, 8, 6, 6, 4, 3, 3, 2, 0} (όπου όμως η Εικασία 7/11 ισχύει λόγω της 10 + 8 + 4 + 3 + 0 = 8 + 6 + 6 + 3 + 2) και {10, 8, 6, 4, 4, 3, 3, 2, 2, 0} (όπου η Εικασία 7/11 ισχύει και πάλι λόγω της 10 + 4 + 3 + 2 + 2 = 8 + 6 + 4 + 3 + 0). (Επισημαίνω και κάτι μάλλον προφανές: στις υπόλοιπες 13 περιπτώσεις άλλοτε υπάρχει λύση με κάθε υποομάδα να περιέχει ακριβώς ένα 3 και άλλοτε όχι.)

[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {0, 1, ... , 2n}, για παράδειγμα).]


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#7

Μη αναγνωσμένη δημοσίευση από gbaloglou » Πέμ Δεκ 28, 2017 11:00 pm

gbaloglou έγραψε:
Τρί Δεκ 26, 2017 11:56 pm
[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {0, 1, ... , 2n}, για παράδειγμα).]
Για n=2 (ελάχιστο δυνατό) έχουμε ήδη το αντιπαράδειγμα {4, 4, 3, 1, 0, 0} ... που πάντως είναι το μόνο δυνατό στην κατηγορία του*.

... Είναι λοιπόν αρκετά λογικό να αναμένει κανείς ότι ένα αντιπαράδειγμα για n=5 (αρχική εικασία 7/11) είναι απλώς θέμα χρόνου και προσπάθειας ... χωρίς φυσικά να αποκλείεται η πιθανότητα εκπλήξεων, μεγαλύτερου 'βάθους' του προβλήματος, κλπ κλπ

*Για n=2 οι 'βασικές', μη τετριμμένες βαθμολογικές καταστάσεις που πληρούν τις συνθήκες της εικασίας -- αρτιότητα αριθμού μαθητών και αρτιότητα αθροίσματος βαθμών -- είναι (νομίζω) οι {4, 2, 1, 1, 0, 0}, {4, 2, 2, 1, 1, 0}, {4, 4, 2, 1, 1, 0}, {4, 3, 3, 2, 0, 0}, {4, 3, 3, 2, 2, 0}, {4, 3, 2, 1}, {4, 3, 3, 2, 1, 1}, {4, 4, 3, 2, 2, 1}, {4, 3, 1, 0}, {4, 3, 3, 1, 1, 0}, {4, 4, 3, 1, 0, 0}, {3, 2, 1, 0}, {3, 3, 2, 1, 1, 0}, {3, 2, 2, 1, 0, 0}.


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#8

Μη αναγνωσμένη δημοσίευση από gbaloglou » Παρ Δεκ 29, 2017 5:33 pm

gbaloglou έγραψε:
Πέμ Δεκ 28, 2017 11:00 pm
gbaloglou έγραψε:
Τρί Δεκ 26, 2017 11:56 pm
[Τα παραπάνω μπορεί να μην απέχουν και πολύ από μία 'εξαντλητική' απόδειξη της Εικασίας 7/11, θα προτιμούσα όμως κάτι πιο έξυπνο και αποτελεσματικό, που θα αποδείκνυε και τις προφανείς γενικεύσεις της (n+2 βαθμοί από τους 2n+1 βαθμούς {0, 1, ... , 2n}, για παράδειγμα).]
Για n=2 (ελάχιστο δυνατό) έχουμε ήδη το αντιπαράδειγμα {4, 4, 3, 1, 0, 0} ... που πάντως είναι το μόνο δυνατό στην κατηγορία του*.

... Είναι λοιπόν αρκετά λογικό να αναμένει κανείς ότι ένα αντιπαράδειγμα για n=5 (αρχική εικασία 7/11) είναι απλώς θέμα χρόνου και προσπάθειας ... χωρίς φυσικά να αποκλείεται η πιθανότητα εκπλήξεων, μεγαλύτερου 'βάθους' του προβλήματος, κλπ κλπ
Ήδη για n=3 και για n=4 βρίσκω ανάλογα αντιπαραδείγματα, {6, 6, 5, 2, 1, 0} και {8, 8, 7, 3, 2, 1, 1, 0} ;)


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7575
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Putnam 2017/A4

#9

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Δεκ 31, 2017 10:53 am

Δεν ισχύει η εικασία. Ένα αντιπαράδειγμα είναι το 0,1,2,7,8,9,9,10. Το συνολικό άθροισμα είναι 46 οπότε κάθε υποσύνολο θα έπρεπε να έχει άθροισμα 23. Κάθε υποσύνολο θα έχει 4 αριθμούς. Άρα ένα από αυτά θα έχει τουλάχιστον 3 από τους 7,8,9,9,10 και άρα άθροισμα τουλάχιστον 7+8+9 = 24, άτοπο.

Πιθανώς όμως η εικασία να ισχύει για μεγάλα n.


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#10

Μη αναγνωσμένη δημοσίευση από gbaloglou » Κυρ Δεκ 31, 2017 12:12 pm

Demetres έγραψε:
Κυρ Δεκ 31, 2017 10:53 am
Δεν ισχύει η εικασία. Ένα αντιπαράδειγμα είναι το 0,1,2,7,8,9,9,10. Το συνολικό άθροισμα είναι 46 οπότε κάθε υποσύνολο θα έπρεπε να έχει άθροισμα 23. Κάθε υποσύνολο θα έχει 4 αριθμούς. Άρα ένα από αυτά θα έχει τουλάχιστον 3 από τους 7,8,9,9,10 και άρα άθροισμα τουλάχιστον 7+8+9 = 24, άτοπο.

Πιθανώς όμως η εικασία να ισχύει για μεγάλα n.
Δημήτρη πολύ ωραία, έψαχνα και εγώ για κάποιο 'ανισόρροπο' αντιπαράδειγμα (με αριθμούς προς τα δύο άκρα, όπως αυτά που είχα δώσει για n=2, 3, 4) αλλά δεν το βρήκα ... και όσο δεν το έβρισκα ... τόσο υποπτευόμουν και εγώ κάτι καλό για μεγάλα n :)

[Αν θέλει να βοηθήσει κανείς που ξέρει δυο πράγματα από προγραμματισμό: αρκεί να εξεταστούν οι περιπτώσεις (για  n = 6, 7, ...) όπου n+2 από τους 2n+1 αριθμούς {0, 1, ..., 2n-1, 2n} εμφανίζονται μία ή δύο φορές ο καθένας (με τέτοιο τρόπο ώστε και το πλήθος και το άθροισμα τους να είναι άρτιο).]


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
panos1962
Δημοσιεύσεις: 3
Εγγραφή: Πέμ Φεβ 11, 2010 8:03 pm
Επικοινωνία:

Re: Putnam 2017/A4

#11

Μη αναγνωσμένη δημοσίευση από panos1962 » Πέμ Ιαν 11, 2018 6:37 pm

Για 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% :lol:


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#12

Μη αναγνωσμένη δημοσίευση από gbaloglou » Πέμ Ιαν 11, 2018 7:32 pm

Πολύ ενδιαφέρουσα, αν όχι πολλά υποσχόμενη, η μείωση των αντιπαραδειγμάτων ύστερα από το n=4 -- αγωνιούμε (και ευχαριστούμε)!


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Άβαταρ μέλους
panos1962
Δημοσιεύσεις: 3
Εγγραφή: Πέμ Φεβ 11, 2010 8:03 pm
Επικοινωνία:

Re: Putnam 2017/A4

#13

Μη αναγνωσμένη δημοσίευση από panos1962 » Παρ Ιαν 12, 2018 5:04 pm

Για n = 7 και n = 8 δεν βρέθηκε τίποτα. Η περίπτωση n = 9 θα είναι έτοιμη μάλλον αύριο αλλά μέχρι στιγμής δεν έχει δώσει κάτι.
Όπως ειπώθηκε παραπάνω, πιστεύω ότι όσο μεγαλώνει το n δίνονται περισσότερες δυνατότητες συνδυασμών και πιστεύω ότι δεν θα βρεθεί κάτι, αλλά η απόδειξη μου φαίνεται δύσκολη. Αυτό που έχει πλάκα είναι η συμμετρία που παρουσιάζουν οι περιπτώσεις 2, 3, 4, 5 και 6: 1, 2, 4, 2, 1


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2391
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2017/A4

#14

Μη αναγνωσμένη δημοσίευση από gbaloglou » Κυρ Ιαν 14, 2018 10:06 am

Όπως με πληροφορεί ο Πάνος, δεν υπάρχει αντιπαράδειγμα ούτε για n=9, από εκεί και πέρα η αναζήτηση χωρίς κάποιες νέες ιδέες θα ήταν απαγορευτικά χρονοβόρα.

Ας επισημάνω κάποια πράγματα για τα αντιπαραδείγματα που έχουμε βρει: ουσιαστικά δεν είναι δέκα αλλά επτά, καθώς κάποια από αυτά είναι 'δυϊκά' το ένα του άλλου, με την έννοια ότι αν το {Χi} είναι αντιπαράδειγμα τότε και το {2n-Χi} είναι αντιπαράδειγμα. (Βεβαίως κάποια αντιπαραδείγματα είναι δυϊκά του εαυτού τους, όπως το {4, 4, 3, 1, 0, 0} (για n=2) και το {12, 11, 11, 10, 9, 3, 2, 1, 1, 0} (για n=6).) Έτσι μπορούμε να πούμε ότι είχα ουσιαστικά βρει όλα τα αντιπαραδείγματα για n=3 (καθώς τα {6, 6, 5, 2, 1, 0} και {6, 5, 4, 1, 0, 0} είναι δυϊκά το ένα του άλλου), ενώ ο Δημήτρης είχε ουσιαστικά βρει όλα τα αντιπαραδείγματα για n=5 (καθώς τα {10, 9, 8, 3, 2, 1, 1, 0} και {10, 9, 9, 8, 7, 2, 1, 0} είναι δυϊκά το ένα του άλλου).

Δεν ξέρω πόσο θα βοηθούσε αυτό στην αναζήτηση (απόδειξης μη ύπαρξης) 'υψηλοτέρων' αντιπαραδειγμάτων με το χέρι, παραθέτω όμως εδώ (ακολουθώντας την βασική ιδέα της επίλυσης του προβλήματος Α4) τις αναλύσεις του καθενός από τα επτά αντιπαραδείγματα σε δύο υποομάδες με διαφορά αθροισμάτων 2 (παρατηρώντας ότι η χαμηλότερη υποομάδα δεν μπορεί να περιέχει μέλος της υψηλότερης υποομάδας μειωμένο κατά 1): (4+3+0)=(4+1+0)+2, (6+5+0)=(6+2+1)+2, (8+7+1+0)=(8+3+2+1)+2, (7+6+0)=(8+2+1)+2, (8+5+0)=(6+3+2)+2, (9+8+1+0)=(10+3+2+1)+2, (11+10+9+1+0)=(12+11+3+2+1)+2.


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

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