A question on pigeonhole principle?

132 Views Asked by At

I came across the following question which I could solve using a "trial-and-error" approach. However, is there a systematic way of solving it using the pigeonhole principle?

"When cleaning her children’s room, a mother found 9 socks. In a group of any 4 of the socks at least two belonged to the same child. In a group of any 5 of the socks no more than 3 had the same owner. How many children are there in the room and how many socks belong to each child?"

1

There are 1 best solutions below

0
On

In a group of any 4 of the socks at least two belonged to the same child.

This means the number of children has to be 3 or less. Otherwise, each socks could belong to a different child.

In a group of any 5 of the socks no more than 3 had the same owner.

This implies the number of children has to be 2 or more. Or else, all 5 socks will belong to the same child.

So at this stage, we know there are 2 or 3 children.

Now if there were 2 children, one of them must have 5 or more socks. In that case, the second condition would be violated.

So, there are 3 children. (One part of the question answered.)

Each child must have 3 socks. Or else at least one will have 4 or more socks and the first case will be violated.

So, there are 3 children and each child has 3 socks.