[ad_1]
Problem 1
Variations of this question have been asked on the SAT, Olympiad qualifying tests, and many other places.
In a singles tennis tournament, there are 100 players. Each match pairs two players; the winner advances and the loser is eliminated. Assuming a minimum number of byes (games in which a player automatically advances due to no opponent), how many matches are need to be played to determine a tournament winner?
Problem 2
This comes from the 1985 Putnam, A1.
Calculate the number of ordered triples (A1, A2, A3) such that:
A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A1 ∩ A2 ∩ A3 = ∅
Write your answer as 2a3b5c7d where a, b, c, d are non-negative integers.
As usual, watch the video for a solution.
When The Hardest Test Actually Had An Easy Question
Or keep reading.
.
.
“All will be well if you use your mind for your decisions, and mind only your decisions.” Since 2007, I have devoted my life to sharing the joy of game theory and mathematics. MindYourDecisions now has over 1,000 free articles with no ads thanks to community support! Help out and get early access to posts with a pledge on Patreon.
.
.
.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To 2 Counting Problems And Tricks You Should Know
(Pretty much all posts are transcribed quickly after I make the videos for them–please let me know if there are any typos/errors and I will correct them, thanks).
Problem 1
First let’s solve it the long way. In each round, we will pair up as many players as we can (we may have 1 unpaired player that gets a bye). Then we will count the number of players that are left, and continue pairing matches until 1 player is the champion.
At first there are 100 players, so that is 50 matches. After those matches are played, 50 players are eliminated leaving 100 – 50 = 50 players. We can then pair these players to 25 matches, which will eliminate 25 players and leave 50 – 25 = 25 players left.
Matches, Players Left
50, 50
25, 25
Now we can only pair 24 players into 12 matches, leaving 1 player with a bye. So 12 players get eliminated, and we are left with 25 – 12 = 13 players. Again we pair up all but 1 so we have 6 matches, and we then are left with 13 – 6 = 7 players. Once more we make 3 matches to eliminate 3 more players, so we have 7 – 3 = 4 players. We can then pair up the rest of the way. We pair into 2 matches to eliminate 2 players, leaving 4 – 2 = 2 players. These pair up in the championship, leaving just 1 champion.
Matches, Players Left
50, 50
25, 25
12, 13
6, 7
3, 4
2, 2
1, 1
The total number of matches is the sum of matches in each round on the left column. This is 50 + 25 + 12 + 6 + 3 + 2 + 1 = 99 matches.
But there is actually no need to do all of these calculations! There is an incredible shortcut to solve questions like this!
In each match, exactly 1 player is eliminated. In the end, there is 1 champion who never loses and 99 players that are eliminated, each in one match. Thus there must be 99 matches to eliminate the 99 players, and the answer is 99 matches!
Similarly if there are n players in a single-elimination tournament you would need n – 1 matches to eliminate all but 1 player. Incredible!
Problem 2
Let x be a number from {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. The number must be assigned to at least one set A1, A2, A3 but not all three. For each set, x can either be an element of the set or not. There are 2 possibilities for each of 3 sets, so there are 2×2×2 = 8 possibilities. However we must exclude x being contained in all 3 sets, and we must exclude x contained in none of the sets. So there are 8 – 2 = 6 possibilities.
The number of triples (A1, A2, A3) is equal to the number of ways to assign x to one of the 6 disjoint subsets. As each number has 6 possibilities, there are 610 = 210310 possibilities. That’s it; that is the answer!
Special thanks this month to:
Mike Robertson
Daniel Lewis
Kyle
Lee Redden
Thanks to all supporters on Patreon!
References
Problem 1
The College Panda
https://thecollegepanda.com/12-tricky-sat-math-questions/
Brainly
https://brainly.com/question/13082487
AoPS 2023 AMC 10B, P15
https://artofproblemsolving.com/wiki/index.php/2003_AMC_10B_Problems/Problem_15
Problem 2
1985 Putnam A1
https://prase.cz/kalva/putnam/psoln/psol851.html
Twitter
https://twitter.com/BannedIran/status/1416592272699842564/photo/1
1985 Putnam
https://kskedlaya.org/putnam-archive/1985.pdf
Math StackExchange
https://math.stackexchange.com/questions/1190662/1985-putnam-a1-solution
1985 Putnam solutions
https://math.berkeley.edu/~giventh/19109_85s.pdf
Other Putnam questions I’ve covered
1968 Putnam exam A1
An integral that implies pi is less than 22/7
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%?
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.
1994 Putnam A2
Finding the area of a sector of an ellipse
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 α?
MY BOOKS
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.
(US and worldwide links)
https://mindyourdecisions.com/blog/my-books
Mind Your Decisions is a compilation of 5 books:
(1) The Joy of Game Theory: An Introduction to Strategic Thinking
(2) 40 Paradoxes in Logic, Probability, and Game Theory
(3) The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias
(4) The Best Mental Math Tricks
(5) Multiply Numbers By Drawing Lines
The Joy of Game Theory shows how you can use math to out-think your competition. (rated 4.3/5 stars on 290 reviews)
40 Paradoxes in Logic, Probability, and Game Theory contains thought-provoking and counter-intuitive results. (rated 4.2/5 stars on 54 reviews)
The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 4.1/5 stars on 33 reviews)
The Best Mental Math Tricks teaches how you can look like a math genius by solving problems in your head (rated 4.3/5 stars on 116 reviews)
Multiply Numbers By Drawing Lines This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 4.4/5 stars on 37 reviews)
Mind Your Puzzles is a collection of the three “Math Puzzles” books, volumes 1, 2, and 3. The puzzles topics include the mathematical subjects including geometry, probability, logic, and game theory.
Math Puzzles Volume 1 features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 112 reviews.
Math Puzzles Volume 2 is a sequel book with more great problems. (rated 4.2/5 stars on 33 reviews)
Math Puzzles Volume 3 is the third in the series. (rated 4.2/5 stars on 29 reviews)
KINDLE UNLIMITED
Teachers and students around the world often email me about the books. Since education can have such a huge impact, I try to make the ebooks available as widely as possible at as low a price as possible.
Currently you can read most of my ebooks through Amazon’s “Kindle Unlimited” program. Included in the subscription you will get access to millions of ebooks. You don’t need a Kindle device: you can install the Kindle app on any smartphone/tablet/computer/etc. I have compiled links to programs in some countries below. Please check your local Amazon website for availability and program terms.
US, list of my books (US)
UK, list of my books (UK)
Canada, book results (CA)
Germany, list of my books (DE)
France, list of my books (FR)
India, list of my books (IN)
Australia, book results (AU)
Italy, list of my books (IT)
Spain, list of my books (ES)
Japan, list of my books (JP)
Brazil, book results (BR)
Mexico, book results (MX)
MERCHANDISE
Grab a mug, tshirt, and more at the official site for merchandise: Mind Your Decisions at Teespring.
[ad_2]