PIGEONHOLE PRINCIPLE - DISCRETE MATHEMATICS
Вставка
- Опубліковано 10 гру 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
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
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
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!
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!
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 :)
7:17 With 0 friends the same rule applies, because if someone has 0 friends then nobody can have n-1 friends and vice versa, so it’s either from 1 to n-1 or 0 to n-2 at most giving n-1 options for n people
Great way of teaching sir. I learnt this topic in just 20 min. Tysm.
The way you said okay in whole video made me smile the whole time.
I'm sick of discrete
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.
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
Good explanation of this easy-difficult concept. Many thanks :)
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.
Finally understood PIGEONHOLE PRINCIPLE applications
Thanks a lot 🙏
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.
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
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.
I love your handwriting!
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!! :)
"Maybe one of them is a serial killer" lol
Really well made video! Thanks for the intuitive and combinatorial proofs!
I really really love you. You make my life so much easier. Thank you so much!
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.
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
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
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.
thanks , you have made it easy and fast to under stand pigeonhole principle
"Oh crap what do I do with this extra one" really nice video thanks
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.
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.
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...
discrete maths amazes me
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
Thankyou so much for this wonderful explanation.
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.
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.
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
Hi, what do you mean by picking 11 numbers?
Nice explanation! Great job!
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
I love your videos man. Super helpful!
lol i choked when he said serial killer
2022 and still excellent 🙏🙏🙏
thank you so much , it really helpful for me
you're welcome :)
Thank you. You helped me
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!
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.
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.
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
Pogchamp, thanks bro really cool vid
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.
Shouldn't it be 367 because we would have to consider the possibility of a leap year
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.
fantastic video
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.
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.
Ú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
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?
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?
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.
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.
Thank you
great video, thanks,
thank you
Hahaha man you are really frickin funny. I'm loving these videos
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
@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.
excellent
Thank you sir
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.
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
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!:)
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 :(
Sir i tried square grid problem , i think i need to discuss this with you
dude the first question aren't u supposed to mention that everyone has at least 1 friend
A lot of people have already answered this in the comments, but the theorem still holds if someone has 0 friends.
I guess a better way to word it is that there are n people, and each of them can either know 0,1,2,...n-1 other people.
By contradiction of the theorem, we say that each of the n people know a different number of people.
So each of the containers is filled. That is, there's a person who knows exactly 0 people, another who knows exactly 1, another who knows exactly 2, ..., and one who knows exactly n-1 people.
Since we have someone who knows 0 people, then we can't have someone else who knows all n-1 other people (because knowing someone is a reciprocal relationship here). Now the person who we thought knew n-1 people actually knows a different number of people; our only other choices are 0, 1, 2, ..., n-2. If we pick any other number, then we'll have 2 people knowing the same number of people. This contradicts our original assumption that every person knows a different number of people. So the pigeonhole principle holds.
Basically, for n people, there are only n-1 containers because you can't have someone know 0 people and another person know n-1 people. Your containers will correspond to either knowing 0, 1, 2, ...n-2 people or 1, 2, 3, ...n-1 people.
Don't worry, no one taking discrete math satisfies this property
I think the easiest way to explain why it still works is because if one person has no friends it's as though he wasn't part of the graph to begin with. Then you have k=n-1 and since n supposedly holds for any positive integer then it'll hold for any value of k as well.
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.
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
thank you!
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
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
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.
At 8:24, this question should say distinct numbers, or else I'm just going to pick 1 (11) times.
Thanks
is it hard man or is it easy
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 u so much
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.
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.
The last problem is really confusing me. How do you fit more than 13 in that box?
Prove that there is a natural number n such that the sum 1+3+3^2+...+3^n is divisible by 1000.
Help!🙏🏽
Ur voice is really nice butt my mam tell us any other formulae to solve this prblm soo i'm little bit confused
it looks easy but it's so hard for me to understand maybe just me TT
Same bro Lol 😂
@@yt-popo3089 you can do it 💪💪 haha
7:03 "No, everybody has a friend here!" That does not complete the proof. Instead you should have considered two cases, the first case has been proven, the second case is the case where there exists a person who has no friends (0), so the maximum number of friends is n-2. By PHP, there must be at least 2 people with the same number of friends. This finishes the proof.
flex
this vid legit look like a troll for the first minute lmfao
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.