[maths extension 1] need help with pigeonhole principle question

[u/NEPTRI0N]

[u/NEPTRI0N]

I did (6C3)/13 = 1.5 and then put a but i just realised how dumb that is

[u/not-just-yeti → u/NEPTRI0N]

6C3 = 20, no? Ah yes, 20/13 is 1.5+. But that’s the inverse of the fraction you want.

Anyway, I don’t see an immediate way to verify a correct answer, but I can rule three of the choices out w/ a little thought.

[u/Alkalannar]

1. There are 20 sets of 3 subjects each. More than 13, so this isn't necessarily true.

2. Can't think of an easy counterexample. Let's see about the others and come back if we have to.

3. Everyone could choose the same set. This ain't necessarily so.

4. There are 39 subjects chosen overall. Divide by 6, that's 6 R 3, so the most you can say is at least 7 students have one subject in common.

So, since A, C, and D are all not necessarily true, B must be necessarily true.

[u/captainAwesomePants → u/Alkalannar]

Does this count as a proof via pigeonhole principle?

[u/Alkalannar → u/captainAwesomePants]

The counterexamples to A and D both use Pigeonhole.

The counterexample to C is just based on reading the question.

That leaves B as the only answer.

So, yes.

[u/AcromMcLain]

B. There are 6c2=15 subject pairs (pidgeonholes) and a total of 3*13 students associated with a subject pair (pidgeons). Furthermore the same student has to be associated to three distinct subject pairs which means that at least one of those 15 subject pairs house 3 students.

[u/Least-Telephone6359 → u/AcromMcLain]

I'm looking for how to prove b Is true, what is the step from 39 subject pairs which proves it is true?

[u/AcromMcLain → u/Least-Telephone6359]

39/15 is more than 2 so at least one of the 15 pairs corresponds with three students. Note also that 39 is three times the students because each student has 3 pairs of subjects.

The way one should think about the pidgeonhole principle in general is that if there are two sets A and B with finite cardinality such that |A|/|B| is a rational number q then given any function from A to B one can find an element of B (a pidgeonhole) such that its preimage through that function has a cardinality that is >=q.

In this specific case you can think of A as the set of students and about f as a special triple multifunction (so not really a function) such that each element of A is associated to three distinct elements of B which would be the set of subject pairs.

[u/[deleted]]

[u/ThunkAsDrinklePeep → u/[deleted]]

A: you mean 6C3?

Expanding upon D: 7 students can can choose objects A B and C while the other six choose objects D, E, and F.

[u/Least-Telephone6359 → u/ThunkAsDrinklePeep]

Do you know a nice way to prove b is true? 6c2 is 15 which is over 13 so doesn't prove in itself.. then each of the people have to had chosen another subject.. there is only 6 subjects to choose from so it lowers the scenarios of 2 matching to 15-13/6? Kinda thing.. I know this isn't fully correct proof haha but wondering if you know it nicely

[u/Least-Telephone6359 → u/[deleted]]

You are right, but 6 choose 3 is 20, not 120

And the description for d is weird to me.. just simpler way would be using the same logic as c..6 people can choose the first 3 subjects and 7 people can choose the last 3, which is less than 8

Edited.. icrealised maybe we aren't meant to just say the correct answer in this sub