IMC 2013/1/3

Eukleidis · #1

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

#2

Σίγουρα κάθε μαθητής πρέπει να πάει σε τουλάχιστον τρεις εκδρομές αφού αλλιώς θα πάει εκδρομή μαζί το πολύ 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: Αν

άρτιος τότε χωρίζουμε τους μαθητές σε τέσσερις ομάδες A,B,C,D

μεγέθους

η κάθε μία και κάνουμε τις εκδρομές AB,AC,AD,BC,BD,CD

.

Περίπτωση 2: Αν

περιττός, έστω $1,2,\ldots,6$ οι πρώτοι έξι μαθητές. Χωρίζουμε τους υπόλοιπους (αν υπάρχουν) σε τέσσερις ομάδες A,B,C,D

μεγέθους

η κάθε μία και κάνουμε τις εκδρομές 123AB,145AC,126AD,245BC,346BD,356CD

.

IMC 2013/1/3

IMC 2013/1/3

Re: IMC 2013/1/3

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