PIGEONHOLE PRINCIPLE - DISCRETE MATHEMATICS

We introduce the pigeonhole principle, an important proof technique.
#DiscreteMath #Mathematics #Proofs #Pigeonhole
Visit our website: bit.ly/1zBPlvm
Subscribe on KZbin: bit.ly/1vWiRxW
-Playlists-
Discrete Mathematics 1: • Discrete Math (Sets, L...
Discrete Mathematics 2: • Discrete Math (Countin...
-Recommended Textbooks-
Discrete and Combinatorial Mathematics (Grimaldi): amzn.to/2T0iC53
Discrete Mathematics (Johnsonbaugh): amzn.to/2Hh7H41
Discrete Mathematics and Its Applications (Rosen): amzn.to/3lUgrMI
Book of Proof (Hammack): amzn.to/35eEbVg
Like us on Facebook: on. 1vWwDRc
Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.

[@omkars764]

"No! Everybody has a friend here." You're so inspirational :,)

[@Weknowjoey]

1:10 me on every discrete math test

[@matthewfrancis5414]

ahahaha :)

[@KT-pe8gw]

hehehe

[@jamespottex5197]

1:11

[@irishjade03]

Funnyyyyy

[@princetonjoshua3028]

You probably dont care but does anyone know a tool to log back into an instagram account?? I somehow lost the password. I would love any tricks you can offer me

[@raghavkhanna6056]

Two of the best teachers at KZbin you and organic chemistry tutor

[@pongtawat26]

YES ORGANIC CHEMISTRY TEACHER ONGGGG

[@PalashBansal]

What an explanation. Principle look like nothing at first, but it's applications are mindblowing.

[@FifthDoctorsCelery]

The friends one still works if you allow people to have 0 friends. Then people can have {0, ..., n-1} friends. From here, either two people have the same number of friends (so the proof is done), or each person has a different number, which means there is one person in each box. However, this is a contradiction, because it says that one person has 0 friends and one has n-1 (the maximum number, since you can't be friends with yourself). It's impossible to have one friendless person and one who is friends with everybody, so either there is nobody in the friendless box or there is nobody in the n-1 box. Either way, there are now n-1 total boxes for n people, so two people must share a box.

[@CriticalPressure1]

@Siyovaxsh En-sipad-zid-ana then it's not a friendship by the definition in this example

[@bigphatballllz]

I love you❤️

[@perfectinstructions9005]

woahh

[@kaushikraj4324]

Say max no of friends can be n-2 then

[@runzsh]

I assume you are considering a person out of n having zero friends, then max friends anyone could be with is n-2. It makes total number of boxes to be filled n-1.

[@APDesignFXP]

It’s like he knew what exactly went on in my lecture and did a great job! Amazing!

[@rickelmonoggin]

I like the technique of 'reverse engineering' the problem. It's good to see how math problems are actually put together. It really helped my understanding.

[@adarshnathaniel8520]

Great way of teaching sir. I learnt this topic in just 20 min. Tysm.

[@wintermute032]

Really well made video! Thanks for the intuitive and combinatorial proofs!

[@lucychix79]

Good explanation of this easy-difficult concept. Many thanks :)

[@froggyq1112]

The way you said okay in whole video made me smile the whole time.

[@soramakizushi]

I really really love you. You make my life so much easier. Thank you so much!

[@shubh_1999]

@TheTrevTutor In the last example, the pigeonhole isn't anywhere in the 2x2 squares but the holes are just one of the opposite diagonal points on the 2x2 square. So essentially, we have 13 pockets or pigeonholes and we just require 14 dots to violate the sqrt(8) distance rule.

[@olivershao3983]

That's what I got as well!

[@cup1den303]

This was great, I was searching for info on it for about an hour and didn’t understand a thing, but i understand it now, thanks!! :)

[@sanjanasharma5629]

Finally understood PIGEONHOLE PRINCIPLE applications Thanks a lot 🙏

[@kanikabagree1084]

Thankyou so much for this wonderful explanation.

[@swapnilmahapatra2218]

thanks , you have made it easy and fast to under stand pigeonhole principle

[@jeremiahnji6]

I love your videos man. Super helpful!

[@sienienudzi8472]

I have A set with 50 natural numbers, each of them is >500 and less than 1000. Prove that in A exists 2 disjoint 2 element subsets with equal sum.

[@intensivemathematics5943]

Nice explanation! Great job!

[@azazel7505]

bro is the savior of many, protector of college students, bringer of high math grades ty trevtutor I will write my exam score if I can find this again :)

[@mangomilkshakelol]

I love your handwriting!

[@jonnathannickolai7827]

awesome video ! just a side note, if it's a leap year it could be the case that 2 people do not have the same birthday.

[@haomintian6815]

Hi, I love your videos! And really appreciate! I have a question here that I am not sure if I should use Pigeonhole Principle: Would you please please please help? Generate, list, and count: the number of distinct quadruples (a,b,c,d) such that: a,b,c,d∈1..9 10∤ (a+b+c+d) and order matters and repetition is not allowed.

[@jesus4life271]

hi Trevor I have a discrete math final coming up soon do you have any tips/advice ?thank you! your videos are awesome thank you thank you thank you for posting them up!

[@Trevtutor]

+Mitch Amp Probably make sure you're able to do all the homework questions assigned in your course (if there were any) and have a general understanding of how to do the harder questions in whatever text you're using. That goes for pretty much every math course out there.

[@jsndftdgs9372]

Thank you. You helped me

[@kaushikdr]

Okay, I have a question on the last problem - I am getting that you can at most have only 13 dots that are at most sqrt(8) away from each other at the same time. Your idea of 16 that you can have 1 dot on each square is not correct, I feel! If I could send you a picture, I would but it seems that adjacent diagonals reuse the same diagonals

[@user-vs2xj7vl5w]

Great stuff, helps me understand it more in Specialist Math.

[@user-vs2xj7vl5w]

@Ibrahim Najm Well I'm not going reveal my school but doing it in Queensland, Australia.

[@madhusaivemulamada4577]

no dislikes and that tells you how good you explain. really great explanation.

[@Daniel-aaaaa]

2021 and still no dislikes!

[@dbuc4671]

@@Daniel-aaaaa wow its almost as if youtube totally did not remove the dislike feature

[@Daniel-aaaaa]

@@dbuc4671 KZbin got rid of the feature a year ago? Time flies by quick.

[@emindenizozkan5158]

great video, thanks,

[@princeplayz8374]

discrete maths amazes me

[@oneinabillion654]

Should we always try to maintain even distribution of pigeons in pigeonholes until we have extras or can we load up one with many

[@desychandra2313]

thank you so much , it really helpful for me

[@AtotheR]

you're welcome :)

[@michaellai327]

can you help me with a question: By using the Pigeonhole Principle, show that if six distinct integers are chosen between 1 and 150 inclusive, some two of them must differ by most 29

[@chamikajayasinghe994]

Thank you sir

[@rajendrakumardangwal8084]

Hey TrevTheTutor In that Square grid problem only 13 such points can be inserted. How can you fit 16 points that are sqrt(8) distance apart?? Please help.

[@htmlguy88]

I think the point is that you can show a quite low upper bound exists, simply by breaking the plane down into shapes that are easy to compute with, and the pigeonhole principle.

[@HimanshuSingh-tu7ik]

@@htmlguy88 dont get your explaination can you explain in more detail

[@shubh_1999]

@Evan Huang yeah right. U can place exactly 13 dots perfectly and the 14th dot is less than sqrt(8) apart from one of the dots.

[@-a5624]

fantastic video

[@hungloe86]

thank you!

[@anishbusviah3612]

HELP! I don't get the dots in squares one. If you use 16 dots aren't all the dots < 8^.5 cm apart? So shouldn't the minimum dots be less than 16? I'm confused, can you clarify?

[@kpiegg2744]

Thank you

[@user-bu8mg7uq3s]

thank you

[@adityachettri8819]

excellent

[@judoexpert2057]

Pogchamp, thanks bro really cool vid

[@martinhawrylkiewicz2025]

I really like your explanation of the Pigeonhole Principle. I'm working on a little math problem with natural numbers and a bit stuck. If a natural number, then there are two distinct natural numbers k, l such that a^k - a^l is divisible by 10. I am thinking of finding a function that maps N into set of possible remainders {0, 1, 2,...9} as f(n) = (a^n)/10...am I on the right track?

[@tarwizegaming8447]

hav e you gotten an solution yet, cuz i might have the answer bud!

[@moratupalawenieka8413]

Thanks

[@haileydirks3559]

Hi, what do you mean by picking 11 numbers?

[@SachinSharma-yk1iu]

2022 and still excellent 🙏🙏🙏

[@merakiday1628]

"Maybe one of them is a serial killer" lol

[@pupkai8658]

so for the s = 1-20 I did (|s|/(|(s|/2)+1)) == 20/((20/10)+1)==20/11 == 1.1818 CEIl == 2, is that an approach I can take if I'm taking an exam? I haven't finished the video at 12:04 currently: Also side note, you're a life saver because I can't understand my prof. when he goes through these examples in class but you can actually explain these things.

[@deepakkalal3790]

let n be odd positive integers. If i1,i2.......iN is a permutation of 1,2....n prove that (1-i1)(2-i2)....(n-in) is an even integer.

[@madhusaivemulamada4577]

we have a set of 11 different integers and pick 8 different integers from the set. prove that with the correct operations we can always obtain a number that is a multiple of 1155. can you please explain this. that would be helpful. thanks.

[@factsverse9957]

I can't help much, but take the prime factorization of 1155 first. 1155 = 5 × 231 231 = 16^2 - 5^2 = 5 × 21 × 11 1155 = 3 × 5 × 7 × 11

[@fruitpunch4338]

8:10 it's still not clear to me which number represent the number of pigeon and number of hole, also could someone explain to me what the 11 numbers we picked represents.

[@AnkitKumar-on1ny]

Sir i tried square grid problem , i think i need to discuss this with you

[@sup7270]

one question i would like you to explain is show that for every integer n, there is a multiple of n that has only 0s and 1s in its decimal expansion. thank you :(

[@jasonspence]

at 12:40, I feel like that's an unnecessarily large bound... I tried to fill in as many dots as I could, and only got 13. I couldn't figure out how to get the 14th dot in without two dots being closer than sqr(8) units. Is there a reason for this smaller number?

[@haribahadur1673]

yeah me too... practically you cannot go beyond 13 and have min no for the distance to be less than root of 8 Everyone else is stuck with zero friend analogy common...

[@LR-fs5ps]

i also think that there must be a misunderstanding somewhere. i doubt we can fit more than 13 dots inside such square.

[@charanpuvvada2772]

There are 120 boxes, each of which contains any number of tennis balls ranging from minimum 130 to maximum 155. The maximum number of boxes containing same number of balls is at least?

[@aldolunabueno2634]

I think the last question is wrong because you're puting the dots in the grid with each cell of size 2 by 2cm. You will get dots separeted by 2cm, less than 2*sqrt(2). I have other approche. Insted of dots, put circles of radius sqrt(2), and expand your 8x8 square to an square of side (8+2*sqrt(2). If you can put 17 circles in this square but no more than that, you are done. But I think it's not posible. I was only able to put 13 circles. The problem is really more complex than you think.

[@lizzmccue]

Hahaha man you are really frickin funny. I'm loving these videos

[@philipvankampen3394]

the problem with the last example is this: we are trying to fit round pegs in square holes. The vertical and horizontal distance between dots is 2, not 2*sqrt(2). We need to fill the grid with circles whose origins are contained within the grid and along the edges of the other circles. This problem, I believe, is much more complex than is supposed in the video. I love your video series!!

[@factsverse9957]

Well yes the vertical and horizontal distance is at max 2, but the furthest distance is the diagonal, which is 2sqrt2 or sqrt8

[@saqlainsajid4067]

did any of you notice that "the minimum number of dots required to place two dots within √8cm of each other is 2? not 17? If you're saying that if we want to fill the board in a way that no dots are within √8cm of each other except two then what's the number of dots required to do that?

[@ptwell7589]

15:12 Hi, I was just wondering where you got ceiling n/16 from , if there was a dot in every box, wouldnt there be two dots within less than root8 distance already?

[@TonyTongWA]

No, there is a possible permutation where all the dots are on the intersections between the lines, and the distance is exactly root8, not less than it. The qn asks for less than root8 :)

[@ghanshamchandel1854]

that leads to solution of answer 13...

[@JoJo777890]

Yeah, then the answer will be 13...

[@Farah-vi2cj]

@thetrevtutor why do you use sqrt of 8 for the distance between two dots?

[@htmlguy88]

because sqrt(8) is the diagonal of a 2 by 2 square. this is what the original square was broken into when 16 subsquares were drawn.

[@matthewanderson96]

Let X be a set containing 12 distinct integers. By considering a suitable function, f: X --> {0, 1, ......, 8} and using the pigeonhole principle, show that there are two members of X whose difference is divisible by 9.

[@Trevtutor]

+Matthew Anderson So f is a function from Z to Z/9Z. What is {0, 1, ..., 8} representing? The remainder of two numbers divided by 9. Hope that helps.

[@matthewanderson96]

+TheTrevTutor naw really

[@gravitycube430]

"Oh crap what do I do with this extra one" really nice video thanks

[@odar9729]

How many container units on a container unit in a container unit and exactly how much Twix can be in each door if I only eat 3 with 50 containers.

[@naturallyweird661]

Shouldn't it be 367 because we would have to consider the possibility of a leap year

[@Lexhanson]

The last problem is really confusing me. How do you fit more than 13 in that box?

[@williampeters71]

there is an element in the sequence 7,77,777,7777,...that is divisible by 2003. from walk through combinatorics I just cannot understand the authors explanation W.Peters

[@smritiprasad5708]

Floor function states that for [x], the value will always be equal or less than x. However when you computed [11/10], you computed 2 instead of 1 (according to the definition). Why?

[@Trevtutor]

ceiling, not floor.

[@AnjaliKumari-rb6qb]

Ur voice is really nice butt my mam tell us any other formulae to solve this prblm soo i'm little bit confused

[@moamenmohamed7578]

hi sir can you help me with this problem it says (show that if the first 10 positive integers are placed around a circle in any order there exist three integers in consecutive locations around the circle that have a sum greater than or equal 17 )

[@htmlguy88]

it comes down to 10,9,8,and 7 all needing at least one number less than 5 next to them without being within 2 of each other for at least 3 of them.

[@dingsiewyap5847]

Hi, can you help me with this question? I just don't get why is PHP so directed by us. As in for the following question, i just purposely arrange the set to have number divisible by 11. instead of randomly arrange into {1,7} but {1,12}. Thank you! Prove that, given any 12 natural numbers, we can choose two of them such that their difference is divisible by 11. A proof requires a general, algebraic argument; not just an example. Hint: Consider the remainders mod 11. So i did, {1,12}, {2,11}, {3,10}, {4,9}, {5,8} and {6,7}. but what if i just arrange them to be {1,7}, (2,6} and so on. Your advise is appreciated!

[@Trevtutor]

ding siew yap You can arrange them like that, but then it wouldn't capture the idea of the proof. In your question, you want to prove that the difference between two randomly chosen numbers is 11. So instead of "arranging numbers to be convenient", we can think more abstractly and say "what possible remainders mod 11 can we have?". Then you see you can have 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, totalling to 11 different choices. These 11 choices come from the difference of two numbers mod 11. When you arrange these numbers now, you have to take in this consideration so you can arrange them in a way that's convenient and helps you. If you arrange them otherwise, then it becomes more difficult to prove and you'll need a new method. In reality, it doesn't matter how you pair these numbers. But, if you pair them another way, then the proof is not clear at all.

[@dingsiewyap5847]

Thank you so much for your explanation, i have solved the question using n1 = q1 x 11 +r , n2=q2x11+r method, and i got n1-n2=11(q1-q2) hence at least 2 of the numbers have a difference which is divisible by 11. Appreciate you prompt reply, really hepful!:)

[@faisalalzaman2915]

Hiii. Can you solve for me this question: 30 Buses are to be used to transport 2000 Students. Each bus has 80 seats. Assume one seat per passenger a) Prove that one of the buses will carry at least 67 Passengers. b) Prove that one of the buses will have at least 14 empty seats.

[@Trevtutor]

Faisal Alzaman a.) By extended pigeonhole principle, we can see that there are 2000 students, and 30 buses. So if we take ceil(2000/30), what do we get? b.) Think about the reverse of that situation.

[@faisalalzaman2915]

TheTrevTutor For Part b) Total seats are 2400 and students 2000. So 400 seats are empty. So (400/30) gives 14. Thhaannkk yoou :D

[@sriharanhariharan8565]

Prove that, given any 12 natural numbers, we can choose two of them such that their dierence is divisible by 11. A proof requires a general, algebraic argument; not just an example. Hint: Consider the remainders mod 11.

[@htmlguy88]

this is the basis of the proof of Fermat's little theorem.

[@madhusaivemulamada4577]

post the link of answered question in the comment inorder to access it. thank you.:-)

[@marjannovotni7449]

Here is a simple example of 0 friends and you will see it works for n people. Say 4 friends. A B C D D does not have a friend A is friends with B and C Therefore there are 3 different options for number of friends 0 or 1 or 2 friends. So 4 people (pigeons) 3 options for friends (pigeonholes) By PHP it works. So you must consider this case for this question.

[@lenoci5]

Prove completely that in any set of three (not necessarily distinct) integers, there will always be two whose sum is even.

[@htmlguy88]

Take odd + odd=even; even+even=even; and odd+even=odd; . By pigeonhole principle at least two of the three integers will have same parity (odd or even). Therefore, there are at least 2 odd, or at least 2 even. These sum to an even number by the three rules above.

[@zachrowson1076]

The point of this video wasn’t to optimally fit points into squares, but on the last problem I don’t think the answer is 17. It is 14. Someone correct me if I’m wrong.

[@sahethi7190]

lol i choked when he said serial killer

[@Rivful]

best

[@wendyavalos4238]

I have a final coming up. I am given 10 topics and told that 5 of these will be on the exam. What is the least amount of topics have to study to ensure that I will see in the exam?

[@Ashish-zs5by]

6

[@kojopolo4588]

I have a question please.. if there are 12 chairs in a row, and 9 people sitting, price that there are three consecutive chairs occupied

[@theash307]

make sets of 3 consecutive numbers such as ....label the chairs as 1,2,3.....12 and make sets like {1,2,3} , {2,3,4} ,{3,4,5}........{10,11,12}......You'll get exactly 10 sets and you have 9 pigeonholes with 10 pigeons ....so you get your answer as 2 by dividing that...hope this helps

[@yancy8570]

People who are born in a leap year and on the 29th of February disliked this video... Just kidding 😊 great video and it helped me a lot with preparing for math olympiad. Thankyou so much

[@FebruaryHas30Days]

I invented a calendar that makes more sense

[@FebruaryHas30Days]

If you're born on a leap day (ex. November 30), your birthday will be either the day or the day after.

[@aniya._.b4702]

Why we use only ceiling functions in this??why not floor function can be used?plzzz help me out; too much confused of it. P.S I like the way you teach,It has helped me alot.👍

[@princebargujar4805]

because you cant distribute the one item in more then two holes in real life ...that's why we consider the rounds of next nearest integer..that is the next item is go in one of the filled holes.

[@bassnashoe]

You da man

[@studiant3004]

Único brasileiro aqui, orgulho bem! Hello friends english speakers, i'm programmer, and i will not fix your pc.

[@walkiriamachado21]

não é mais o único kk

[@moodman6426]

I don't get the example at 11:30. How is this an abstract idea at all? If you have 20 numbers 1 through 20, and you pick 11, it is more than obvious that the sum of 2 numbers must be 21 or higher. You can just pick the 11 smallest numbers possible (base case), and if the sum of 21 is possible with 2 of those (10,11), than you've proved it for every case.

[@semirumutkurt6635]

7:23 shouldn't it be 367 days? since in a leap year there is 366 days. so if the year is 2020 then there is possibility that no one will share the same birthday

[@gokhanozeloglu]

In picking 11 numbers question, I got confused on the question. I understood that we are picking 10 numbers from 1 to 10. So, the last number must be seleceted from 11 to 20. It is OK. So, let's say, we picked 14 as a last number. Also, if we choose 7 and 14, the sum is 21. But, we can choose 2 and 14. And their sum is 16. So, not 21. I mean, there is not guarante that the sum is always 21. Maybe, I did not understand question clearly. But if you help me about this, everything will be clear for me..

[@htmlguy88]

basically, in the numbers 1 to 20, you have only 10 sums using 2 distinct numbers, that add up to 21. picking 1 number from each of these sums, isn't enough to pick 11 numbers. Therefore picking both numbers from at least 1 of the sums that sum to 21 is forced.

[@ghty102]

6:57 lol

[@cesareborgia9259]

I don’t get it. Each person can have up to (n-1) friends, but we don’t have a choice of n, unless we’re considering that the person can be his own friend. So isn’t it (n-1) people to be fitted in (n-1) containers?

[@htmlguy88]

No, because there are n people present.

[@syntheticpolymer620]

Something about your cadence reminds me of nightvale and i dont know why

[@zubairsyed5570]

Q. Show that in any group of 6 people there are either three mutual friends or three mutual strangers? Can you please tell me how to do this?

[@PrivacyKingdoms]

+Zubair Syed i agree. this question is a real fucker. never understood it.

[@zubairsyed5570]

+atribecalled solitude ya i am still struggling with this fucker.

[@kushwanthkapa2041]

we can also write 0 to n-2..................... :);

[@seckinkarakoc7767]

Prove that there is a natural number n such that the sum 1+3+3^2+...+3^n is divisible by 1000.

[@seckinkarakoc7767]

Help!🙏🏽

[@stupidwisconsin]

The birthday one is false due to the fact that there is a possibility the that one people was born on the leap day. Just felt like that was a needed input.

[@thecode2028]

why did u took 2:2

[@Mish580]

if you have 17 way more of the dots will be in less than root8

[@raynarts5977]

#discrete

[@mejurymabhegedhe7728]

Each of 25 pupils must choose 2 tasks from 5 possible tasks.use the pigeon principle to show that at least 3 will choose the same two tasks.

[@Trevtutor]

(5 choose 2) = ?? You have 25 people, so take the ceiling of 25/(5 choose 2), since there are only (5 choose 2) ways to pick 2 tasks, then you're assigning 25 people overall to each of those.

[@mejurymabhegedhe7728]

thank you tutor