PIGEONHOLE PRINCIPLE - DISCRETE MATHEMATICS

We introduce the pigeonhole principle, an important proof technique.

#DiscreteMath #Mathematics #Proofs #Pigeonhole

*--Playlists--*

*--Recommended Textbooks--*

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.

[omkars]

"No! Everybody has a friend here." You're so inspirational :, )

[raghavkhanna]

Two of the best teachers at YouTube you and organic chemistry tutor

[PalashBansal]

What an explanation. Principle look like nothing at first, but it's applications are mindblowing.

[APDesignFXP]

It’s like he knew what exactly went on in my lecture and did a great job! Amazing!

[FifthDoctorsCelery]

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.

[rickelmonoggin]

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.

[shubh_]

@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.

[adarshnathaniel]

Great way of teaching sir. I learnt this topic in just 20 min. Tysm.

[froggyq]

The way you said okay in whole video made me smile the whole time.

[azazel]

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 :) <3

[lucychix]

Good explanation of this easy-difficult concept. Many thanks :)

[kaushikdr]

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

[wintermute]

Really well made video! Thanks for the intuitive and combinatorial proofs!

[madhusaivemulamada]

no dislikes and that tells you how good you explain. really great explanation.

[jesuslife]

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!

[rajendrakumardangwal]

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.

[soramakizushi]

I really really love you. You make my life so much easier. Thank you so much!

[cupden]

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!! :)

[sienienudzi]

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.

[haomintian]

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.