IMC 2013/1/3

Συντονιστής: Demetres

Eukleidis
Δημοσιεύσεις: 669
Εγγραφή: Τετ Ιούλ 01, 2009 9:55 pm
Τοποθεσία: Θεσσαλονίκη

IMC 2013/1/3

#1

Μη αναγνωσμένη δημοσίευση από Eukleidis » Πέμ Αύγ 08, 2013 4:20 pm

Σε ένα σχολείο υπάρχουν \displaystyle{2n} μαθητές \displaystyle{\left( {n \in {\Bbb N},n \geqslant 2} \right)}. Κάθε εβδομάδα \displaystyle{n} μαθητές πάνε εκδρομή. Μετά από αρκετές εκδρομές η ακόλουθη συνθήκη ικανοποιήθηκε: κάθε δύο μαθητές ήταν μαζί σε τουλάχιστον μία εκδρομή. Ποιός είναι ο ελάχιστος αριθμός εκδρομών ώστε να ικανοποιείται αυτή η συνθήκη;


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

Re: IMC 2013/1/3

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Αύγ 08, 2013 7:46 pm

Σίγουρα κάθε μαθητής πρέπει να πάει σε τουλάχιστον τρεις εκδρομές αφού αλλιώς θα πάει εκδρομή μαζί το πολύ 2(n-1) = 2n-2 < 2n-1 άλλους μαθητές και άρα θα υπάρχει μαθητής που δεν θα πάει εκδρομή μαζί του.

Αν λοιπόν x_1,\ldots,x_{2n} οι μαθητές και E_1,\ldots,E_r οι εκδρομές έχουμε rn = \sum_i|E_i| \geqslant 3(2n) και άρα r \geqslant 6, δηλαδή πρέπει να γίνουν τουλάχιστον 6 εκδρομές. Θα δείξουμε ότι έξι εκδρομές αρκούν

Περίπτωση 1: Αν n άρτιος τότε χωρίζουμε τους μαθητές σε τέσσερις ομάδες A,B,C,D μεγέθους n/2 η κάθε μία και κάνουμε τις εκδρομές AB,AC,AD,BC,BD,CD.

Περίπτωση 2: Αν n περιττός, έστω 1,2,\ldots,6 οι πρώτοι έξι μαθητές. Χωρίζουμε τους υπόλοιπους (αν υπάρχουν) σε τέσσερις ομάδες A,B,C,D μεγέθους (n-3)/2 η κάθε μία και κάνουμε τις εκδρομές 123AB,145AC,126AD,245BC,346BD,356CD.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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