PIGEONHOLE PRINCIPLE - DISCRETE MATHEMATICS
Vložit
- čas přidán 30. 12. 2014
- We introduce the pigeonhole principle, an important proof technique.
#DiscreteMath #Mathematics #Proofs #Pigeonhole
Visit our website: bit.ly/1zBPlvm
Subscribe on CZcams: 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 :,)
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
Two of the best teachers at CZcams 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.
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.
@Siyovaxsh En-sipad-zid-ana then it's not a friendship by the definition in this example
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.
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!
Really well made video! Thanks for the intuitive and combinatorial proofs!
Great way of teaching sir. I learnt this topic in just 20 min. Tysm.
I really really love you. You make my life so much easier. Thank you so much!
Good explanation of this easy-difficult concept. Many thanks :)
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!! :)
The way you said okay in whole video made me smile the whole time.
I love your videos man. Super helpful!
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.
thanks , you have made it easy and fast to under stand pigeonhole principle
Thankyou so much for this wonderful explanation.
Finally understood PIGEONHOLE PRINCIPLE applications
Thanks a lot 🙏
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 :)
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
Nice explanation! Great job!
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.
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.
@Ibrahim Najm Well I'm not going reveal my school but doing it in Queensland, Australia.
Should we always try to maintain even distribution of pigeons in pigeonholes until we have extras or can we load up one with many
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.
"Maybe one of them is a serial killer" lol
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.
great video, thanks,
thank you!
Thank you. You helped me
I love your handwriting!
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
thank you so much , it really helpful for me
you're welcome :)
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!
Thank you sir
Hahaha man you are really frickin funny. I'm loving these videos
thank u so much
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 CZcams got rid of the feature a year ago? Time flies by quick.
thank you
Thank you
discrete maths amazes me
fantastic video
Pogchamp, thanks bro really cool vid
excellent
lol i choked when he said serial killer
Thanks
"Oh crap what do I do with this extra one" really nice video thanks
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 :(
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
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.
Sir i tried square grid problem , i think i need to discuss this with you
Hi, what do you mean by picking 11 numbers?
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?
@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.
2022 and still excellent 🙏🙏🙏
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.
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
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...
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
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.
post the link of answered question in the comment inorder to access it.
thank you.:-)
Shouldn't it be 367 because we would have to consider the possibility of a leap year
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?
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.
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 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.
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?
Ur voice is really nice butt my mam tell us any other formulae to solve this prblm soo i'm little bit confused
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.
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.
The last problem is really confusing me. How do you fit more than 13 in that box?
You da man
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.
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 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!:)
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.
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
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
best
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 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
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.
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
Ú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
this vid legit look like a troll for the first minute lmfao
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
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.
Something about your cadence reminds me of nightvale and i dont know why
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.
why did u took 2:2
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
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.
5000th like
6:57 lol
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.
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
if you have 17 way more of the dots will be in less than root8