Putnam 2017/A4

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

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7520
Εγγραφή: Δευ Ιαν 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
Επιμελητής
Δημοσιεύσεις: 2375
Εγγραφή: Παρ Φεβ 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
Γενικός Συντονιστής
Δημοσιεύσεις: 7520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Putnam 2017/A4

#3

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

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


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2375
Εγγραφή: Παρ Φεβ 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 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Απάντηση

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

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

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