[Discrete Mathematics] Pigeonhole Principle Examples
Vložit
- čas přidán 8. 09. 2024
- We do a couple pigeonhole problems, including a visual problem that requires a triangle.
LIKE AND SHARE THE VIDEO IF IT HELPED!
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
Submit your questions on Reddit: bit.ly/1GwZZrP
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.
First example answer why: There are 26 letters in the english alphabet, if everyone has a unique first letter and last letter initial combined, that means for every first letter initial (there are 26 possible letters), there are 26 last letters that can go with it, so by probability, there are 26 x 26 unique possibilities. Adding + 1 means that the next person will guaranteed to have a repeating initial since all unique initials are taken.
Second example answer why: Split each edge into 1/3, connect the points of each edge split into 1/3, you see there are 9 regions, those are 9 triangles with equal length 1/3 or less. Count every point of every edge (including the middle point), there are 10 points, so now you have 10 points that can make triangles with length 1/3 or less.
This is helpful! Thank you
Well, first notice that there are 26^2 different combinations of initials one can make. All of these
initials are distinct. But we want to have two people with the same initials. So we must have that
26^2+1 is the number of seats filled in (the 1 was added for the repetition of a pair of initials. For instance, AB already "appeared"
in all of the 26^2 combinations of 26 letters and initials. So we must have that since an another initial
say, AB, is repeated, we have now 26^2+1 combinations). So the answer is that 26^2+1 seats must be filled
in order to ensure that two people have the same initials. For if 26^2 seats are filled, then there are
676 seats filled with distinct people with distinct initials. So one needs to fill 26^2+1=677 seats to ensure
two people seated have the same initials. This is because by the pigeonhole principle, (26^2+1)/26=2. So 2 people
now have the same initials.
@@allenpetkov4184 i did ceiling(n/676) = 2 //n = 677
@@robertjimenez5608 Yeah I did the same thing but, I felt it more intuitive to mention (26^2)+1
@@allenpetkov4184 thanks for the thorough explanation, it enlightened me
These video's are so under appreciated. Thank you so much Trev.
So for problem 2, just drawing the triangle is plenty proof to answer the question? the answer was a bit vague there.
Combining the 9 smaller triangles and the given 10 points I guess it is enough to use the [10/9] = 2 to prove.
I see! With the initials question, we find all the ways to arrange first and last initials. As the result we find must be unique, one more attempt at combining the alphabets guarantees a repetition. I didn’t know that unrestricted arrangements can be used this way to solve a pigeonhole problem. Thank you so much❤
What do you mean by unrestricted arrangements here? That term doesn't make sense
@@050138 unrestricted arrangement refers to making selection from a sample space that allows for repetition. E.g. choosing 1 card from 52 cards, then choose again after returning the first chosen card to the deck. We calculate these cases by making (52) to the power of selection. E.g. if I choose from 52 cards twice, I’ll do 52 to the power of 2.
I don't understand why in the first example you add 1. You should add one if you've done 26*25 -> all different combinations.
Lets assume that there're 3 letters in the alphabet, a b c, so if I have two places _ _ if I can place any of the 3 letters in the first place and any of the 3 in the second i would get 3*3, so -> aa,ab,ac, ba,bb,bc, ca,cb,cc -> we already have aa bb cc.
But if we choose any of the 3 letters for the first place, and we discard it, we are left with 2 letters, ensuring there's never 2 same letters: (3=abc) a -> 2(b,c) b , ab. so there are 3*2*1=6, next person will have either aa bb or cc.
This is more helpful and clear than my professor. Thank you very much!
tutor: How many triangles do we have? 2:53
me: Is this a trick question? (counts 9 + the triangle ABC = 10)
tutor: 9
me: 🤦oh my bad
@Kesha Hardel Whoa! It took roughly 150 minutes but it really doesn't work!!
just in time! thank you!
Excellent video. Very helpful!
In the first example I understand the 26^2 but I don't understand why did you add +1, you said that you add the 1 to guarantee that somebody has the same first and last initial as somebody else. But I'm a little bit confused.
Basically 26^2 covers all possible cases for different pairs of initials, meaning the 26^2 people all have DIFFERENT initials but they have all possible initials covered. The +1 person added, will have a random pair of initials, but since the 26^2 people have all possible cases of all initials, the +1 person will have the same initials as someone else in the theatre.
why did you say that 1300 is irrelevant? if the number of seats is less than (26*26)+1, then we can have zero people with same initials, if more than we have two, if the number is three times, then three people, isn't it?
For question 2, is it supposed to be ≤ 1/3? The triangle is split into 9 equal equilateral triangles with 1/3 length and we could place the points in the centre of each triangle which would still be a 1/3 apart from other points. I think It should just say greater than 1/3
theres still one more point to place
for the triangle problem, what if you put every dot at every angle rather than in the middle. so you would end up with 10 dots all 1/3 distances apart. wouldnt that disprove it?
it says less than or equal to. your way also states that the problem is valid
Thanks brother
Thank you very much Trev
I am so COOKED.
sir in the first ques how do u directly get 26 ,I can't get it
understood sir it's the number of letters in alphabet
thank you
I was looking for dictionary definition of pigeonhole. I didn't signed up for this. My head is all over the walls.
bro first one should have been 26*25 not 26*26 according to combinations rule. 26*26 generates 26 pairs of same letters. Except for that explanation is amazing.
are seats with the same latters not possible in theaters, like AA,BB,so on. I don't think it makes crucial difference.
How to solve this qn, Among 6 people (friends or strangers), show that at least 3 of them are all friends or strangers with each other?
there are as many as 6 people(pigeons). And they can either be friend or stranger to each other(holes). considering the worst case scenario 6/2 =3 people will be friends to each other and the other 3 will be strangers to each other. So at least both categories(holes) will have 3 and the both of them cannot have less than 3 people in them at the same time. So the statement is valid.
Very clear explanation! Nice job!
Why not just put 9points in one small triangle and the last on as far away as possible? That was my first thought... feel dumb but I honestly don't get where my thought-process goes wrong, help?
because those 9 points would be at a distance smaller than 1/3, you have to distance all the points from each other so that the distance betwen them is larger than 1/3
* selecting points from the triangle itself or its bounded region.
Can anyone help me solve this problem: From 1 to 100 (including 1 and 100), at least how many numbers are drawn randomly to ensure that there are two numbers which have 2 or more common factors?
thank you :)
great
can i know why 26 is squared? @ 00:40
and thank you for the video it was helpful
Someone already answered it above so I'm just gonna paste it:
First example answer why: There are 26 letters in the english alphabet, if everyone has a unique first letter and last letter initial combined, that means for every first letter initial (there are 26 possible letters), there are 26 last letters that can go with it, so by probability, there are 26 x 26 unique possibilities. Adding + 1 means that the next person will guaranteed to have a repeating initial since all unique initials are taken.
why did you add the 1 in the first ewaution?
Can someone explain why this is wrong for Q1.
27 people ---> atleast 2 people with the same first name
therefore
27 x 13 people ----> atleast 2 x 13 people with the same first name
351 people ----> atleast 26 people with the same first name
351 + 26 -----> atleast 27 people with the same first name
atleast 27 same first name ----> atleast 2 same last name
therefore 377 (351 + 26) is the solution
I don't understand what the meaning of '26' is
what is the sense of it?
There are 26 letters in the English alphabet. An initial can only contain 1 of those letters
Thanks for letting us know what's irrelevant in the problem. I will be tricked no more!
Are you the Casually Explained guy?
Nope!
How did he obtain 26?
Al same question
26 letters in the alphabet
The explanation was having no sense, to be honest. I know pidgeon hole principle but could not understand these examples.
voides ka sath koi quiz bi tu bany dy today i am so worried about mcq's of pigeon hole principle plzzzz.
For problem one where does 26 come from!!
26 possible letters
Why the number in number 1 must be 26?
there are 26 letters in the english alphabet
why u take 26 in 1st q?
26 different possible alphabets for first and second initials.you must understand product rule(counting) to understand this