Can you solve these counting problems?
Vložit
- čas přidán 18. 06. 2024
- There are 100 players in a single elimination tournament. How many matches need to be played? Three sets have their union as the integers from 1 to 10, and their intersection is the empty set. How many such sets are possible? Special thanks this month to: Mike Robertson, Daniel Lewis, Kyle, Lee Redden. Thanks to all supporters on Patreon! / mindyourdecisions
0:00 problems
2:25 solution 1
5:18 solution 2
Problem 1
The College Panda
thecollegepanda.com/12-tricky...
Brainly
brainly.com/question/13082487
AoPS 2023 AMC 10B, P15
artofproblemsolving.com/wiki/...
Problem 2
1985 Putnam A1
prase.cz/kalva/putnam/psoln/p...
Twitter
/ 1
1985 Putnam
kskedlaya.org/putnam-archive/...
Math StackExchange
math.stackexchange.com/questi...
1985 Putnam solutions
math.berkeley.edu/~giventh/19...
More Putnam videos
--------------------------------------
1968 Putnam exam A1
An integral that implies pi is less than 22/7
• Legendary test questio...
2004 Putnam A1
If your free throw percentage is below 75%, and later is above 75%, is there necessarily a point where it is exactly 75%?
• The hardest test had t...
1978 Putnam B1
A convex octagon inscribed in a circle has four consecutive sides of length 3 and four consecutive sides of length 2. Find the area of the octagon.
• The smartest students ...
1994 Putnam A2
Finding the area of a sector of an ellipse
• Secret math trick to s...
1989 Putnam A4
For an irrational number &alpha between 0 and 1, is there a finite game with an unbiased coin such that the probability of one player winning the game is α?
• Problem From The Harde...
Subscribe: czcams.com/users/MindYour...
Send me suggestions by email (address at end of many videos). I may not reply but I do consider all ideas!
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
Book ratings are from January 2023.
My Books (worldwide links)
mindyourdecisions.com/blog/my...
My Books (US links)
Mind Your Decisions: Five Book Compilation
amzn.to/2pbJ4wR
A collection of 5 books:
"The Joy of Game Theory" rated 4.3/5 stars on 290 reviews
amzn.to/1uQvA20
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" rated 4.1/5 stars on 33 reviews
amzn.to/1o3FaAg
"40 Paradoxes in Logic, Probability, and Game Theory" rated 4.2/5 stars on 54 reviews
amzn.to/1LOCI4U
"The Best Mental Math Tricks" rated 4.3/5 stars on 116 reviews
amzn.to/18maAdo
"Multiply Numbers By Drawing Lines" rated 4.4/5 stars on 37 reviews
amzn.to/XRm7M4
Mind Your Puzzles: Collection Of Volumes 1 To 3
amzn.to/2mMdrJr
A collection of 3 books:
"Math Puzzles Volume 1" rated 4.4/5 stars on 112 reviews
amzn.to/1GhUUSH
"Math Puzzles Volume 2" rated 4.2/5 stars on 33 reviews
amzn.to/1NKbyCs
"Math Puzzles Volume 3" rated 4.2/5 stars on 29 reviews
amzn.to/1NKbGlp
2017 Shorty Awards Nominee. Mind Your Decisions was nominated in the STEM category (Science, Technology, Engineering, and Math) along with eventual winner Bill Nye; finalists Adam Savage, Dr. Sandra Lee, Simone Giertz, Tim Peake, Unbox Therapy; and other nominees Elon Musk, Gizmoslip, Hope Jahren, Life Noggin, and Nerdwriter.
My Blog
mindyourdecisions.com/blog/
Twitter
/ preshtalwalkar
Instagram
/ preshtalwalkar
Merch
teespring.com/stores/mind-you...
Patreon
/ mindyourdecisions
Press
mindyourdecisions.com/blog/press - Věda a technologie
The first question was pretty easy, and the second one went way above my head 😅
Same here!
Add another. First question was trivial. Even after the explanation, I don't understand the 2nd question. Somehow in my learning career, sets and set theory got only minor coverage.
@@oldguydoesstuff120Okay, so breaking down the second question:
An ordered triple means a triple where the order matters. X, Y, Z is not the same as Y, X, Z (unless X and Y happen to be equal).
A1, A2, and A3 are all sets containing some/all/none of the numbers from 1 to 10. (This is implicit based on the statement about their union.)
The union of two or more sets is the set of all things that are in at least one of those sets. {1, 2} union {2, 3} = {1, 2, 3}.
The intersection of two or more sets is the set of all things that are in all of those sets. {1, 2} intersection {2, 3} = {2}.
The symbols are just abbreviations: u = union, n = intersection, 0 with slash = empty set (the set containing nothing).
If they are triplets, how can they contain a total of 10 distinct elements?
@@HenrikMyrhaug Because it's not a triplet of numbers, it's a triplet of *sets* of numbers. A1 = {1, 2, 3, 4}, A2 = {5, 6, 7}, A3 = {8, 9, 10} is an example of a triplet matching the conditions.
Problem 1's solution was taught to me as a heuristic when arraning tournament brackets and figuting out time allocations, n players means n-1 matches, so you need (n-1) times estimated match length amount of time to play the whole bracket
Exactly if you don't count prorrogation
This is a well-known theorem in computer science, every tree has one edge less than it has nodes, no matter its shape.
Fences and posts were how I learnt this. Completely same theory.
Yes but here you need to use the complete tree problem of a binary tree. There should be 2^n leaves (n=8); as there is a remainder - 28 people will get a bye and 36 spots would be selected from the qualifiers. Thus, with 64 leaves - The internal nodes would decide the number of matches to be played - 63 (2^n - 1 internal nodes). Thus, 99 matches. This should be the solution.
So given a single-elimination tournament that results in 1 winner, you construct a graph by letting players be the nodes and matches between players be the edges. Now you still have to show that this is a tree: connected and no loops. This is certainly doable but seems considerably more work than using the trivial counting argument of the video.
@@ronald3836@ronald3836 it's easily and intuitively represented as a tournament tree. The leaf nodes represent players, and the internal nodes are matches, the edges connect players and the winners to their next match.
Now you have your tree with n leaf nodes, and n-1 internal nodes.
If you're familiar with comp sci, you don't *need* to prove anything, because it's already been proven
@@eaglegosuperskarmor you have constructed a graph. You still have to prove that this graph is a tree, i.e. connected and without cycles. I agree that it is a tree, but my point is that proving this is more work than directly applying the simple counting argument given in the video.
I misread problem 1. I thought it was asking how many rounds were needed.
which should be log2
Same
Can you explain? Last I checked log2 != 7 @@robmarney
@@Pawn-Sacyou round up in this case. 128 is the next power of 2 after 100, so 7.
@@Pawn-Sac the 2-log of 100, i.e. log(100)/log(2) and round upwards.
If you're familiar with such tournaments the first thing that comes to mind is indeed to count the number of rounds, but the beautiful thing is there is no need to. The answer is independent of the shape of the tree. You could have player #1 play #2, let the winner face #3, let the winner face #4, etc. The answer is still the same: 99.
Each match eliminates 1 player. We need a winner, so 99 players need to be eliminated, so we need 99 matches.
It is that simple.
8:07 : "... 2¹⁰3¹⁰ , and that's the answer!"
No, it's not. The question specifically asked for an answer in the form
2ᵃ 3ᵇ 5ᶜ 7ᵈ
where a, b, c, d are non-negative integers.
So the correct answer is
2¹⁰ 3¹⁰ 5⁰ 7⁰
1 point subtracted for pedantry.
@@ronald3836 thx for teaching me a new word
So, the first problem, I figured out both of those solutions in my head, first thinking you'd do 50 matches, then 25, then 12, etc... figured if I sat down and did the math it would be 90 something, then I thought, what if we held one match at a time and the winner moves on, that would be 99 matches. I was please to see both of those fleshed out in the video.
On the second problem, I concluded "huh?"
Number 1 is kind of a joke tbh. To crown 1 winner, exactly 1 person must remain after all eliminations. This happens after 100 - 1 = 99 eliminations. Since each match corresponds to an elimination, 99 matches are required.
It is true that the number of matches required is 99 matches. However, because the question specifically mentions tennis matches, the calculation method must use the standard tennis match method. Byes are carried out in the first round of the match to prevent byes from occurring at further stages of the match. The first stage is to determine the player who gets a bye by subtracting the nearest 2^n to the number of players. so 128 - 100 = 28 people get a bye. so only 72 players played in the first match.
So total matches should be:
1st round = 36 (72 play - 28 bye)
2nd round = 32 (64 play)
3rd round = 16
4th round = 8
Quarter final = 4
Semi Final = 2
Final = 1
The total also 99 matches
woa
For the tournament problem, a better question would be how to arrange the tournament to require the fewest number of byes.
My favourite Putnam competition question is the empty set.
I know you mainly explain problems, but I don't even understand the second question, let alone it's solution. If you had a second channel, teaching a bit about that problem would be a great thing to put there.
I had a hurdle with understanding, that A1, A2 and A3 are sets. Like, one possibility would be the triple
({1,2,3},{4,5,6},{7,8,9,10}).
The sets can overlap.
To rephrase it, you want to distribute the numbers from 1-10 into 3 groups A, B and C that follow the following conditions:
1)Every number must be in at least 1 group
2)No number can be in all 3 groups. (A number appearing in 2 groups is still allowed)
We need to find how many possible ways there are to do this distribution that obeys the two afermentioned rules.
Hopes this helps
To generalize the second problem, let's say that you want to find how many n-tuples of sets satisfy the conditions that the union of the tuple's elements is the set {1, 2, ..., m} and the intersection of the tuple's elements is the empty set; the answer is ((2 ^ n - 2) ^ m).
@@Ninja20704 and "ordered" means that e.g. {1},{2},{3,...,10} and {2},{1},{3,...,10} are TWO solutions. This makes counting a lot easier in this case.
Thank you
3:14 I initially misunderstood this part. Of the 25 players, only 24 play a match but the remaining 1 player isn't automatically eliminated or anything, they just "skips over" a round and will be paired in a match the next bracket, so they're still in the running. imho this could have been explained a bit more explicitly.
I was scratching my head like crazy about what happenned with that 25th player with no match at that stage. This makes sense, THANK YOU! 😁
As a former tennis player, the explanation did not make sense. There are 63 matches in a 64-person tournament. To eliminate the other 36, you would need to have a corresponding number of matches, and the losers would be eliminated in the round of 128. That would be 99 matches with 28 byes. Placing the byes in later rounds may make sense mathematically but not in actual practice. As a temperamental lot, the described solution might make those who had to play every match feel cheated…
Tx so much
The tennis problem seemed so simple that I thought that there must be some condition not specified. Like, maybe the problem was poorly worded or some such. Solving such a problem, I would probably make my assumptions very explicit and provide solutions for a number of different problems under different assumptions.
The problem clearly states that a bye is a game. So when counting games, byes MUST also be counted, assuming "game" = "match".
@@bernardbrooks2737 Aha, "assuming"...
@@bernardbrooks2737 I would call it a match only if it matches two players. If there is no player to play against, there is no match in the literal sense of the word. It still could be a game, as a game can be played alone. So the number of matches required is different from the number of games. On the other hand, this amounts to logomachy and hairsplitting, as for instance, the word "game" has a special meaning within Tennis, and usually, a player has to win at least two games (best of three) to win a match. Both the ATP and the WTA count byes as matches in their scores, which would even non-matches turn into matches. Shall I continue with all the ambiguities?
@@bernardbrooks2737 Exactly. If you think the problem through with 10 players, then you get 5 matches, one bye, then 2 matches for the remaining four players and finally 1 match for the final. If you exclude the bye than you only have 5 + 2 + 1 = 8 matches.
Byes should not have been mentioned in the question. There was no mention of rounds, matches being played simultaneously, or any other aspect of standard tournament structures, so byes are irrelevant.
@MindYourDecisions ,
7:07 "So how many regions are there?"
In the diagram, there are _seven_ regions left. The seventh region is the region outside the three circles, which remains black. However, putting any element x into that region doesn't lead to a valid ordered triple (A1, A2, A3) because it wouldn't satisfy the condition " A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ".
By the way, the statement " x ∉ Ø " doesn't make sense. What you meant, was " x ∉ NOT(A1 ∪ A2 ∪ A3) " or " x ∉ (NOT(A1) ∩ NOT(A2) ∩ NOT(A3) )" .
I agree, and prefer " x ∉ NOT(A1 ∪ A2 ∪ A3) " as that 7th region. he does mathematically list that as one of the regions that is subtracted during the arithmetic, but i see what you're saying
Nice video, it'll be useful
I think the second one can be seen a little easier without separating the unions out - each of the numbers must be in 1 or 2 of the 3 sets. Can't be 0 because of rule 1, can't be 3 because of rule 2, and no other numbers can be in the sets because of rule 1.
There's 3 ways to put a number in 1 of 3 sets and 3 ways to put a number in 2 of 3 sets, total of 6 per number. (alternatively it's 2^3 minus the 2 cases that break the rules)
Each number is independent because the rules being used don't cause any interaction between numbers.
Therefore it's just 6^10.
Agreed. I don't know why the video has the Venn diagram, which seems entirely unnecessary. Instead, it should have explained the meaning of "ordered" in this context.
Thanks
A variation of Problem 2 would be to require the three sets to also be nonempty. The 6^(10) possibilities found in the original version contain various with one set being empty, so we need to count the number of those configurations and subtract it from 6^(10). This can be done via inclusion-exclusion:
(1) If we fix one of the three sets to be empty (3 choices), then each number from 1 to 10 has only three possibilities which set it can lie in - the first of the two remaining sets, the second one, or both. We thus have 3*3^(10) choices for this.
(2) However, any solution in which two sets are empty is counted twice in (1), depending on which of the two sets we fixed to be empty. We thus have to subtract this from the number determined in (1). The number of such configurations is just 3 (choose which set is *not* empty; then all numbers from 1 to 10 have to lie in that set).
(3) We thus have 3*(3^(10)-1) configuration with at least one empty set.
In total, this gives us 6^(10)-3*(3^(10)-1) configurations with no empty set.
oh wait nevermind
I dont think Presh answer is correct for problem 2..I got 1670 because you have three sets of triples so one of the digits is always left out correct? And why did he onlymdibtract two.otpion from 8..you cannot have in, in , and out because each element can only appear in one set st a time correct right NOT two? Anyone else see this?
@@leif1075 It seems you understood the problem differently.
(1) It asks for the number of all ordered triples (A1, A2, A3) with some additional properties. That does *not* mean that A1 itself is an ordered triple (and neither are A2 and A3). They can be sets of any size, as long as they satisfy the other properties.
(2) The union of all three sets needs to be the integers from 1 to 10, so every such integer has to lie in at least one of the three sets. No number is allowed to be left out.
(3) The intersection of the three sets needs to be empty. This means that no number can lie in all three sets at the same time. The intersection of, say A1 and A2 can be nonempty, provided that A3 does not contain any elements which are both in A1 and A2.
Presh's solution is correct. By putting each number from 1 to 10 into at least one of the three sets, property (2) is guaranteed, and by avoiding to put it into all three sets, property (3) is satisfied aswell. Property (1) is just a different way of saying that the three sets can be distinguished by their indices, which is also fine by the construction.
I solved this one while looking at the thumbnail. Its pretty ez if u simplify it. If u have a 4 person tournament it would take 3 matchs, so 100 players would take 99
In the first question: The rule of implementing minimum byes feels odd and impractical. In a tennis tournament there would ideally be byes given in the first round rather than handing out byes in quarterfinals.
However, the n-1 matches trick is cool. Good to learn.
99 (or n-1) matches are still required regardless of the number of byes, but it would be an interesting extension of the problem to prove what the minimum number of byes would be. If all the byes are limited to the first round only, then 28 players would be given a bye, which is rather high. The example given in the video only has 3 players given byes across the tournament, which is probably the minimum, but I'm not sure.
Minimum byes was unnecessary information, probably given to make the reader first look for the tournament structure that has the minimum number of byes (whereas the tournament structure is not relevant at all to the number of games required).
@@ryanratcliff2726 I'm pretty sure the optimal algorithm is to postpone byes as much as possible (which is what the video does). So at every round, if the number of remaining players is even, let them all play without bytes. If odd, then allow 1 bye. If you "move" a bye to an earlier round, you basically need to replace it with 2 byes.
However, this is not yet a proof, and also the video does not give a proof.
Didn't understand enough set theory to understand 2. I ended up counting combinations where each number in each set could only be used once. I definitely counted wrong using combinations and got 3^2*4111. Knowing the solution now the answer to *that* would just be 3^10, since each number would have 3 choices. It makes sense that the actual problem would be 3^10*(2^10). It's more intuitive to me that for each number there are 6 ways for it to occupy the sets: 3 combinations in only one set and 3 combinations where it is in two sets.
If each number could occur only once in A1,A2,A3, then the answer would be 3^10: you assign each number to exactly one of A1, A2, A3.
Note that "ordered" in the problem statement means that e.g. {1},{2},{3,...10} and {2},{1},{3,...,10} are two different solutions.
1:24 - Heh! I thought this description WAS Problem 2!
Regarding the Putnam, I didn't understand how the median score could be 1, so I looked it up. The scoring allows for partial scores, which are usually 1 or 9. So, if all the scores are listed from lowest to highest, the score in the middle got the lowest possible partial credit on 1 of the 12 problems and no credit on the other 11. (What originally confused me is that if there were no partial credit, it'd be impossible for the median to be anything other than a multiple of 10.) Also, for what little it's worth, in Problem One, that's not how a tournament would be organized. The byes always come first, to reward the higher-seeded players by requiring them to play fewer matches (though some argue that sitting idle for one round is actually a disadvantage). We want to get down to a power of 2. The largest power of 2 less than 100 is 64, so we want to get down to 64, so we need to eliminate 36 players, so we have 36 first round matches, and after that it's powers of 2 -- 32 second round, 16 third round, 8 fourth round, 4 fifth round, 2 sixth round, 1 seventh round. Same number of rounds (it'll always be the power of 2 that's next greater than the number of players -- 128 is 2 to the 7th, the only variable is how many first round matches you have) and of course it's still 99 matches, but that's how it'd be done. It's unusual for only 28 of 100 players to get a bye, and for some winners in the first round to play other first round winners instead of a player who got a bye, but that's how this particular example works out.
Wrong. It says to MINIMIZE the number of byes, so as little as possible, like in video, where the number of byes was 0, exactly as specified...
@@KuK137 I did forget the requirement for the minimum number of byes. You're right, the way shown in the video does minimize those. On the other hand, I never said my solution was better for the stated problem, merely that that's not how actual tournaments are conducted (which I believe to be correct). Also, the bye requirement is irrelevant to the answer -- minimizing the byes makes NO difference (the answer is always 99 matches, or one less than the number of players, no matter the number of byes). Also, you are wrong that the number of byes is 0. Any time the number of players left (right column) is odd, there's a bye in the next round, so there are 3 in this example -- after the rounds where there are 25, 13, and 7 players left.
@@KuK137 There were 3 byes in this video's solution.
How you organize the tournament does not matter. The answer is always 99, simply because a match always eliminates exactly 1 player and "single elimination" means each player but the winner is eliminated exactly once. So after 99 eliminations = 99 matches you have the winner.
@@ronald3836 I think everyone on this thread already agrees with what you said. But the stated problem did have an additional (irrelevant) requirement to minimize the number of byes. (I'm not sure why that's in there, except to confuse us by making us think it matters. What, in my elementary school days, we used to call "word problems" often include irrelevant information, as do problems we encounter in real life. Weeding out the irrelevant is part of the problem-solving process.) That's what KuK137 was commenting on. The video solution minimizes byes; my solution doesn't. But I never said my solution was a better answer to the problem as stated, merely that it was how actual tournaments are conducted.
Isn't the actual answer to #2 (2^10)(3^10)(5^0)(7^0)? It seems a bit misleading to imply 5 and 7 are factors of the answer and that the exponents will all be different, even if none of that is stated explicitly
At this level of mathematics, most people would actually not assume 2, 3, 5, and 7 are all factors of the answer, believe it or not. It looks to me like they put it in there moreso to have a clean way to express the answer than to try to give more information. Having an exponent of 0 is pretty immediately considered or even not given any thought because it's automatic in your mind.
Agreed. Knowing these type of tests, I don’t think you’d get full marks unless you showed it in the form (2^a)(3^b)(5^c)(7^d).
I’d perhaps even state a=10, b=10, c=0, d=0 just for good measure. :)
The way they stated "non-negative" instead of "positive" or "strictly positive" should cue you into that I guess.
It is actually providing additional information, just not the information you're thinking of: the answer has to be expressed in its prime factorised form, but none of its prime factors can be above 7. The requirement tells you that the answer couldn't be 11, for example.
@@alexholker1309 LOL I remember an exam with a T/F question which said that "if you don't place at least 3 Ts and at least 3 Fs, your answer will not be graded"! 😂
We don't even need to think about the structure of the tournament tree, since it's arbitrary.
Consider a match. It takes two players, and eliminates the loser. The winner is left in the player pool.
We can see to find the champion, we need to eliminate the other 99 players, and thus 99 matches are needed, each eliminating a single player. It doesn't matter one bit whether the games are arranged in a nice tree shape, or if the whole affair ends up being a single strong player clobbering 99 opponents one after the other. So long as players who are eliminated don't get to play in more games, the result is the same.
Shouldn't the answer to problem 2 be 2^10 * 3 ^10 * 5^0 * 7^0?
that escalated quickly
i made a formula for calculating how many matches with even more players per match
x=(z-1)y+1, where x is the number of players, z is the amount of players per match (assuming 1 winner), and y is the total number of matches. (Edit mixed up x and y)
The tournament problem reminds me of a Professor Layton puzzle that asked:
“Forbidding cutting multiple pieces of chocolate at the same time, how many times do you have to split one piece of chocolate into its 30 squares?” The answer was 29 by the same logic, but backwards: Splitting any piece of chocolate makes two smaller pieces, increasing the count by 1.
Single-elimination tournaments can indeed be mapped 1-1 to single-piece chocolate cuttings :)
Without the "forbidding cutting multiple pieces of chocolate at the same time" detail, the answer would be nine: four vertical cuts for five columbs and five cuts for six rows.
Shame on me ! I found quickly the second problem but took the long way for the first.Thank you for all these funny problems !
In the first problem, why do we need the constraint that there are minimum number of "byes"? On easy solution is to number the players from 1 to n, have a match between the first two, have a match between the winner and the 3rd, then a match between the winner and the 4th, and so on. Clearly, this gives n-1 matches.
My dad told me that when I was 6 years old, he asked me this question, to which I immediatly answered "1 less than the total (99 matches for 100 players) because the last remaining player only has himself to play against".
I'm pretty sure the answer to the second problem is 0, not 6^10. You can't have a set of ten numbers all fitting into three sets of three numbers. Similarly, if it was nine numbers, you couldn't have any of them occurring in two sets since you'd run out of numbers to assign to them.
The question was originally worded as "ordered triples of sets"
A1, A2, A3 are an ordered triple because there's 3 sets. It's not a set of 3 triples.
It is always number of total players - 1, since each game produces a single loser, so you need 99 losers and 1 winner.
I don't really understand question 2. Are A1 A2 and A3 sets? If they are what does (A1, A2, A3) mean? I understand the solution but I can't grasp what the question asks really.
A1 A2 and A3 are sets and (A1,A2,A3) is an ordered triple which means it's a group of three elements or set of elements in our case. If you are familiar with the couple (x,y) it's basically the same thing but the triple is (x,y,z). One case in the exercise would be ((1,2,3),(4,5,6),(7,8,9,10))
In that case we can see
A1=(1,2,3)
A2=(4,5,6)
A3=(7,8,9,10)
And I made sure it fulfills the 2 conditions required in the exercise.
Here's another example of an ordered triple that would work
((1,5,7,9),(2,1),(3,6,2,8,4,10))
Now the exercise ask you the number of ordered triples possible. The term "ordered" means (A1,A2,A3) is different from (A2,A1,A3). If it was not ordered we would multiply the answer in the video by 3!=6 Because it's a permutation of 3 elements.
@@Fallilouseyeyour explanation has one slight issue. This is an ordered triple of sets, not an ordered triple of ordered sets. The order doesn't matter within the individual elements of the ordered triple. If you change the individual elements of the order triple to have set brackets {} instead, that resolves my complaint.
@@Fallilouseyealso, if the triples were not ordered, you would divide by 3! = 6 rather than multiplied by 6 to get the correct answer.
@@mike1024. I didn't say it's an ordered triple of ordered sets . If that was the case (1,2,3) would be different from (3,2,1) and that's a different exercise. In thoses sets there's no order and that simplifies the exercise
@@Fallilouseye I was more noticing how you used (2,1) do denote a set that's an element of the triple. If you want to stress that order in a set doesn't matter, you can do that, but more importantly, if you use parentheses, it implies order. Anyway, I'm saying that (2, 1) means something entirely different from {2, 1}. And in that notation, I'd probably write it {1, 2} anyway.
This is not the way that draws are made for any real tournaments. Minimising byes like this is unfair. All the byes come in the first round. With fhis then it is necessary to have 64 players left in the second round. So if we draw 72 playes to play each other we will have 36 who win. 28 players got a bye. That is 64 players then get into the second round.
The Putnam problem seems to be a trick question. The obvious answer is of course 6^10 (rewritten as 2^6 * 3*6 * 5*0 * 7*0), but this fails to take into account the possibility of, for instance, A1=A2, which would mean that (A1, A2, A3) is now actually the same triple as (A2, A1, A3).
Since A1 = A2 = A3 violates the intersection condition, we just need to take into account the 3 possibilites of A1=A2, A1=A3, and A2=A3. Each of these is equivalent to just asking the original question about an ordered pair (A1, N), so we can see that there are 3 * 2^10 duplicate triples that need to be removed.
Thus, the final answer is 6^10 - 3*2^10, which must be calculated and factored, an exercise left to the student.
There is no problem with A1=A2. 6^10 is correct.
E.g. replace 10 with 1, and the answer is 6¹1 , not 6^1 - 3*2^1 = 3:
empty, empty, {1}
empty, {1}, empty
{1}, empty, empty
empty, {1}, {1}
{1}, empty, {1}
{1}, {1}, empty
@@ronald3836 Hmm, yeah, I was somehow thinking that we'd end up like if you computed for N=1 two combinations, {empty, empty, {1}} and {empty, {1}, {1}}, and then found all the permutations of these, which would indeed include duplicates when you, for instance, swapped 2 empty's. But we're counting how many ways each digit can be mapped to the sets given our restrictions. Since each digit is completely independent of the others, the final answer is 10^6.
@@Keldor314 Yes, I think your calculation is a necessary step if you want to count the number of "unordered" triplets {A1,A2,A3}.
For every ordered triplet (A1,A2,A3), at most two are equal, and you have counted those.
To get to unordered, we note that each triplet {A1,A2,A3} with all sets different is counted 6 times in 6^10, and each triplet {A1,A2,A3} with not all sets different (i.e. exactly two the same) is counted 3 times.
super
Every number 1,...,10 occurs in exactly one set, and each set is identifiable and can take any amount of numbers, so we can just label each number with a set to put in, for a total of 3¹⁰ labellings/triples
Each number can be in exactly one or two sets. It is required that the intersection of A1, A2 and A3 is empty, but A1 and A2 (as well as A1 and A3, and A2 and A3) may have overlap.
So then you get 6^10.
In the World Cup, the remaining 16 teams compete in 8 eighth-finals, 4 quarter-finals, 2 semifinals and 1 final match. Which are 15. Well, and the reason there are actually 16 matches is that there is a match for place 3.
I think every World Cup there is a moment after the group stage where I want to count the total number of remaining matches and then realise it has to be the number of remaining teams (indeed because of the match for place 3).
Doesn't 6^10 only give you the number of sets {A1, A2, A3}? To get the ordered triples don't you have to multiply by 3!=6?
No - the ordered triples are factored in as part of the 6^10.
Let's say you had A1={1}, A2={2} and A3 = {3,...,10}. Then, 1 would be "in" A1 and "not" in A2 or A3, 2 would be "in" A2 and "not" in A1 or A3, and so on. If you were to put 1 "in" A2 and "not" in A1 or A3, and 2 "in" A1 and "not" in A2 or A3, that would be the same as simply swapping A1 and A2. In the same way, ordering those sets any other way would just be a different combination of "ins" and "nots". All of those combinations go into creating the 6^10, so there isn't any need to further take into consideration the ordering.
No. It says "Ordered triple (A1, A2, A3)", so A1 is always the first set in the triple, A2 always the second set, and A3 always the third set. So reordering the triple as (A2, A3, A1) is not allowed. Moreover, all possible combination distributions are already accounted for since each element from {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} has been given _6_ possible distributions (only in A1 ; only in A2 ; only in A3 ; in both A1 and A2 ; in both A2 and A3 ; in both A1 and A3).
And just FYI: please use spaces when writing "3! = 6" . Because the combination "!=" is also occasionally used to mean "is not equal to".
Problem 1:
Only 1 match is needed to determine the tournament winner, the final match. All the others leading up to that are not determining the tournament winner.
No, one match to determine the Finals winner. You have to account for the tournament field if that is the question. Nice job at trying to game the problem, though.
Presh: “Pause the video if you want to give these a try …”
Me: “HAHAHAHAHAHAHAHAHAHA” {gaping inhale} “HAHAHAHAHAHAHAHAHAHA”
I immediately said 99 as the logical answer, then reread the question, which states assuming a minimum number of byes. From this, I knew my answer was wrong as they were including byes as a match, otherwise it doesn't matter how many byes you choose to consider, the answer is 99.
But your answer is right and is valid for any (single-elimination) tournament structure. The info about byes was probably intended to trick you into thinking that you first need to determine the tournament structure.
That was like walking down the hall from kindergarten to grad school.
1:27 the average is actually considered the mean not median
The byes are confusing to think about, which is why you shouldn’t think about those. Exactly one player is eliminated if and only if exactly one match is played. Hence to eliminate 99 players, you need exactly 99 matches.
What does "ordered" triple mean here? I thought it meant the elements in A1 were less than or equal to the elements in A2, and so on.
For numbers is just 1,2,3 is different from, 3,2,1 or 2,1,3 - as set they are the same.
Ordered triple just means a group of 3 things where the order matters. So for example (1,2,3) is an ordered triple, which is not the same as (3,2,1)
It's basically the same thing as a 3-tuple.
@@sonobox-lu6mr Thanks!
@@Ninja20704 Thanks!
The phrasing of the Putnam question is wrong. The original does not say anything about "ordered", which would imply having to further reduce the answer by counting unique permutations, carefully avoiding double counting when two of the sets are equal.
The original statement does have "ordered", and this is correct. The solutions {1}, {2}, {3,..., 10} and {2} ,{1},{3,...,10} are distinct, i.e. count for 2, because of "ordered".
I wouldn't consider the 99 matches answer a "trick". I consider it the obvious and logical answer.
So you got 99 matches, but a trick ain't one?
Of 100 contestants, 99 need eliminated, so 99 matches
There's only one answer, but more than one way to find the answer.
I believe Presh used "trick" to mean "clever way to do something" rather than meaning it's somehow dishonest or false.
@@indigoziona I think what he said is that the trick is not clever. It is just that the regular way is the "illogical one"
I would say the tournament has 36 first round matches and 28 seeds. Still the matches come out to be 99. But it has 28 byes. But thats more ideal than going to semis not playing quarters
The fun thing about problem 1 is that you could do the matches any way you want. So long as the loser of a match is eliminated, there will always be 99 matches.
For example, you could have players 1 and 2 play, then the winner faces player 3. The winner of that match faces player 4, and so on. This will still be 99 matches, but they will all be done in series (i.e. sequentially). At best, this would mean players 1 and 100 play one match, and the rest play 2 matches. At worst, player 1 or 2 would have to play all 99 matches. On average, the winner of the tournament will have to play roughly half of the matches in this format.
Sure, but I'd imagine it would be rather annoying for player 1 if they won 98 matches in a row and lost the 99th and final match to a player on fresh legs lol
The answer to the tennis problem is 101.
Eliminating 99 players takes 99 matches. But when halving 50 until 1 is reached, there are 2 odd numbers, 25 and 3. That is 2 extra matches where no player gets eliminated, bringing the total number of matches to 101.
So as a non-tennis person how was I supposed to know if a "bye" is counted towards the matches played or not? After all the question states "how many matches are NEEDED", not "how many matches are ACTUALLY PLAYED"
The order of giving the bye is not correct in a real world (although it doesn't depend on the order as only internal nodes in the binary tree matters which is n-1) - In a real tournament the top 28 will not play the 1th round - and the remaining 72 will play the 1th round. Thus, you would have 64 players in the second round. These are all leaf nodes of a binary tree. The number of nodes inside the complete tree would be n-1 (63 matches). Hence 63 + 36 matches = 99. This should be the more realistic solution.
Technically the answer to Question 2 is incomplete. It is mathematically correct, but didn't follow the format required in the question. It should be 2^10*3^10*5^0*7^0.
Memo to CZcams: I boycott all products that you advertise.
There's no need to consider minimum number of byes. Each player must be eliminated or win at least 1 game. The number of players who need to lose is 99. There is only one winner. 99 losses means minimum 99 games.
That’s the most convoluted answer to Q1. You need to eliminate 99 players, one match at a time. 99 matches.
Right? Even the logical "short way" answer presented was way too long!
after 99 games ,there will be 99 people eliminated leaving a winner ,so we need 99 games
Very few Putnam questions are all that hard once you see the sneaky thought process behind them, but finding it is what makes them hard. That said, I have no idea why Presh felt the need to draw Venn diagrams when the answer was pretty much solved as soon as he broke down each number having 6 possibilities.
I think the people who thought the second problem was way over their head are probably lacking in understanding of all the notation used. Set theory has its own nuances that you definitely want to understand.
I would suppose that he gave the venn diagrams to help to visualise the distribution for those who are not too familiar with combinatorial problems.
@ mike119886 -- Wrong. Plenty of Putnam questions *ARE* all that hard. You are doing Monday morning quarterbacking with your statement, so you are very disingenuous as well as not accurate.
The reason for the unnecessary Venn diagrams *might* be that one of the solutions you can find with Google lists the 6 possibilties A1nA2, A1nA3, etc.
@@Ninja20704 But the effect is that anyone who was not already able to solve the prolbem by themself ended up only more confused.
The minimum byes condition makes 99 the only solution.. And not necessarily 1 champion who wins all, but rather an assumption that whoever has won a match against a player would certainly defeat anyone the defeated player had defeated.. So, in a sense, the 100th player enters the final directly
The minimum byes condition is superfluous. The answer is 99 no matter the tournament structure (provided it remains "single elimination").
Single elimination means that the winner does not lose and that each of the 99 other players loses exactly once.
It is further given that each match results in exactly one loser.
So you need 99 matches.
2nd problem, what do they mean by "ordered triples"? I would think an "ordered triple" (singular) would mean a set containing 3 numbers. But then the union of 3 such sets can't contain 10 numbers...?
I think it's basically asking "how many ways can you generate three sets A1, A2, A3 s.t. they follow the stated rules, order matters"
@@TimothyRE99oh, I guess "an ordered triple" here is a set of 3 sets, and they're asking how many of those... My mistake, thinking each A1, A2, and A3 were ordered triples individually.
Thanks.
@@ratamacue0320 Yeah. Ordered triple of sets simply meaning that, for example:
A1 = {1,2,3}; A2 = {4,5,6}; A3 = {7,8,9,10}
is counted as distinct from
A1 = {4,5,6}; A2 = {1,2,3}; A3 = {7,8,9,10}
despite being the same 3 sets, simply assigned different names.
@@TimothyRE99 would your 2nd example be one that fits the criteria? It looks like A1 U A2 U A3 = {4,5,6,1,2,3,7,8,9,10}, so no?
@@ratamacue0320 The sets themselves aren't ordered, just the triple.
Let's say S1 = {1,2,3}; S2 = {4,5,6}; S3 = {7,8,9,10}
In this case, the situation I previously described is (S1,S2,S3) ≠ (S2,S1,S3). The triples are ordered.
But the sets, generally, are not. {a,b,c} == {a,c,b} == {b,a,c} == ...
Thus, S1 U S2 U S3 == S2 U S2 U S3 == {1,2,3,4,5,6,7,8,9,10} == {4,5,6,1,2,3,7,8,9,10} == {10,3,8,5,2,7,6,9,4,1} == ...
Just watched a video about Wayne Gretzky so going with 99 for the first problem lol
Edit: Holy crap, it was the answer 😂😂😂
I've seen the first question, but it was as double elimination.
Every game eliminates exactly one player, and no player is eliminated twice, 99 players get eliminated, so whatever your schedule is, you'll have exactly 99 games.
This is a well-known theorem in computer science, every tree has one edge less than it has nodes, no matter its shape.
But can you prove that the tournament graph (players -> nodes, matches -> edges) is a tree in fewer words than your first sentence uses?
On the first question, the number of byes is irrelevant.
We could have had 36 matches in the first round (28 byes), to get numbers down to 64, with no more byes. This would still be 99 matches.
For the second question, I said each number could be in one or two of A1,A2,A3, creating 2^10. Then for each number, whether it is in 1 or 2 sets, there are 3 options for the set of sets it’s in (be it a pair or a single). This creates 3^10 options.
So I got to 2^10*3^10, multiplying these together.
You could also do the linear route, one match per round where the winner of of each match continues until they lose.
The number of byes is irrelevant, they put it in to trick you. Super common
Before watching:
Problem 1: 102 matches (of which 3 are byes)
I can't answer Problem 2 because I don't understand the question. The union of three ordered triples cannot contain ten elements!
Wait a minute… Problem 1 is not how in real life it happens.
Whilst you want to minimise the byes, you also want to get to a square number with fewer qualifications possible.
So you have 64 players qualified to the main tournament plus other 36 who lost in previous qualifiers
So you have 1+2+4+8+16+32 matches = 63 main matches + 36 losers… OH CRAP YOU’RE RIGHT… IT IS 99 WHATEVER WE DO 😮
if you do it mortal combat style it's 99 always, but your spine might get ripped out.
Technically, 2^10* 3^10 would not be given full marks on the Putnam examination. The problem specifically calls for the answer to be expressed in the form 2^a * 3^b * 5^c * 7^d, so the answer does need to be expressed in the equivalent form of 2^10 * 3^10 * 5^0 * 7^0.
While these are numerically equivalent answers, in a competition setting, you *must* follow the directives of the prompt to receive full marks!
I would argue that 2^10*3^10 is in the right format. The solutions I found on the internet indeed all stop there. (But it would be interesting to see the "official" grading instruction.)
I have no experience with these kinds of exams, but is that not just an example rather than a specific instruction? Isn't it just saying the answer should be expressed as the product of prime numbers? Why would you continue on to 5 and 7 if they aren't part of the solution? What if the solution had required 11?
@@SgtSupaman You must follow the format specified in the prompt if the prompt specifies the format.
In competition, prompts do not give examples nor typically require any particular formatting, so for most questions, any expression that is mathematically equivalent would suffice. When a prompt is specified, therefore, there's usually some reason for it, relevant to the rubric.
In fact, specifically /because/ the problem calls for this format, experienced test-takers can game the system a little bit and recognize that 11, or indeed any prime factor above 11, will not be a part of the solution.
First graders: "100-1" Solution: 99
Presh: "In a tennis tournament 100 players participate but only 1 player wins. Figure out how many players don't win. Find a general formula for any arbitrary number of participants." Solution: x-1
Part ii: proof it (obviously by induction)
@@nvapisces7011 "proof it" or "prove it" ?
"proof it" = "make it resistant to [some potential damaging/harmful factor]", for example, "make it waterproof/resistant to water".
@@yurenchu Why indulging in such a high IQ discussion lmao
Closest number over 100 that is a power of 2 is 128. So 127 matches, but 28 players are missing so 28 less matches. 127-28=99 Thats how I did it :))
That solution reads like you thought byes would count as matches as otherwise the problem would have been too easy, and then noticed they didn’t count as matches lol
Problem with Question 1, is that in tennis for most tournaments, a bye is only given for the first round. You don't get a bye for a quarterfinal match or any other.
Specifically how would a 100 person matchup be done then? Perhaps give 14 byes in the first round so that there are 64 teams in the second round? Powers of 2 work nicely with tournaments. But how would one determine which 14 players to give that bye?
@@mike1024. Normally, it would be put into 64 initial matches, with byes as needed to fill out the rest of the space, then you have a power of 2 and you can half it all the way down. (127 total matches including byes)
@@mike1024.If you google"Tournament Bracket Generator" you can do this easily. Still 99 matches though!
@@ingiford175ah, yes I see that I messed up. It would be 28 byes, not 14.
@@mike1024. Top 14 seeded players get byes.
Do 2009 A1 and B1! A1 I got right and B1 I got 5 points, A4 I got 1 point. Very proud of my 16!!
I know I got a 16, and I thought you could get a 5, and I know I got A1 right, and I felt great about B1, so I assumed I got half for it. Now I am learning about how it is scored and seeing that my instincts can't be right. Oh the assumptions I made as an undergrad.
The first question I got easy, only to be slapped with a 'hey, that was actually the hard way. You could've just logic-ed this'
I also use the pattern to find the answer: 2 tennis players need 1 match, 3 tennis players need 2 matches, 4 tennis players need 3 matches, and so on.
Therefore, n tennis players need n-1 matches to determine a winner.
first 50 matches result in 50 preliminary winners
25 more matches to narrow down to 25 preliminary winners
then 12 more matches to get down to 13
then 6 more to get down to 7
then 3 more to get down to 4
then 2 more to get down to the final 2
then 1 more to get the final winner
50 + 25 + 12 + 6 + 3 + 2 + 1 = 99
It always works out so nice when the number of players (teams) is a power of 2 since each round eliminates half the players. No "byes" are needed. Like the NHL play-offs starting with 16 teams. 4 rounds and 15 matches are needed: 8+4+2+1 = 15 = 16 - 1 = 2^4 - 1. So starting with 2^4 teams is very deliberate.
If not a power of then byes are usually granted at the start of the tournament and the number given makes sure that the number of matches in the first round is a power of 2. If there are 6 players then 2 byes gets you 8 players and 4 matches in the first round. Clear sailing after that.
100 players is a very awkward number to start with since the next power of 2 is 128. At any rate, 28 byes would be granted to the top 28 seeds giving you 2^7 - 1 = 127 "matches" in total. But 28 of these are "fake" so 127 - 28 = 99 real matches.
To minimise the number of byes, postpone them to later rounds as much as possible. Indeed not what happens in real tournaments because byes anyway do not count towards the total number of games needed, and it makes sense to minimise the number of games in the very first, largest round.
But you fell into the same trap I did initially. You made unnecessary assumptions about the structure of the tournament and did more math than needed. While you get to the same answer, this was a 2-second solve problem which was so obvious to me in hindsight! Math on this is not all that hard in the end - you can structure the tournament however you wanted and you'd come to the same answer no matter what. The issue will be how long did it take you to solve it!
@@ronald3836 in a real tournament, assigning byes in the first round benefits the high seeded players - which the fairest way to do the 1st draw.. 28 byes are needed no matter where you place them.
@@DavidDSimon Well, when I first saw the problem, 100-1 didn't take me too long.... Just presenting an alternative which mirrors the way byes are actually assigned and tournaments structured. Byes are always given in the first round. It's just nice to know the power of 2 relationship when making up the initial draw.
@@ianfowler9340 sure, but not related to the question.
Each match ends with one less player. We start at 100 and we need to go down to 1. We need 100-1=99 matches.
1:22 Average is NOT median...
You're conflating "average" with "mean"... the median is one of the types of average, with the other common ones being the mean and the mode. Presh didn't claim them to be synonyms, he just clarified which type of average holds.
Question 1: **simple, straightforward, good for children**
Question 2: **I, an adult, don’t understand any element of this question**
Is the first problem practical?
In a real 100 player tournament, 72 players would play 36 matches in the first round. The other 28 would receive a bye into 2nd round where they would meet the 36 winners of the first round. It would still be 99 matches in total.
@@BradburyNO Yep, they would play the amount of matches to get to 64 (a power of 2) players. So each person above 64 there will be a match to eliminate one of the 'extras' 100-64 = 36, which agrees with your first round.
First you have 50 matches featuring all 100 players. Then you have 25 matches featuring the 50 left over. Then you have 12.5 matches with the 25 people that are left over... The problem is now broken since there cannot be a match with only one contestant... Say you let one person skip several rounds, then you have 12 matches with 24 people +1extra person. Then you have 6 matches with the 12 people but there is still that one extra person who has no one to compete against. Then you get to 3 matches with 6 people, +1 extra contestant. Then 2 matches with the 3 from last round and the one extra. Then one final match. So assuming that the problem is not practical and you let a contestant skip some rounds, you need 50+25+12+6+3+2+1= 99 matches to get a single winner.
...I thought the bit about the average scores of students being 1 was a question 😅
I got the first one totally wrong. That’s because I just assumed, without reading properly, that they asked how many “rounds” of matches would be needed before there was a winner. Make sure to read the question properly, as they say.
i took the putnam 4 times, i've had enough. good video though
With 25 players and 12 matches... one player advances automatically to the next round? That is weird. I would say that 13 matches are required (one player -- say the one with the least amount of points -- has to play twice)... bringing total to 102 matches.
Automatic advancement without playing is a bye.
If you let the 25th player play one of the 12 winners, then that would result in an elimination of either the 25th player or of one of the 12 winners. Meaning you are left with 12 players, not 13.
@@ronald3836 Exactly my point... meaning that the video is wrong. (at 3:25)
@@gijsgijs2365 not your point, because you would still end up with 99 matches if you do the counting correctly. No matter how your structure the tournament, if it is single elimination, you need exactly 99 matches to determine one winner.
Once you understand the question, it's pretty straightforward to find out the answer: every time you divide the number of competitors by 2 to get the integer part of the quotient, and add the the remainder: 100/2 to get 50+0, •••, 25/2 to get 12+1=13, until the last one
I feel like the second question might be much easier to solve if it was better formulated. It’s not very comprehensible
It’s comprehensible if you know set notation. That said, I was still lost at it.
I dont think Presh answer is correct for problem 2..I got 1670 because you have three sets of triples so one of the digits is always left out correct? And why did he onlymdibtract two.otpion from 8..you cannot have in, in , and out because each element can only appear in one set st a time correct right NOT two? Anyone else see this?
I was very confused when I saw the 2nd question was on the putnam exam. It took me about 5 seconds to come up with the provided solution and so I watched the rest of the video to see in what way I misunderstood the problem only to find out it just was that simple.
I don't think I'd do well on the Putnam because it took me 3 hours to solve how much time I'd have per problem .
I once did a first round math olympiad where I stopped one hour early because I somehow did not manage to read my watch correctly. (Still made it through to the next round, though :-))
What if the winner was also the only person who got byed as the 25th, 13th and 7th participant O_O
That guy must've been lucky :>
An actual tournament would never work like that, all of the byes would be in round one, in a bracket made for 128 entries taking the field down to 64
100 players /2 players in a match =50 games
50 / 2 = 25 [+50]
25/2 = 12 games +1 player [+75 games]
13players /2 = 6 games +1 player [+ 87]
7 players/2 = 3 games +1 player [+93]
4 players/2 = 2 [+ 96]
2 players/2 = 1 [+98] =99 total games.
These seemed easy ones. Given the scores, I am guessing these were the easiest in the test. ??
Second problem has received some negative comments that it's not readily understandable. I concur, but IMO that is because it is so badly stated. The first three lines of the problem seem to contain a basic contradiction: 2nd & 3rd lines require A1, A2, A3 to be SETs. First line says that (A1,A2,A3) is an ordered triple, which implies that A1, A2, A3 are NUMBERS. Which is it? How do those statements play together? Is this just a deliberate misdirection?
It's the way math is. A math entity can be both an element and a set. The problem statements is actually enough to deduce that As are sets.
Ordered triples are not necessarily triples of numbers.
Yeah, but general public education tends not to go deep on any math topics so it's very likely general students are going to be confused, even though the problem statements are technically clear.
Nothing says the triple's elements are numbers.
Average is a synonym for mean, not for median.
Gud
If one is eliminated only after a loss... For only 1 winner there has to be 99 losers... Hence 99 matches