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 KZread: 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.
Пікірлер: 248
"No! Everybody has a friend here." You're so inspirational :,)
1:10 me on every discrete math test
@matthewfrancis5414
7 жыл бұрын
ahahaha :)
@KT-pe8gw
6 жыл бұрын
hehehe
@jamespottex5197
4 жыл бұрын
1:11
@irishjade03
2 жыл бұрын
Funnyyyyy
@princetonjoshua3028
2 жыл бұрын
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
Two of the best teachers at KZread you and organic chemistry tutor
@pongtawat26
Жыл бұрын
YES ORGANIC CHEMISTRY TEACHER ONGGGG
What an explanation. Principle look like nothing at first, but it's applications are mindblowing.
It’s like he knew what exactly went on in my lecture and did a great job! Amazing!
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
5 жыл бұрын
@Siyovaxsh En-sipad-zid-ana then it's not a friendship by the definition in this example
@bigphatballllz
4 жыл бұрын
I love you❤️
@perfectinstructions9005
4 жыл бұрын
woahh
@kaushikraj4324
2 жыл бұрын
Say max no of friends can be n-2 then
@runzsh
2 жыл бұрын
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.
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.
Great way of teaching sir. I learnt this topic in just 20 min. Tysm.
Really well made video! Thanks for the intuitive and combinatorial proofs!
Good explanation of this easy-difficult concept. Many thanks :)
The way you said okay in whole video made me smile the whole time.
I really really love you. You make my life so much easier. Thank you so much!
@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!
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!! :)
I love your videos man. Super helpful!
Finally understood PIGEONHOLE PRINCIPLE applications Thanks a lot 🙏
thanks , you have made it easy and fast to under stand pigeonhole principle
Thankyou so much for this wonderful explanation.
Nice explanation! Great job!
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 :)
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
8 жыл бұрын
+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.
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.
Great stuff, helps me understand it more in Specialist Math.
@user-vs2xj7vl5w
4 жыл бұрын
@Ibrahim Najm Well I'm not going reveal my school but doing it in Queensland, Australia.
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.
no dislikes and that tells you how good you explain. really great explanation.
@Daniel-aaaaa
2 жыл бұрын
2021 and still no dislikes!
@dbuc4671
Жыл бұрын
@@Daniel-aaaaa wow its almost as if youtube totally did not remove the dislike feature
@Daniel-aaaaa
Жыл бұрын
@@dbuc4671 KZread got rid of the feature a year ago? Time flies by quick.
I love your handwriting!
great video, thanks,
Hahaha man you are really frickin funny. I'm loving these videos
"Maybe one of them is a serial killer" lol
thank you so much , it really helpful for me
@AtotheR
4 жыл бұрын
you're welcome :)
Thank you. You helped me
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
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
5 жыл бұрын
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
4 жыл бұрын
@@htmlguy88 dont get your explaination can you explain in more detail
@shubh_1999
3 жыл бұрын
@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.
thank you!
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.
Pogchamp, thanks bro really cool vid
fantastic video
Should we always try to maintain even distribution of pigeons in pigeonholes until we have extras or can we load up one with many
Thank you sir
lol i choked when he said serial killer
thank u so much
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
discrete maths amazes me
2022 and still excellent 🙏🙏🙏
"Oh crap what do I do with this extra one" really nice video thanks
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!
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.
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
4 жыл бұрын
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
Thank you
thank you
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 :(
excellent
Thanks
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?
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
4 жыл бұрын
Well yes the vertical and horizontal distance is at max 2, but the furthest distance is the diagonal, which is 2sqrt2 or sqrt8
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?
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.
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
5 жыл бұрын
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
5 жыл бұрын
i also think that there must be a misunderstanding somewhere. i doubt we can fit more than 13 dots inside such square.
Hi, what do you mean by picking 11 numbers?
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
8 жыл бұрын
+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
8 жыл бұрын
+TheTrevTutor naw really
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
9 жыл бұрын
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
9 жыл бұрын
TheTrevTutor For Part b) Total seats are 2400 and students 2000. So 400 seats are empty. So (400/30) gives 14. Thhaannkk yoou :D
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.
Shouldn't it be 367 because we would have to consider the possibility of a leap year
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
5 жыл бұрын
this is the basis of the proof of Fermat's little theorem.
Prove completely that in any set of three (not necessarily distinct) integers, there will always be two whose sum is even.
@htmlguy88
5 жыл бұрын
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.
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
6 жыл бұрын
ceiling, not floor.
Sir i tried square grid problem , i think i need to discuss this with you
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.👍
@princebargujar63
4 жыл бұрын
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.
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.
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.
Único brasileiro aqui, orgulho bem! Hello friends english speakers, i'm programmer, and i will not fix your pc.
@walkiriamachado21
3 жыл бұрын
não é mais o único kk
@thetrevtutor why do you use sqrt of 8 for the distance between two dots?
@htmlguy88
5 жыл бұрын
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.
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
7 жыл бұрын
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
6 жыл бұрын
that leads to solution of answer 13...
@JoJo777890
5 жыл бұрын
Yeah, then the answer will be 13...
Ur voice is really nice butt my mam tell us any other formulae to solve this prblm soo i'm little bit confused
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.
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?
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
5 жыл бұрын
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.
00:02 Understanding sum and product rule in permutations 01:47 Finding ways to choose one circle and one rectangle 04:09 Understanding permutations through examples 06:35 Calculating permutations using the sum and product rule 10:15 Understanding Permutation and its application in forming combinations. 14:37 Explanation of permutation with example 17:19 Understanding permutation rules between 100 and 1000 19:05 Finding 3-digit odd numbers with certain rules
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
5 жыл бұрын
6
6:57 lol
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
8 жыл бұрын
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
8 жыл бұрын
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!:)
I died at 7:00 HAHAHA
The last problem is really confusing me. How do you fit more than 13 in that box?
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
You da man
post the link of answered question in the comment inorder to access it. thank you.:-)
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
5 жыл бұрын
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
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.
this vid legit look like a troll for the first minute lmfao
it looks easy but it's so hard for me to understand maybe just me TT
@yt-popo3089
3 жыл бұрын
Same bro Lol 😂
@amrnrsyada
3 жыл бұрын
@@yt-popo3089 you can do it 💪💪 haha
An ice cream shop serves 4 flavors of ice cream. 7 friends show up, and each of them orders a cone with 2 different flavors. Prove that there must be at least 2 people who ordered the same combination of flavors.
@htmlguy88
5 жыл бұрын
4*3/2 = 6
Something about your cadence reminds me of nightvale and i dont know why
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
7 жыл бұрын
(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
7 жыл бұрын
thank you tutor
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
5 жыл бұрын
No, because there are n people present.
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.
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
5 жыл бұрын
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.
Prove that there is a natural number n such that the sum 1+3+3^2+...+3^n is divisible by 1000.
@seckinkarakoc7767
4 жыл бұрын
Help!🙏🏽
It's so obvious but gets complicated when you extend it.
best
In case of the birthdays of 366 people problem it is not necessary that at least 2 of them have same birthdays. The 366th person can have birthday on 29th February.