3
$\begingroup$

Each student writes down his/her name, surname, age and birthplace on a card in a class. After that, these cards (each containing four entries) are collected and examined. The following observations are made:

  • No matter which four cards are picked, at least two of them contains an identical entry.
  • There are at most three people in the group having: the same name.
  • There are at most three people in the group having the same surname.
  • There are at most three people in the group having the same age.
  • There are at most three people in the group having the same birthplace.

So,

What is the possible maximum number of students in the class?

$\endgroup$
  • 1
    $\begingroup$ does identical entry mean that name, surname, age and birthplace all same or just any two same? $\endgroup$ – Shahriar Mahmud Sajid Aug 7 '18 at 9:35
  • $\begingroup$ @ShahriarMahmudSajid each name, surname, age and birthplace is an entry. $\endgroup$ – Oray Aug 7 '18 at 11:21
3
$\begingroup$

I think the answer is

$27$ students

Consider the following set of students' cards

1. Name: John, Surname: Smith, Age: 15, Birthplace: Bogota
2. Name: John, Surname: Jones, Age: 16 , Birthplace: Podgorica
3. Name: John, Surname: Brown, Age: 17, Birthplace: Ljubljana
4. Name: Mary, Surname: Smith , Age: 17, Birthplace: Podgorica
5. Name: Mary, Surname: Jones , Age: 15 , Birthplace: Ljubljana
6. Name: Mary, Surname: Brown, Age: 16, Birthplace: Bogota
7. Name: Susan, Surname: Smith , Age: 16 , Birthplace: Ljubljana
8. Name: Susan, Surname: Brown , Age: 15 , Birthplace: Podgorica
9. Name: Susan, Surname: Jones , Age: 17, Birthplace: Bogota

Notice that

Any two cards selected from this set will have an identical entry.

Now

Suppose we have two more sets of nine students with the same structure but different entries. Then two cards selected from the same set of nine will have an identical entry. If we select four cards arbitrarily from the entire group then, by the Pigeonhole Principle, at least two will come from the same set of nine and have an identical entry.

Proof that this is the maximum.

Suppose that there are $28$ students in the group. It is not hard to see that we would be able to pick three students from the group that do not share an identical entry, call them $A$, $B$ and $C$. Then, there are at most two other students that share each of the properties name, surname, age and birthplace with each of $A$, $B$ and $C$. This means there are at most $24$ students who have something in common with $A$, $B$ and $C$ and that there is at least one student with nothing in common with any of them.

$\endgroup$
0
$\begingroup$

I think it is

9 students

because

If we make 4 groups of 3 students (12 in total), with each group having one entry in common, we can choose one student/card from each group. So that is not working.

But luckily we can decide that in one group of students (e.g. the group with same names), each of the three students has another entry common with another group of students (e.g. one student in the 'same names' group has the same surname as people in the 'same surnames' group, and so on), we can't choose 4 students without two of them saving a common entry. Unfortunately now we have too much students in 3 of the groups, so we have to remove 3 students, leaving we with 9 students in the class.

Here is a diagram

diagram of the answer

I think there must be a better way of explaining this and actually proving that this is the largest number of students, but this is how I can make it sound reasonable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.