Distinct Friendship Counts Puzzle in a Small Middle School

Γρίφος Φιλίας σε Μικρό Γυμνάσιο

Σε ένα πολύ μικρό γυμνάσιο υπάρχουν n μαθητές της ΣΤ΄ τάξης και n μαθητές της Ζ΄ τάξης. Κάθε μαθητής της ΣΤ΄ τάξης είναι φίλος με ακριβώς 6 μαθητές της Ζ΄ τάξης. Κάθε μαθητής της Ζ΄ τάξης είναι φίλος με τουλάχιστον έναν μαθητή της ΣΤ΄ τάξης, και κανένας δύο μαθητές της Ζ΄ τάξης δεν έχουν τον ίδιο αριθμό φίλων από τη ΣΤ΄. Ποια είναι η τιμή του \(n\);

(A) 11    (B) 12    (C) 13    (D) 14    (E) 15

Λύση

Υπάρχουν \(n\) μαθητές ΣΤ΄ και \(n\) μαθητές Ζ΄. Κάθε μαθητής ΣΤ΄ έχει 6 φίλους Ζ΄, άρα ο συνολικός αριθμός «δεσμών φιλίας» είναι

\(6n.\)

Από την πλευρά της Ζ΄: κάθε μαθητής Ζ΄ έχει κάποιον αριθμό φίλων από τη ΣΤ΄, όλοι αυτοί οι αριθμοί είναι διαφορετικοί και τουλάχιστον 1, και φυσικά δεν μπορούν να ξεπερνούν το \(n\) (τόσοι είναι οι μαθητές της ΣΤ΄).

Άρα οι βαθμοί φιλίας των μαθητών της Ζ΄ είναι τα \(n\) διακεκριμένα ακέραια από 1 μέχρι το πολύ \(n\). Ο μόνος τρόπος να έχουμε \(n\) διαφορετικούς θετικούς ακέραιους ≤ \(n\) είναι να είναι:

\(1, 2, 3, \dots, n.\)

Το άθροισμά τους είναι:

\(1 + 2 + \dots + n = \dfrac{n(n+1)}{2}.\)

Αυτό το άθροισμα πρέπει να είναι ίσο με το σύνολο των δεσμών φιλίας, δηλαδή \(6n\):

\(\dfrac{n(n+1)}{2} = 6n.\)

Για \(n > 0\) απλοποιούμε με \(n\):

\(\dfrac{n+1}{2} = 6 \Rightarrow n+1 = 12 \Rightarrow n = 11.\)

Άρα \(n = 11\). Σωστή απάντηση: (A).

Friendship Counts Puzzle in a Small Middle School

At a very small middle school, there are n sixth graders and n seventh graders. Every sixth grader is friends with exactly six seventh graders. Every seventh grader is friends with at least one sixth grader, and no two seventh graders have the same number of friends among the sixth graders. What is the value of \(n\)?

(A) 11    (B) 12    (C) 13    (D) 14    (E) 15

Solution

There are \(n\) sixth graders and \(n\) seventh graders. Each sixth grader has 6 friends among the seventh graders, so the total number of friendship edges is

\(6n.\)

From the seventh graders’ side: each seventh grader has a positive number of sixth-grade friends, all these numbers are distinct, and none can exceed \(n\) (there are only \(n\) sixth graders).

Hence the friendship counts for the seventh graders must be the integers

\(1, 2, 3, \dots, n.\)

Their sum is

\(1 + 2 + \dots + n = \dfrac{n(n+1)}{2}.\)

This must equal the total number of edges \(6n\):

\(\dfrac{n(n+1)}{2} = 6n.\)

For \(n > 0\) divide by \(n\):

\(\dfrac{n+1}{2} = 6 \Rightarrow n+1 = 12 \Rightarrow n = 11.\)

Thus \(n = 11\). Correct answer: (A).