PIGEONHOLE PRINCIPLE - DISCRETE MATHEMATICS
Вставка
- Опубліковано 14 жов 2024
- We introduce the pigeonhole principle, an important proof technique.
#DiscreteMath #Mathematics #Proofs #Pigeonhole
Visit our website: bit.ly/1zBPlvm
Subscribe on UA-cam: 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.
![[Discrete Mathematics] Pigeonhole Principle Examples](http://i.ytimg.com/vi/pPuvnD4PYNE/mqdefault.jpg)
![[Discrete Mathematics] Pigeonhole Principle Examples](/img/tr.png)
"No! Everybody has a friend here." You're so inspirational :,)
Two of the best teachers at UA-cam you and organic chemistry tutor
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.
I love you❤️
woahh
Say max no of friends can be n-2 then
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.
6 years late, but great comment
1:10 me on every discrete math test
ahahaha :)
hehehe
1:11
Funnyyyyy
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
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.
@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.
That's what I got as well!
Great way of teaching sir. I learnt this topic in just 20 min. Tysm.
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.
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.
@@htmlguy88 dont get your explaination can you explain in more detail
@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.
The way you said okay in whole video made me smile the whole time.
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
Good explanation of this easy-difficult concept. Many thanks :)
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!
+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.
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 :)
no dislikes and that tells you how good you explain. really great explanation.
2021 and still no dislikes!
@@Daniel-aaaaa wow its almost as if youtube totally did not remove the dislike feature
@@dbuc4671 UA-cam got rid of the feature a year ago? Time flies by quick.
Really well made video! Thanks for the intuitive and combinatorial proofs!
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.
I love your handwriting!
"Maybe one of them is a serial killer" lol
Hi, what do you mean by picking 11 numbers?
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.
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
"Oh crap what do I do with this extra one" really nice video thanks
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?
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...
i also think that there must be a misunderstanding somewhere. i doubt we can fit more than 13 dots inside such square.
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?
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.
+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.
+TheTrevTutor naw really
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?
hav e you gotten an solution yet, cuz i might have the answer bud!
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.
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
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!!
Well yes the vertical and horizontal distance is at max 2, but the furthest distance is the diagonal, which is 2sqrt2 or sqrt8
I really really love you. You make my life so much easier. Thank you so much!
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?
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.
Finally understood PIGEONHOLE PRINCIPLE applications
Thanks a lot 🙏
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!! :)
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.
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.
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.
TheTrevTutor For Part b) Total seats are 2400 and students 2000. So 400 seats are empty. So (400/30) gives 14. Thhaannkk yoou :D
discrete maths amazes me
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.
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?
Should we always try to maintain even distribution of pigeons in pigeonholes until we have extras or can we load up one with many
Shouldn't it be 367 because we would have to consider the possibility of a leap year
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.
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?
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 :)
that leads to solution of answer 13...
Yeah, then the answer will be 13...
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?
6
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.👍
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.
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.
this is the basis of the proof of Fermat's little theorem.
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!
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.
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!:)
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.
Great stuff, helps me understand it more in Specialist Math.
@Ibrahim Najm Well I'm not going reveal my school but doing it in Queensland, Australia.
Thankyou so much for this wonderful explanation.
Thank you. You helped me
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
Nice explanation! Great job!
@thetrevtutor why do you use sqrt of 8 for the distance between two dots?
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.
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 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.
Sir i tried square grid problem , i think i need to discuss this with you
thanks , you have made it easy and fast to under stand pigeonhole principle
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.
2022 and still excellent 🙏🙏🙏
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 )
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.
I love your videos man. Super helpful!
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?
ceiling, not floor.
The last problem is really confusing me. How do you fit more than 13 in that box?
Thank you sir
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
I invented a calendar that makes more sense
If you're born on a leap day (ex. November 30), your birthday will be either the day or the day after.
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
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
Thank you
lol i choked when he said serial killer
Prove completely that in any set of three (not necessarily distinct) integers, there will always be two
whose sum is even.
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.
thank you so much , it really helpful for me
you're welcome :)
Pogchamp, thanks bro really cool vid
thank you
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.
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 :(
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..
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.
excellent
fantastic video
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.
Thanks
the last second example is not that clear, let me try to add some explanation: in the worst case, you would pick the first ten numbers from each possible sets (like in 1,20 you only take 1 or 20) and then the eleventh number will be picked from all the sets you have picked before, so you are guranted that there must be at least one set is matched to the sum of 21
BTW I think a way of interpretating the pigion hole principle is thinking about the worse case, how does the worse case look like.
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?
+Zubair Syed i agree. this question is a real fucker. never understood it.
+atribecalled solitude ya i am still struggling with this fucker.
is it hard man or is it easy
also
Consider any five points in the interior of a square
of side 1. Show that two of these points are no more than √
1
2
apart. Can you
partition the square into 4 such regions?
thank you
+Ome Pius Literally the last question I did /2.
Ur voice is really nice butt my mam tell us any other formulae to solve this prblm soo i'm little bit confused
great video, thanks,
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.
(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.
thank you tutor
Hahaha man you are really frickin funny. I'm loving these videos
A teacher gives a multiple choice quiz that has 3 questions, each with six possible answers: a, b, c, d, e, and f. What is the minimum number of students that must be in the class in order to guarantee that at least 3 answer sheets will be identical? Give your answer using the pigeonhole principle.
344?
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?
No, because there are n people present.
Prove that there is a natural number n such that the sum 1+3+3^2+...+3^n is divisible by 1000.
Help!🙏🏽
I know this is late, but it would have been nice if you did the type of problem where it’s like: someone has a certain number of hours/weeks, prove that he must do some action (such as studying) such that the sum of the hours spent doing the action on each day will equal some number, where he must spend at least one hour a day
How to solve the following problem using pigeonhole principle?
If eleven integers are chosen from the set {1, 2, 3, ..., 20}, then show that one of them must be a multiple of another.
You could use the following ten containers:
{1, 2, 4, 8, 16} {3, 9, 18} {5, 15} {6, 12} {7, 14} {10, 20} {11} {13} {17} {19}
Because you will select eleven unique integers, the pigeonhole principle says you must take at least two from one of these containers. You can't take two from a container with only one number, so you have to pick your two from one of the first six containers. But it's easy to see that if you pick two integers from any of those containers, the larger one will be a multiple of the smaller one.
1,2,3,5,7,11,13,17,19 are all the primes under 20 and the number 1. There are only nine of them. every natural number is 1 prime or composite, with a lowest prime factor less than the sqrt. Since all primes and 1 have been used up two of the numbers must be compisite, it then follows that they are divisible by the primes .
Único brasileiro aqui, orgulho bem! Hello friends english speakers, i'm programmer, and i will not fix your pc.
não é mais o único kk
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.
4*3/2 = 6
thank u so much
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
At 8:24, this question should say distinct numbers, or else I'm just going to pick 1 (11) times.
it cannot be 0 friends not because you are assuming it. There are n people, say guy Z has n-1 friends, that means he is friends with everyone, which includes the last guy to be sorted. That means the last guy cannot have 0 friends AND must have at least 1 friend whom in this case is guy Z