4 employees together bill 160 hours per week. Does that mean at least one bills more than 35 hours? or less than 35 hours? Box principle will help you find the answer:

00:28 Example 01

03:53 Box Principle Theory

06:00 Box Principle for k items

06:45 Testing option in Conclusion questions

09:45 Example 02

13:10 Summary

[TRANSCRIPT]

The 11th theory practice session of the problem-solving test course is devoted to the pigeon hole principle.

If we have one hundred sales managers in 33 cities, is it true that some cities have four or more sales managers? We will find it out in a few minutes.

Let us start with the following example. As always pause the video and try to solve the question on your own.

And then we’ll check. Based on the information in the Exhibit 1, which of the following statements is a valid conclusion?

Exhibit 1: duration and number of visitors for two most recent exhibitions at Fate. Duration and days; visitors: members and non-members. For two exhibitions: Cometti and Shining souls.

Let’s check all the options one by one. Option A: during the last hundred days, each day more people visit the Cometti exhibition then the Shining souls exhibition. Well this is actually something we don’t know, because we don’t know if the exhibitions took place at the same time or within the last hundred days? Option B: all non-member visitors to the exhibition also visited the Shining souls’ exhibition. Well this is easy to check and this is actually false, because of the number of visitor’s non-members to Cometti is about eleven points five thousand versus eight points five thousand at Shining souls.

So, all of them could not have visited shining souls.

And option B is false.

Option C: there was at least one day in which less than hundred people visited the Cometti exhibition.

The total number of visitors to the Cometti exhibition is twelve thousand six hundred and thirty-one and there were 120 days.

So, on average more than 100 people visited the exhibition every day, but this does not mean that there is at least one day in which less than 100 people visited the Cometti exhibition.

There might be such a day, for example, if on the first day only one person visited the exhibition, but that could also be no such days, if every day hundred people visited the exhibition and on the last day hundred plus everyone else 631 visited the exhibition, so in this case C is unknown. What about option D then?

There were days in which more than 90 people visited the Shining soul’s exhibition.

Let’s write it down: the total number of visitors to Shining soul’s exhibition was nine thousand six hundred and sixty-two and there were hundred days.

So, on average there were about 97 visitors per day which is more than 90.

It seems that option D is true, that necessarily there were days in which more than 90 people visited the Shining soul’s exhibition, because the average is more than 90.

But we can easily check that.

Suppose the opposite and suppose there were no days with more than 90 people. So that at most there were 90 people times hundred days equals nine thousand people.

But this is not true, because the actual number of visitors was nine thousand six hundred and sixty-two.

That means the assumption that there are less than 90 people each day is false.

Therefore, D is a valid conclusion.

There is a useful result for solving similar questions.

It’s called The Box principle. Its other names are “pigeon hole principle” and “Dirichlet principle”, after a Peter Dirichlet a German mathematician who created it.

It states that if we got N items and we wants to put all of them in M boxes such that N is greater than M than at least one box must contain more than one item.

The idea is intuitively simple: suppose we have three pigeons and two pigeonholes.

We want to put all three pigeons into two pigeon holes.

If you want to put all the three pigeons into two pigeon holes, we must accept that one pigeon hole will contain more than one pigeon.

The first two pigeons will occupy both pigeonholes, then the third one will have to join either of them.

The technique of proving this result calls “prove by contradiction” is just as important and applicable to PST as the result itself.

Once again, the results were trying to prove here is if you got N items and we want to put all of them into M boxes, such that N is greater than M, then at least one box must contain more than one item.

For starters, assume the opposite of what they’re trying to prove.

All N items are put into boxes and there are no boxes with more than one item.

Now we will show that this assumption leads to a contradiction and such has to be rejected. If there are no boxes with more than one item, the total number of items in the boxes at most one times M equals M. But the total number of items is N, which is greater than M. Therefore, N minus M items are still not of the boxes.

This contradicts the assumptions of our proof.

Therefore, the assumption is wrong and there is at least one box with more than one item. A general principle for K rather than 1 items per box also holds. If N greater than K times M items are put into boxes then at least one box must contain more than K items.

The intuition is the same as before.

Now we’re just distributing K items rather than 1. In the following example, we want to distribute 8 pigeons into two pigeonholes, three pigeons in each.

Then there must be at least one pigeon hole with more than two pigeons.

The proof by contradiction goes along the same lines as before.

Assume the contrary and conclude that this option is not viable.

How do we apply this knowledge then?

Suppose we need to test an option in the conclusion question. We tried to find situations in which the option is true and in which the option is false.

If both are found, then the validity of the option is unknown.

If just one example is found, we need to quickly make sure the other does not exist. To do that, we run mentally or quickly on a paper a prove by contradiction and establish that the assumption of the examples existence leads to a contradiction.

Here are a few examples.

20 Pigeon’s 10 pigeonholes.

The claim is that at least one hole has more than two Pigeon’s. We can show that there are examples when this is true.

If there is these a hole with 20 pigeons and all the remaining holes have just zero pigeons and then there is an example when this is false, when the pigeons are distributed equally among the pigeon holes. So, they validity of the claim is unknown.

Another example: 20 pigeons and nine pigeon holes.

The claim is, that there is at least one hole has more than two pigeons.

We can easily find an example when this is true, again put all the twenty pigeons into one pigeon hole and the remaining pigeon holes are empty.

But the problem is that now because there are just too few pigeonholes we cannot find a false example.

So, let’s prove that it does not exist.

Assume the opposite, namely that such a hole does not exist.

Let’s take the claim that at least one hole has to have more than two pigeons and prove it by contradiction.

So, I assume the opposite, namely that such a hole does not exist.

You get nine holes with no more than two pages each, hence you get no more than 18 pigeons which less than 20 pigeons are overall.

We get a contradiction.

So, the initial claim is true.

And other example: twenty pigeons, ten holes and the condition that there are no more than 2 pigeons per hole. The claim is that at least one hole has less than two pigeons.

We can easily find an example when this is false, when the pigeons are distributed equally. But the problem is that we cannot find the true example here, so let’s prove that this example does not exist?

So, let’s assume the opposite, namely that the desired hole exists and there are no more than 2 pigeons per hole.

Then this special hole has just one pigeon and all the remaining nine holes have two pigeons.

And in this case, there are just one plus two times nine equals 19 pigeons which is less than 20 pigeons and we get a contradiction.

That means our assumption is wrong and the desired whole does not exist.

The initial claim is false.

It’s high time for an official practice question on this topic. Pause the video now and try to find the answer yourself.

Based on the information provided by the Orlando manager regarding staffing at the Orlando landfill site, which of the following statements is a valid conclusion? From the text with three important facts.

At least one environmental specialist is required 24 hours a day seven day a week.

The NGI landfill site is the only such site in the city and it’s open from 9am to 5pm from Monday to Friday.

It employs four environmental specialists and eight other staff and then the total weekly employee cost is seven thousand dollars.

Let’s check all the options one by one.

Option A: one third of total employee cost for the landfill site is for environmental specialists.

The validity of this option is unknown because there is no information about the cost of one employee so we cannot calculate the share of total employee costs attributed to environmental specialists.

Option B: at least one environmental specialist must work more than 40 hours per week.

We know that at least one and environmental specialist must be present at the landfill site 24 hours a day and seven days a week so that a number of hours is 168 per week and we know that there are just four environmental specialists.

So that means that on average the environmental specialists have to work 42 hours.

However, it does not mean that every one of them works forty-two hours. But by the box principle it means that at least one environmental specialist must work more than 41 hours and more than 40 hours.

It is easy to check. Let’s assume the contrary.

Let’s assume that all four environmental specialists work not more than 40 hours.

In this case the total work hours would be not more than 160 which is less than 168. We get a contradiction here.

If we assume that all the environmental specialists work less than 40 hours per week their total work hours are 160 and there are eight hours in which none of the environmental specialists are present at the landfill site which contradicts our first condition.

Therefore at least one environmental specialist has to work more than 40 hours and option B is true. Option C: staff who are not environmental specialists do not work more than 40 hours per week.

This is something we do not know because we do not know the work hours of not environmental specialists.

We know the opening hours of the landfill sites but it’s a different thing.

Option D: the majority of the landfill sites employee cost is for staff who are not environmental specialists?

This is similar to option A and this is something we do not know because there is no information about the cost of one employee.

We know that the number of non-environmental specialists is greater than the number of environmental specialists but this is not enough to conclude that the cost on non-environmental specialists is higher than the cost on environmental specialists because environmental specialists might be more expensive.

Hence option D is unknown. Let us synthesize what we have learned today.

The box principle states that if M greater than KM items are put into boxes that at least one box must contain more than K items.

The intuitive result is easy proved by demonstrating a contradiction. The technique of demonstrating a contradiction is actually useful when we cannot find a false or a true example in a concluding question related to the box principle.

So much for the box principle. If you have any questions or comments please leave them below the video and I’ll be happy to reply.

Thanks for a time and see you later.