Παρακολούθηση μαθημάτων

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

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

Παρακολούθηση μαθημάτων

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Μάιος 26, 2017 12:18 pm

Σε ένα καλοκαιρινό σχολείο παραδίδονται 7 μαθήματα. Κάθε μαθητής παρακολούθησε τουλάχιστον ένα μάθημα και κάθε μάθημα παρακολουθήθηκε από τουλάχιστον 40 μαθητές. Γνωρίζουμε ότι για κάθε δύο μαθήματα υπάρχουν το πολύ 9 μαθητές οι οποίοι παρακολούθησαν και τα δύο.

Να δειχθεί ότι στο σχολείο έλαβαν μέρος τουλάχιστον 120 μαθητές.



Λέξεις Κλειδιά:
silouan
Επιμελητής
Δημοσιεύσεις: 1183
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Παρακολούθηση μαθημάτων

#2

Μη αναγνωσμένη δημοσίευση από silouan » Παρ Μάιος 26, 2017 8:43 pm

Αυτή είναι μια κλασική άσκηση που εντάσσεται στο διπλομέτρημα. Πρώτα όμως φτιάχνουμε έναν πίνακα με τα μαθήματα και τους μαθητές.
Στα κελιά αυτού του πίνακα βάζουμε 1 ή 0 ανάλογα αν ο μαθητής παρακολουθεί το μάθημα ή όχι.
Έστω n το πλήθος των μαθητών.
Θα μετρήσουμε με δύο τρόπους τις τριάδες (μαθητής, μάθημα, μάθημα), όπου ο μαθητής παρακολουθεί και τα δύο μαθήματα. Έστω A το πλήθος τους.
Αν σταθεροποιήσουμε ένα ζεύγος μαθημάτων, τότε από την εκφώνηση έχουμε το πολύ 9 τριάδες. Αφού λοιπόν τα ζεύγη είναι \binom{7}{2}=21 θα έχουμε ότι A\leq 9\cdot 21=189.
Επιπλέον οι τριάδες αυτές είναι εκεί που συμφωνούν δύο γραμμές του πίνακα. Αν x_i είναι το πλήθος των άσσων στην i γραμμή, τότε έχουμε \displaystyle A=\sum\binom{x_i}{2}=\sum\frac{x_i^2-x_i}{2}.

Από C-S έχουμε n\left(\sum x_i^2\right)\geq S^2 όπου S=\sum x_i. Ξέρουμε ότι το πλήθος των άσσων σε μία γραμμή είναι τουλάχιστον 40.
Οπότε S\geq 40.

Συνοψίζοντας:

189\geq A\geq\frac{S^2-nS}{2n} οπότε n\geq\frac{S^2}{2\cdot 189+S} και επειδή S\geq 40 λόγω της μονοτονίας θα έχουμε n\geq 120.

Πολύ παρόμοιο είναι αυτό: https://artofproblemsolving.com/communi ... 503p124458


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

Re: Παρακολούθηση μαθημάτων

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Μάιος 28, 2017 12:07 am

silouan έγραψε:Αυτή είναι μια κλασική άσκηση που εντάσσεται στο διπλομέτρημα.
Ακριβώς έτσι. (Υπάρχει όμως ένα τυπογραφικό αφού είναι S \geqslant 280.) Την πήρα από εδώ.


Απάντηση

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

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

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