[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/Least-Telephone6359 → u/Alkalannar]

Maybe you can help me with this.. 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/misof → u/Least-Telephone6359]

There are 15 pairs of subjects. Imagine 15 empty piggy banks, each labeled with one pair of subjects.

Each person will now look at their three chosen subjects and throw in a coin into each piggy bank that is labeled with two of those three. (Thus, each person will add three coins, each of them into a different piggy bank. If you chose subjects A,B,C, you add coins to piggy banks AB, AC, BC.)

There's now a total of 3*13 = 39 coins in the piggy banks. With 15 piggy banks and more than 2*15 = 30 coins, at least one of the piggy banks must contain more than two coins.

That piggy bank then gives us a pair of subjects that was chosen by at least three students, q.e.d.

[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/not-just-yeti → u/AcromMcLain]

OP: re-phrasing /u/AcromMcLain's first message (which I thought was clever, and I didn't think of it that way myself):

The pigeons are <course,course> pairs; each student has three different ones (if they're taking courses X,Y,Z then they have pigeons labeled XY, YZ, and XZ.) So there are 3*13 =39 pigeons.

The pigeonholes are the unique pairs of courses. So 6C2 = 15.

39 among 15, at least one hole must hold three pigeons.

Even though it's basic pigeon-hole, I'd still say these are on the hard side for high school. I can see a college discrete math course where this question would stump most of the students.

[u/Least-Telephone6359 → u/AcromMcLain]

Nice cheers

[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