Mαθητές και θρανία

#1

(Κάνει και για Junior).

Σε ένα σχολείο υπάρχουν 100

μαθητές και

θρανία στα οποία μπορούν να κάτσουν δύο μαθητές την φορά. Οι μαθητές αποφάσισαν κάθε μέρα να κάθονται όπου θέλουν γιατί ο στάχος τους είναι, αργά ή γρήγορα, ο καθένας να κάτσει τουλάχιστον μία φορά στο ίδιο θρανίο με οποιονδήποτε άλλον. Εννοείται ότι αυτό θα τους πάρει τουλάχιστον

μέρες αφού ο καθένας θα κάτσει, αργά η γρήγορα, με

άλλους.

Δείξτε ότι οι

μέρες αρκούν για να πετύχουν τον στόχο τους.

(Εννοείται ότι το πρόβλημα γενικεύεται σε

μαθητές και

θρανία. Η λύση που έχω δεν αλλάζει είτε εργαστούμε με 100

μαθητές είτε γενικότερα).

#2

Επαναφορά.

Αν θέλουμε παράδειγμα (χωρίς να βοηθά στην λύση), αν είχαμε

μαθητές και

θρανία, χρειζόμαστε

μέρες για να καθίσουν όλοι με όλους. Μία διευθέτηση είναι ως εξής:

α' ημέρα: $1+6, \, 2+5, \, 3+4$

β' ημέρα: $5+6, \, 1+4, \, 2+3$

γ' ημέρα: $4+6, \, 3+5, \, 1+2$

δ' ημέρα: $3+6, \, 2+4, \, 1+5$

ε' ημέρα: $2+6, \, 1+3, \, 4+5$

Το πρόβλημα, στην περίπτωση των 100

μαθητών και

θρανίων, είναι να βρούμε έναν συστηματικό τρόπο να περιγράψουμε τα ζεύγη ανά ημέρα. Έχω έναν ωραίο και πονηρό τρόπο να το κάνω, με χρήση κάποιου γεωμετρικού σχήματος.

Nikitas K. · #3

Καλησπέρα,
Οι μέρες που θα χρειαστούν είναι το πηλίκο του
πλήθους των συνδυασμών

μαθητών μεγέθους

προς των αριθμό των

θρανίων ανά ημέρα

.

$\displaystyle \frac{\binom{2N}{2}}{N/d} = \frac{\frac{2N!}{2!(2N-2)!}}{N/d} = \frac{2N!d}{2!N(2N-2)!} = \frac{2N(2N-1)(2N-2)!d}{2N(2N-2)!}=(2N-1)d$

#4

Nikitas K. έγραψε: ↑
Τρί Δεκ 12, 2023 3:24 pm
Καλησπέρα,
Οι μέρες που θα χρειαστούν είναι το πηλίκο του
πλήθους των συνδυασμών μαθητών μεγέθους προς των αριθμό των θρανίων ανά ημέρα .

$\displaystyle \frac{\binom{2N}{2}}{N/d} = (2N-1) d$

Νικήτα, προσοχή.

Δεν είναι σωστή (δεν είναι πλήρης) η απάντηση. Λείπει η ουσία. Αυτό που γράφεις δείχνει ότι θέλουμε οπωσδήποτε 2N-1

μέρες (δεν γίνεται λιγότερες) για να πετύχουμε τον σκοπό μας (πράγμα που έδειξα με απλούστερη μέθοδο στο πρώτο μου ποστ). Το ερώτημα είναι αν μπορούμε να διευθετήσουμε τους μαθητές ανά ημέρα στα θρανία ώστε να μην χρειαστούμε περισσότερες από 2N-1

ημέρες.

#5

Δίνω την κατασκευή που έχει υπόψη ο Μιχάλης αλλά χωρίς να αναφερθώ στη γεωμετρία.

Ονομάζω τους μαθητής $x_0,x_1,x_2,\ldots,x_{99}$ . Την ημέρα

, όπου $k = 1,2,\ldots,99$ ο μαθητής x_0

κάθεται με τον μαθητή x_k

, ενώ οι μαθητές x_i,x_j

(με $i,j \neq 0,k$ ) κάθονται μαζί αν και μόνο αν $i+j \equiv 2k \bmod 99$ .

Παρατηρούμε ότι κάθε μέρα όντως δημιουργούμε

ζευγάρια. Το μόνο πιθανό πρόβλημα θα ήταν αν ο

καθόταν με τον εαυτό του αλλά αυτό δεν συμβαίνει διότι θα έπρεπε να είχαμε i=k

. Ο μαθητής

προφανώς έχει καθίσει με όλους κατά τη διάρκεια των

ημερών. Το ίδιο και ο μαθητής

για κάθε $i=1,2,\ldots,99$ αφού θα καθίσει με τον μαθητή $j \neq i$ τη μέρα $k \equiv 50(i+j) \bmod 99$ .

#6

Mihalis_Lambrou έγραψε: ↑
Κυρ Νοέμ 19, 2023 1:36 pm
Σε ένα σχολείο υπάρχουν μαθητές και θρανία στα οποία μπορούν να κάτσουν δύο μαθητές την φορά. Οι μαθητές αποφάσισαν κάθε μέρα να κάθονται όπου θέλουν γιατί ο στάχος τους είναι, αργά ή γρήγορα, ο καθένας να κάτσει τουλάχιστον μία φορά στο ίδιο θρανίο με οποιονδήποτε άλλον. Εννοείται ότι αυτό θα τους πάρει τουλάχιστον μέρες αφού ο καθένας θα κάτσει, αργά η γρήγορα, με άλλους.

Δείξτε ότι οι μέρες αρκούν για να πετύχουν τον στόχο τους.

(Εννοείται ότι το πρόβλημα γενικεύεται σε μαθητές και θρανία. Η λύση που έχω δεν αλλάζει είτε εργαστούμε με μαθητές είτε γενικότερα).

Ας δούμε και μία σχηματική περιγραφή της διευθέτησης των μαθητών στα θρανία. Για λόγους οικονομίας στο σχήμα θα το κάνω για 2N=10

(αντί

) αλλά είναι προφανές ότι η περιγραφή γενικεύεται σε οποιοδήποτε

. Επίσης θα είμαι λίγο αναλυτικός για να είναι η λύση προσιτή και στους αρχάριους Juniors.

Ζωγραφίσουμε έναν κύκλο και τοποθετούμε τον αριθμό

στο κέντρο του (στην γενική περίπτωση θα είναι ο

) και μετά τους

έως

(γενικά

έως

) στην περιφέρεια, σε κορυφές κανονικού 9-γώνου. Συνδέουμε τώρα τους κύκλους με κόκκινες γραμμές όπως δείχνει το αριστερό σχήμα. Τώρα τα ζεύγη των μαθητών, με οδηγό τα σχήματα, θα είναι

Την 1η μέρα εκείνα που συνδέονται με κόκκινη γραμμή, συγκεκριμένα $1+10, \, 2+9, \, 3+8, \, 4+7, \, 5+6$ .

Την 2η και κάθε επόμενη μέρα μετακινούμε τους αριθμούς της περιφέρειας κατά μία θέση δεξιόστροφα, ενώ ο αριθμός στο κέντρο μένει πάντα εκεί που είναι. Τα ζεύγη θα είναι πάλι όπως μας καθοδηγούν οι κόκκινες γραμμές. Συγκεκριμένα,

Την 2η μέρα θα είναι τα $9+10, \, 1+8, \, 2+7, \, 3+6, \, 4+5$ .

Την 3η μέρα θα είναι τα $8+10, \, 9+7, \, 1+6, \, 2+5, \, 3+4$ .

Την 4η μέρα θα είναι τα $7+10, \, 8+6, \, 9+5, \, 1+4, \, 2+3$ .

...

Την 9η μέρα θα είναι τα $2+10, \, 3+1, \, 4+9, \, 5+8, \, 6+7$ .

Είναι σαφές ότι όλοι κάθονται με όλους από μία φορά. Ας δούμε για παράδειγμα τον

. Το ταίρι του είναι διαδοχικά από μέρα σε μέρα

$10, \, 8, \, 6, \, 4, \, 2$ και μετά $9, \, 7, \, 5, \, 3$ (γενικά θα είναι οι $2N, \,2N-2,\, 2N-4,\, ...\, , \, 2$ και μετά $2N-1, \, 2N-3, \, ...\, , \, 3$ ), δηλαδή όλοι.

Tώρα, επειδή κάθε άλλος θα περάσει από την αρχική θέση του

και θα ακολουθήσει την ίδια διαδικασία με αυτόν αλλά ετεροχρονισμένη, θα καθίσει και ο ίδιος με όλους.

Αυτό τελειώνει την περιγραφή, η οποία προφανώς γενικεύεται.
.

abfx · #7

Καλησπέρα.

Παραθέτω σχετικό λήμμα της Wikipedia για όποιον ενδιαφέρεται.

Σημειώνω πως το παραπάνω πρόβλημα είναι ισοδύναμο με κατασκευή τουρνουά όπου "όλοι παίζουν με όλους" και οι αγώνες
πραγματοποιούνται σε 2N-1

αγωνιστικές.

Mαθητές και θρανία

Mαθητές και θρανία

Re: Mαθητές και θρανία

Re: Mαθητές και θρανία

Re: Mαθητές και θρανία

Re: Mαθητές και θρανία

Re: Mαθητές και θρανία

Re: Mαθητές και θρανία

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