How large can a subset be???

[@robshaw2639]

you have to check that the periodic union does reintroduce a violation across periods. 9+7, 9+4, 7+7, 6+7 dont conflict with anything in S+11, so the periodic union is valid at each step...

[@lucasturci5764]

That's why he chose 11 as the size of the set. Because x + 4 ≡ x - 7 (mod 11) and x - 7 ≡ x + 4 (mod 11). Why is that good? Because if x is in an 11-block, either the left side or right side of the congruence is in the same 11-block, implying that it isn't in S, which then implies that the other side isn't in S . But yeah, he should have mentioned that!

[@therealmaster9686]

@@lucasturci5764 i got lost right at the beginning as i couldnt get why he chose 11 so thx for ur help

[@philippenachtergal6077]

Yeah, took me some time to see that it works For there to be a "problem" you would need to have some i and j such that Xi + 11 = Xj + 4 or Xi + 11 = Xj + 7 Where Xi and Xj are members of a subset of {1,...11} that satisfies the rule. But that cannot be because Xi + 11 = Xj + 4 means that Xi + 7 = Xj and Xi + 11 = Xj + 7 means that Xi + 4 = Xj so Xi and Xj can't be both members of a subset of {1,...11} that satisfies the rule which is a contradiction. Therefore it is impossible to have such a problem.

[@jagmarz]

"The government doesn't want you to know this one combinatorics trick!"

[@joshyman221]

Not enough exclamation marks!!!!!!!!!!!!!

[@prithujsarkar2010]

lol that's a nice title

[@TheArmyofWin]

“You won’t believe!” kzbin.info/www/bejne/nGWppoKfbtepgdk

[@goodplacetostop2973]

15:33 Not gonna lie, I was "worried" for today because Google services were completely down worldwide few hours ago 🤯

[@tonyhaddad1394]

Yes 😭😭

[@rinkiranjan5383]

There was no "to stop", isn't it?

[@advaykumar9726]

You made a video on this

[@HagenvonEitzen]

7:30 without cases: We must have 10 in S (because singleton). Then 6 notin S and 3 notin S, hence 2 and 7 in S, hence 9 notin S, 5 in S, 1 notin S, 8 in S, 4 notin S, 11 in S, contradicting 7 in S

[@RexxSchneider]

But then you might ask if a different partition were chosen such that the singleton was not 10, would you still get a contradiction? That would then require 11 (?) cases to test. I'm not very comfortable with proof by exhaustion. It doesn't scale well.

[@mehdimarashi1736]

@@RexxSchneider You don't need to check other different partitions. We picked this partition and this partitions proves no such subset with more that 6 members exists. If any such subset exists, it has to work with "any given partition", and since there is a partition for which a 6 member subset is impossible, a 6-member subset is impossible. I don't like proof by exhaustion, neither. But for a case like this, it's just "inelegant". Elegance is overrated, though. It works, and it's not a lot of hassle.

[@kevinmartin7760]

The fact that S' satisfies "the rule" should have at least been touched on. You can figure it out pretty easily by inspection, or perhaps more formally due to the fact that 7≡-4 (mod 11). Also, you have the correct result by the chance selection of the elements of S. There are other valid S's which include 10 or 11 for which you would have had to do more careful treatment of the 9 extra elements 1981-1989.

[@thetom341]

Since S' can be rotated modulo 11, any other S' can be transformed such that its maximum is 9. I believe this gives only two unique sequences, {1,3,4,6,9} and {1,4,6,7,9}

[@kevinmartin7760]

@@thetom341 That is one form of the "more careful treatment" that he would have had to apply if he had started with, for instance, S={3, 5, 6, 8, 11}. At the start of the solution there was no analysis to indicate that choosing S to not contain values over 9 would be beneficial.

[@leif1075]

@@gregorymorse8423 It's not NP hard right because you can use basically tbe same strategy just with different partitions right as opposed to 4 and 7 difference..just plug in whatever difference constraints you are given..

[@leif1075]

@@gregorymorse8423 Thanks, as for Michaels solution I didnt fitdt think of what he does at 10:45 and 11:50 with the union of sets, i thought of adding on 12 first to the 11 and seeing how big a set you can get from a 12 element set, then 13 and see what pattern emerges.wouldnt this work and be logicaland efficient also? I haven't finished working it out...though I wouldve thought of dividing 1989 by 11 eventually

[@kevinmartin7760]

@@gregorymorse8423 Even if you start with 1, you might generate {1, 2, 4, 7, 10} but that makes the overall subset one element smaller because the 10 corresponds to the value 1990. You can tell this may happen because the bigger gap (2) between elements is not at the end of the set: The gap is only 1 between 10 and the first element 12 of the next mapping of S, while for the set S presented in the video the gap between 9 and 12 is 2, one of the "largest" gaps. Depending on the remainder of (last number)/11 you might find other S choices give the maximum cardinality. If the gaps in S are strictly in non-descending order it should give an optimal result all the time, but I'm not sure that you can always generate such an S for spacings other than 4&7. I think my point is that he didn't go into any of this, how the specific choice of S can affect the subset size you measure.

[@prithujsarkar2010]

This is a Floor Function problem from the Indian National Maths Olympiad 2014 problem 2 (since you love floor functions so much) The problem states : Let n be a natural number , prove that floor(n/1) + floor(n/2) + floor(n/3) + ... + floor(n/n-1) + floor(n/n) + floor(sqrt(n)) is even , below is the link to official pdf of the problem olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/inmo-2014.pdf Thanks!

[@debayuchakraborti1963]

YESS WE WANT IT

[@sarthakanand4515]

You can give the title "Combinatorics or CombinaTRICKS"

[@shriramsahoo1274]

0:10 Well, thats a great question! Most successful videos immediately tell you what its about. This is why most of your more successful videos are geometry problems as they don't have more than a couple words and attracts the viewers eyes. Even if its superfluous a country's flag as seen in your videos has surprisingly proved to be a secret sauce as well. I would recommend to find some combinatorics problems that you can easily portray pictorially even though i understand it is quite the task to do so! Having said that, you posted those combi vids quite a while ago, now that you have gathered an audience, PEOPLE WILL CLICK FOR MICHAEL PENN rather than the question itself. As , your subscribers grow you get more leverage with what content you want to post. Hence , with considerable assurance I would say they would do well ! Best of Luck!

[@PlutoTheSecond]

I think you can prove 3:06 more effectively using graph theory than with partitions. Build a graph with 11 vertices, connect each pair of vertices that differ by 4 or 7, and prove that any vertex colouring cannot have 6 vertices in the same colour.

[@debayuchakraborti1963]

Really nice solution... How long we all had been waiting for this !! Thanks to Mr.Penn!!

[@eugenekim3012]

I have a question here: at 10:50, why is there no need to check whether a union of two consecutive periods, such as {S} union {S+11}, abide by the rule? How are we certain that the difference between a small number in {S+11} and a big number in {S} is not 4 or 7, without even checking?

[@buxeessingh2571]

I like the combinatorics and number theory problems the most! Please keep at them.

[@mehdimarashi1736]

That argument at the end 14:10 was eluding me. I started by just playing with numbers, looking for a periodic solution. I noticed that if n and n+4 cannot go together, the largest subset possible cannot have more than 1989/2 members. I considered picking only multiples of 3, which obviously satisfies the rule. Better than than, would be either even or odd numbers and excluding every third number in the series to avoid the difference of 4, which again produces only 1989/3 members. Then I decided that There must be a better solution. There must be a period, coprime with 7 and 4, which let's us pick the most members possible. Playing with number picking, I found the period 11; and then it became obvious that since 11= 7 + 4. anything less than 11 produces more interfere at each end of the period and any period larger than 11 loses some opportunity to pick maximum member. I found a picking {1, 3, 4, 6, 9}, and I knew that at most 1/2 of the period can be included, so 6 was impossible already. But I couldn't prove 11 is the optimum period, while it looked like it. Lessons for everyone: pick pen and paper and play with numbers. You will find intuition (11 period, more than half the pool size impossible in this case). Then, you can claim results (6 member in an 11 period is impossible, period larger than 11 not as good as 11). Then you can look for proofs for the claims. As soon as Michael started talking about partitions, I remembered there is this strong tool I have totally neglected: pigeon hole principle. If I remembered that, I would have had easier time proving my findings.

[@docsigma]

Combinatorics was my area of focus at university! I'd love to see more combinatorics videos!

[@goodplacetostop2973]

0:19 Here’s an idea IT TOOK 300 PAGES TO SOLVE THIS 😱 ULTIMATE PROOF FOR 1+1 = 2!!!!!

[@captainsnake8515]

Sounds like a fresh toad walker title

[@TechToppers]

Why two comments?

[@goodplacetostop2973]

@@TechToppers Yeah I know, I don’t do that usually... I guess one more comment gets more engagement for Michael’s channel lok

[@jimschneider799]

At 6:30 - would it not have been simpler to start with the final, singleton element of 10? Selecting 10 eliminates both 3 and 6. With 3 and 6 eliminated, the construction requires adding 2 and 7. But these rule out 9 and 11. Ruling out 9 and 11 requires both 5 and 4. 5 and 4 eliminate both 1 and 8, so the entire { 1, 8 } partition is eliminated.

[@xCorvus7x]

9:17 Don't we have to check all different partitions to prove this?

[@Bennici]

Techncially, yes. Obviously, you will always end up with a singleton because 11 is odd, so that is true regardless of the partition you choose. And from there, you can probably show that of the 5 pairs you choose, you always have either 2 that differ by 4 and 3 that differ by 7, or vice versa. And then you can prove in general how that will always lead to a contradiction. Just a sketch of a proof, and maybe it works differently, but this is what I can come up with in 2 minutes with pen and paper at hand. edit: I just thought about it more and it wouldn't work like that at all. Maybe arguing "backwards" for each of the 11 different singletons would work?

[@beatlesetchansonplus]

​@@Bennici No, I don't think we do. Consider any partition into 5 pairs and one singleton of the 11 numbers such that no two numbers in a pair can be in a set that respect "the rule" (e.g the one shown in the video). Then, if a subset of {1,...,11} that respect "the rule" exists with 6 elements, it cannot contain two elements from one of the pairs. Therefore, it must contain at most one number from each set in the partition we considered, and since there are 6 sets in the partition, it must contain exactly one number from each pair, plus the singleton we singleton-ed out. Then, you proceed to show that it leads to a contradiction like in the video, therefore our assumption is wrong, i.e no 6 elements subset of {1,...,11} exists.

No. Any single one partition is good enough for this argument.

[@xCorvus7x]

@ So, the different partitions are interchangable in a way that doesn't affect the reasoning?

[@beatlesetchansonplus]

@@xCorvus7x Yes, any partition happen to work in this case (It seems to be the case, but I didn't check). For each partition, a 6 elements solution must contain an element from each set in the partition. It is true simultaneously for every partition, for any given 6 elements solution. So to prove no such solution exist, you just have to find one partition that gives a contradiction. If somehow, which doesn't seems to be the case here, some partitions gave no contradiction, as long as one leads to a contradiction, the proof stands.

[@robertgerbicz]

Simplified method as we don't need two different cases: if we want six terms, then 10 should be in the set. But then 3 and 6 is not in the set, hence 2 and 7 is in the set. From this 9 and 11 is not in S, from this 4 and 5 is in the set. But then 1 and 8 is not in S, this is a contradiciton, because from {1,8} exactly one should be in S.

[@wesleydeng71]

Should've mentioned that no pairs between {1,4,6,7,9} and {12,15,17,18,20} differ by 4 or 7.

[@wesleydeng71]

Well, actually it is not an coincidence. One can prove that if no pairs differ 4 or 7 in the 1st set, then there will be no such pairs between it and the next set either.

[@joysreenath919]

good job Michael you are just excellent

[@donofmath248]

Slightly streamlined version of the proof that there can’t be a 6 element subset of 1-11 satisfying the rule: There were 11 pairs of mutually-exclusive numbers, and each number 1-11 appears in exactly 2 of those pairs. If there were a 6 element subset satisfying the rule, those elements would need to appear in 12 distinct pairs (since they appear in 2 each and cannot appear with each other and satisfy the rule). But as there are only 11 such pairs, some 2 of our numbers must appear in the same pair, meaning the set doesn’t satisfy the rule.

[@trangium]

For the proof at 9:02 I started with the fact that 10 is in S and then followed to chain to a contradiction. This is better because you don't have to check two branches.

[@AlephThree]

Three brainstorming ideas for you. 1. I think you’d get more views if you updated a question like this to the current year I.e. {1, 2, ... 2020}. Then you can say based on a 1989 problem or whatever in the video and solution is similar. But would feel more current/relevant. 2. Also may help to include flag or logo of competition in thumbnail, where it is a competition question - think glamour by association. 3. You could also tease the question in the thumbnail: “How many subsets of {1,2,...2020} satisfy...” so that folk click through to get the rest of the question, rather than try to summarise it and end up using too many words (comparative to other things we can click on.

[@sirgog]

A lot of IMO style problems don't work for any given year, they rely upon some specific property of the number of the year. Example from my first IMO, 1998 Q6 (which I didn't solve in the contest but got 1 point for) relies somewhat upon 1998 having multiple distinct factors. It would have been trivial in a year that was a prime number.

[@AlephThree]

@@sirgog that’s true. It will work for some though!

[@gutfroh]

A possible solution for your "click problem": I admit that I personally also don't watch a lot of combinatorics videos and I think it is because the thumbnails always look so "complicated". When I see these thumbnails, I always feel too lazy to try to understand the problem or the proof, but later I realize that it wasn't that hard to follow you while explaining it. Maybe you could try to make the thumbnail look more "easy to understand" and for example put the part of the problem in the video which makes it so beautiful or the part which inspired you to make a video about this problem. Or maybe an interesting visualization which helps understanding the problem. If you take this thumbnail for example, there is just a long sentence describing the problem. One positive thing about this thumbnail is the interesting font and the the different colors highlighting the four and seven and the set. To make the person seeing this more curios about the video, you could maybe write the first numbers of the final set. The title of the video completes the thumbnail which is, in this example, choosen very nice I think. The person sees the unknown set and then sees the question "How large can this subset be???" and wants to know the solution. Hope I could help you :)

[@jagmarz]

It's not at all clear to me why the union of all the offset subsets S should follow the rule? Can't there be exclusions between adjacent subsets also?

[@anastasissfyrides2919]

my question exactly

[@robertgerbicz]

Right, this hole is at 11:49 in the video. The S_final set satisfies the rule but not due to the construction of S. To show that it is satisfying the rule you could work mod 11.

[@samyakmahapatra9154]

Sir keep on bringing more of such variety problems, don't worry abt views :)))

[@chhabisarkar9057]

Pro

[@adrianamor8472]

Note that if the remainder of 1989/11 was < 9 you would have to substract these elements from S_final

[@mathiashudobadebadyn4236]

Cool graph or network pictures might help the thumbnail situation

[@paolomilanicomparetti3702]

I feel like the impossibility of a set S of 6 out of 11 consecutive numbers C can be proven more simply by noting that among 11 consecutive number every number is mutually exclusive with exactly two others, according to the rule. A set of 6 elements would cause 12 exclusions, to be distributed among the remaining 5 numbers in C - S. That requires at least one of the 5 to be excluded by more than 2 of the numbers in S. But that is not possible, as each number in C is only at +-4 or +-7 of exactly two numbers in C, not more.

[@djvalentedochp]

michael don't worry if some videos don't get nice results, the most important thing is the knowldge you share to us

[@prithujsarkar2010]

yea

[@namannarang4208]

personally i really enjoy all the combinatorics stuff

[@anastasissfyrides2919]

Quick question We know that each set in the union follows the rule, since the elements in it are chosen just for that. But how do we know that the elements in a set do not "contradict" the ones in the next or in the previous set in the union?

[@andrzejjasek1990]

I asked this question myself too, but the set was set nicely. If we consider two consecutive pair of sets: {1, 4, 6, 7, 9} U {12, 15, 17, 18, 20} and compare all reasonable, possible, common elements breaking possibly the rule of first set with the second we get: 9+4=13, 9+7=16, 7+7=14, 6+7=13, 4+7=11. None of these breaks the rule. Rest is a simple induction.

[@gliderguld]

Proof accepted for repetitive patterns of length 11. Still needs to see, that this is not beaten by repetitive patterns longer than 11 or (unlikely) a non-repetitive soloution.

[@jamirimaj6880]

What's a great reason/proof as to why (s+11) doesn't have any elements that when subtracted to an element of s, it will give either 4 or 7 without inspecting the elements one by one? Because I understand that if this is established, then you can indeed unionize it with s+22, s+33, s+44 etc etc...

[@tarohojo6761]

Awsome little quiz!

[@prithujsarkar2010]

amazing problem , please bring more such AIME problems :)

[@samyakmahapatra9154]

:santhathonk:

[@prithujsarkar2010]

@@samyakmahapatra9154 :kuchbhi_kuchbhi:

[@samyakmahapatra9154]

@@prithujsarkar2010 -_- kya?

[@leif1075]

Would anyone donwhat he did at 11:59 with the set union..why not add a 12th element and then a 13th and see if a pattern emerges thst way..that is logical and efficient too..

[@Walczyk]

this makes me think about van der waerden numbers, fascinating stuff

[@thayanithirk1784]

S please do more combinatorics problem, maths Olympiad in India is coming close there are more Indian viewers watching your channel professor it will be helpful for us

[@hanskoch6564]

Suggestion for future combinatorics videos: EXTREMELY HARSH combinatorics problem, I NEARLY DIED and a good old giant red arrow pointing at the chalkboard

[@goodplacetostop2973]

As a meme video, I’d love to see the most clickbait video Michael could do 😂

[@moonlightcocktail]

Sounds like Pressed Tap Water

[@sirgog]

@@goodplacetostop2973 4! tricks mathematicians HATE! You won't believe #13

[@ivanklimov7078]

I think this title works well because when i saw it i initialy thought it would be some sort of theoretic video about subset sizes in general, and i'm personally more interested in these type of videos on theorym rather than concrete problems. You could say that it's kinda clickbaity in that way, but i still got interested and ended up watching a video i would otherwise probably skip.

[@nawusayipsunam1643]

Tys

[@chester_m]

Maybe for thumbnails construct a set of such numbers then make an image where each number (whether it's there or not) maps to a pixel and the pixel is assigned a color based on presence in the set?

[@HagenvonEitzen]

2:00 Correct expression is DA RULEZ ;)

[@brianastle4428]

He did not prove that Su(S+11) followed the rule which is necessary for the remainder of the proof.

[@dougcampbell7898]

why did you eliminate 5 but not 1?

[@malharmanagoli]

This shows that max |S|

[@keinKlarname]

@Malhar: The maximum size is 905.

[@parthgandhi8359]

Can you please make a video on how to self learn mathematics from begineer to advanced mathematics ?

[@officialgigel]

Pls solve for m and n , when 11 divides (m +13n) and 13 divides (m+11n)

[@Pumbear]

For a title suggestion In this case it could have been nice to mention it's from a contest.

[@JohnDoe927]

I don't get how you can get 1 and 9 in the same set. Note that 9 - 1 = 8 > 7 > 4 so 1 and 9 can't be in the same sub set right?

[@keinKlarname]

@Eliot: 8 is different from 7

[@SG2048-meta]

8 is not 7????

[@doontz111]

I suggest using colors and shapes when possible

[@claytoncoe838]

Thumbnail idea: Illustrate "the rule", e.g. on a number line, or something similar

[@NavyBlueMan]

Maybe it's just the convention but it seems weird to me that the set is explicitly stated to include {1,2,3...,1989} but doesn't necessarily include 1, 2, or 3 depending on how it works

[@xCorvus7x]

I think you are misunderstanding some thing. The set S we are looking for is *not* described as {1,2, 3,...,1989}. {1,2, 3,...,1989} is the set of which S *is a subset* (maybe strict, maybe not), so initially we really don't know what elements are in S.

[@Umbra451]

NOT 4 OR 7? THIS IS INCREDIBLE!!!

[@captainsnake8515]

Probably doesn’t work for this one, but for combo problems that have easy to see visualizations, I think putting an example visualization in the title would look nice.

[@KSJR1000]

I found the set {1,2,4,7,10}

[@Outwhere]

{1,3,6,9,11} also works, but the final set will be 904 (like with {1,2,4,7,10}), because 11 (or 10) + 1980 will be larger than 1989. So before constructing the "simple example", you would have to show that because 1989 ≡ 9 (mod 11) the largest number in your "simple example" must be smaller than or equal to 9. (Instead of just putting it on the board as "one of the possibilities").

[@jeequestionsindia]

Combinatorics gone wrong

[@fibbooo1123]

Awesome!

[@JM-us3fr]

I feel like there's gotta be a nice pigeonhole argument for this

[@MrRyanroberson1]

Since the Sfinal starts with 1 and ends with 1989, if the subset contains one more number then the density must therefore be greater somewhere along the way; the pigeonhole argument is basically this where you choose to look at the densest region

[@jimallysonnevado3973]

i didnt het the last part how is it

[@andrewandcubes]

181 * 5 = 905, if you were wondering

[@Utesfan100]

We can start with 10 is in s, so 6 is not. Then 2 must be in s, so 9 can't be. Thus 5 must be and 1 can't be. Thus 8 must be and 4 can't be and continuing as with 8.

[@haritambindua]

You can give the tittle "how to count smartly"

[@hollisluethy3673]

Wouldn’t the answer be greater than 180*5 because 1989/11 has a remainder of 9?

[@hollisluethy3673]

If our set is constructed “multiples” of {1,4,6,7,9}, the last member of our final set would be 9 + 11(180) = 1989- Oh okay never mind then.

[@TypoKnig]

However one might get more views, your videos seem to be well monitized. I keep seeing commercials at interesting transitions points. I hope Old Spice is paying you enough to keep you in chalk.

[@route66math77]

Ha, fun problem. I like it!

[@haritambindua]

You can also start a series on combinatorics with name "combino domino"😁😀

[@andrzejjasek1990]

''1 choose 0 from combinatorics''

[@srikanthtupurani6316]

Nice problem. If I am in a hurry. I think of how to find the solution of the problem for the case when the set is {1,2,...,n+1} if I know how to solve the problem when the set is {1,2,......n}. This is a wrong approach. Nice solution.

[@movax20h]

You didn't prove that S union S+11 satisfy the rule.

[@darreljones8645]

The total size of S, which Michael never mentions or calculates, is 905 members, or just over 45.5% of the entire original set.

[@elosant2061]

Yes he did, 181*5

[@darreljones8645]

@@elosant2061 Well, he never said 181 * 5 = 905.

[@ayoubabid714]

Nice

[@keithmasumoto9698]

1989 - (1989/4 + 1989/7 - 1989/28) gets you close.

[@Leockard]

You need a mascot, like 3b1b's pi creatures. Easier thumbnails!

[@Tekashiixine-yb5kh]

For combinatorics, if you make the problem kind of into a "game" it would interesting to watch.

[@rupeshsaini2011]

I am a bit confused. Why did you not consider relationship between the 181 sets. Some elements from consecutive sets will eliminate others.

[@guymross]

What’s the intuition for choosing 11? Oh you know it’s because uhm that’s what’s written in the solution.

[@raystinger6261]

Why 11? Why not start with a set that goes from 1 to 9? 9 is a factor of 1989.

[@zygoloid]

Because we want S satisfies the rule => S' satisfies the rule We get that with 11 elements because if two elements in different copies of S differ by 4 then the congruent two elements in the same copy of S differ by 7 and vice versa. (I think Michael's explanation skipped over this.)

[@raystinger6261]

@@zygoloid Thanks! But I gotta say, he shouldn't skip on information like that it makes the whole calculation look arbitrary and undermine students' confidence that they can solve problems like this on their own. As much as I like his videos, he's often reassuring us that he isn't just pulling some cop out, but fails to fully explains his thought process.

[@GKinWor]

i dont know anything about combinatorixs

[@JohnSmith-vq8ho]

I found this quickly and poorly explained compared to the quality of your usual videos.

[@muckchorris9745]

"The hidden Power of Combinatoric" And you make cobinatoric as a supe rhero with a laserbeam and trousers over his head.

[@michak8029]

current title "How large can a subset be???" doesn't explain much about the video and is kinda click baiting - something, what SMART people just avoid (dumb will click for click bait, but imho dumb ppl are not interested in this matter), better to clearly describe content of video, for example "AIME 1989 subset problem" - clear title matching content of video

[@Ensign_Cthulhu]

You have to demonetize, Mr Penn. I did not get 70 seconds into this video before being interrupted by 10 seconds worth of ads. This is unacceptable. The maximum size of S is zero. For any of the 1989 natural numbers, there will always be at least two that differ by 4 or 7.

[@JohnSmith-vq8ho]

Lmao what are you saying? The maximum size of S is 905