Math Jams

## Who Wants to Be a Mathematician, Round 2

Go back to the Math Jam Archive

AoPS instructor David Patrick will discuss the problems on Round 2 of qualifying for the 2019 Who Wants to Be a Mathematician Championship. We will be joined by Mike Breen and Bill Butterworth, the creators of the game. Mike is also the host of the Championship finals, to be held in Baltimore in January 2019.

#### Facilitator: Dave Patrick

DPatrick 2018-10-23 19:13:36
DPatrick 2018-10-23 19:30:12
I think we're ready to get started!
DPatrick 2018-10-23 19:30:16
Welcome to the 2018-19 Who Wants to Be a Mathematician Championship Round 2 Math Jam!
DPatrick 2018-10-23 19:30:25
I'm Dave Patrick, and I'll be leading our discussion tonight. Many of you know me from around AoPS: I've taught dozens of AoPS classes over the past 14 years, and I've written or co-written a few of our textbooks.
DPatrick 2018-10-23 19:30:39
I also once was a contestant on ABC's Who Wants to Be a Millionaire back before I started working at AoPS, way back when Regis Philbin was still the host. Here's a picture (I'm on the left, Regis is on the right):
DPatrick 2018-10-23 19:30:42
DPatrick 2018-10-23 19:30:46
Photo Credit: Maria Melin, copyright 1999 ABC Television.
j3370 2018-10-23 19:30:58
How much did you win!
DPatrick 2018-10-23 19:31:07
Well, I didn't win the million bucks, but I did win enough to buy a new car.
DPatrick 2018-10-23 19:31:19
Before we get started I would like to take a moment to explain our virtual classroom procedures to those who have not previously participated in a Math Jam or one of our online classes.
DPatrick 2018-10-23 19:31:35
The classroom is moderated, meaning that students can type into the classroom, but these comments will not go directly into the room. These comments go to the moderators, who may choose to share your comments with the room.
DPatrick 2018-10-23 19:31:49
This helps keep the class organized and on track. This also means that only well-written comments will be passed into the classroom, so please take time writing responses that are complete and easy to read.
DPatrick 2018-10-23 19:32:04
There are a lot of students here! As I said, only (a fraction of the) well-written comments will be passed to the entire group. Please do not take it personally if your comments do not get posted, and please do not complain about it. I expect this Math Jam to be much larger than our typical class, so please be patient with me---there are quite a few of you here tonight!!
DPatrick 2018-10-23 19:32:22
Also, we won't be going through the math quite as thoroughly as we do in our classes -- I can't teach all the material for every problem as we go. Another difference between tonight and our regular online classes is that it is very unlikely that we'll be able to answer every single question you ask. We usually do in our classes, but we have a large number of students tonight! So, please go ahead and ask questions, but also please understand if we aren't able to answer them all!
DPatrick 2018-10-23 19:32:37
Joining us tonight are the co-creators of WWTBAM, Mike Breen (mikebreen) and Bill Butterworth (TPiR).
mikebreen 2018-10-23 19:32:41
Hello, everyone.
DPatrick 2018-10-23 19:32:49
Mike taught at Alfred University and Tennessee Technological University before becoming AMS Public Awareness Officer in 2000. He and Bill began Who Wants to Be a Mathematician for the American Mathematical Society in 2001. The first national game was in 2010. Mike has been on Jeopardy! and Wheel of Fortune (if you want to know if he won lots of money on either show, note that he is still working for a living) and may be the only person ever to cut his hand on the wheel. Who Wants to Be a Mathematician has so far been much safer.
TPiR 2018-10-23 19:33:03
Hi everyone!
DPatrick 2018-10-23 19:33:08
Bill earned an undergraduate degree in mathematics from Santa Clara University and a Ph.D. from Northwestern University, and is currently an associate professor and associate chair of mathematics at DePaul University. He shares a life-long interest in game shows with colleague Mike Breen, with whom he works as the not-so-lovely assistant on the mathematics game show Who Wants to Be a Mathematician.
DPatrick 2018-10-23 19:33:17
And do you know why TPiR is his username?
Mathisfun04 2018-10-23 19:33:37
the price is right?
KSS 2018-10-23 19:33:37
The Price is right?
champion999 2018-10-23 19:33:37
the price is right!
alex7 2018-10-23 19:33:37
The Price is Right
WLongtin 2018-10-23 19:33:37
the price is right!
DPatrick 2018-10-23 19:33:43
Yes! In addition to authoring articles and presenting talks related to game-show mathematics, Bill served as mathematics consultant to the CBS television show The Price is Right from 1997 to 2009. (Hence, his username.)
DPatrick 2018-10-23 19:33:55
As you can see, we have a lot of game show background here tonight!
DPatrick 2018-10-23 19:34:04
Finally, we have a very special guest here with us tonight. Ken Ono (KenOno) is a professor of mathematics at Emory University and is Vice President of the American Mathematical Society (AMS), which sponsors Who Wants to Be a Mathematician. The AMS promotes mathematical research, fosters excellence in mathematics education, and increases the awareness of the value of mathematics to society.
KenOno 2018-10-23 19:34:23
Hi there.
DPatrick 2018-10-23 19:34:32
Ken is also the Director of the "Spirit of Ramanujan" project, which AoPS is also a partner with. If you'd like to learn more about Spirit of Ramanujan, please attend our Math Jam next week, October 30, at this same time, where we'll talk about Ramanujan's life, his mathematics, and the Spirit of Ramanujan talent search program.
DPatrick 2018-10-23 19:35:09
Or if you can't make the Math Jam next Tuesday, visit spiritoframanujan.com to learn more.
KSS 2018-10-23 19:35:17
There are a lot of cool people here today!
DPatrick 2018-10-23 19:35:22
Wait, one more!
DPatrick 2018-10-23 19:35:28
We also have an assistant here to help out tonight: Zach Stein-Perlman (ZachSteinPerlman). Zach has loved mathematics, brainteasers, and logic puzzles for longer than he can remember. He joined AoPS in 2011, back in the days when you faxed in homework. In addition to math, Zach is interested in philosophy and government. In his free time, Zach likes reading fantasy novels, cuddling with his cats, and running half marathons.
DPatrick 2018-10-23 19:35:47
Zach can try to help you if you have a question or are having some other difficulty. He may open a private window with you to chat if needed.
DPatrick 2018-10-23 19:36:10
Tonight we'll be talking about Round 2 of the 2018-19 WWTBAM Championship contest, which concluded yesterday. Round 2 was only open to students who scored 7 or better (out of 10) on Round 1, which was held in September.
DPatrick 2018-10-23 19:36:24
Round 2 consisted of 10 questions, with a 15-minute time limit. So the problems are quick: you have an average of 90 seconds per question. (But as we'll see as we work through the problems, some of them may not take you nearly that long.) No books, notes, calculators, or internet access was permitted during the contest.
DPatrick 2018-10-23 19:36:45
We'll take a bit longer than 15 minutes tonight (probably about an hour), because we'll stop along the way to discuss each question. Please also remember that the purpose of this Math Jam is to work through the solutions to the problems, and not to merely present the answers. "Working through the solutions" often includes discussing problem-solving tactics. So please, when a question is posted, do not simply respond with the final answer.
DPatrick 2018-10-23 19:37:03
And here is problem #1:
DPatrick 2018-10-23 19:37:07
1. Find the remainder when $2019^{2019} + 2020^{2019}$ is divided by $7$.
DPatrick 2018-10-23 19:37:14
(Most of the questions are short-answer.)
Mathisfun04 2018-10-23 19:37:40
motorfinn 2018-10-23 19:37:40
Does this have something to do with using Modular Arithmetic?
DPatrick 2018-10-23 19:37:49
Good idea. We can use modular arithmetic and work modulo $7$. (If you haven't seen this before, basically we're just going to keep track of remainders).
DPatrick 2018-10-23 19:38:09
In particular, what are $2019$ and $2020$ modulo $7$? (Meaning, what are their remainders when we divide by $7$?)
motorfinn 2018-10-23 19:38:35
2019 mod 7 is equal to 3 I believe
asdf334 2018-10-23 19:38:35
3 and 4
RuiyangWu 2018-10-23 19:38:35
2019 modulo 7 is 3, 2020 modulo 7 is 4
lkarhat 2018-10-23 19:38:35
3 and 4
motorfinn 2018-10-23 19:38:35
And similarly, 2020 is 7 mod 4.
JotatD 2018-10-23 19:38:35
3 and 4
Mathisfun04 2018-10-23 19:38:35
3 and 4 mod 7 respectively
DPatrick 2018-10-23 19:38:41
Right. $2019 = 288 \cdot 7 + 3$, so $2019 \equiv 3 \pmod{7}$.
DPatrick 2018-10-23 19:38:49
And thus $2020 \equiv 4 \pmod{7}$. (It's just one more.)
DPatrick 2018-10-23 19:38:53
So what we're trying to compute is the residue $3^{2019} + 4^{2019} \pmod{7}$.
sbudaraj 2018-10-23 19:39:14
now we use euler's
motorfinn 2018-10-23 19:39:14
Do we find a pattern with the residues?
DPatrick 2018-10-23 19:39:30
Certainly we could use Fermat's Little Theorem, or experimentally determine, the two terms mod $7$ and work from there, but what's a simpler way?
champion999 2018-10-23 19:39:49
3 and -3
sbudaraj 2018-10-23 19:39:49
4 = (-3) mod 7
DPatrick 2018-10-23 19:39:54
Very nice.
DPatrick 2018-10-23 19:39:59
Note that $4 \equiv -3 \pmod{7}$!
DPatrick 2018-10-23 19:40:07
So our quantity modulo $7$ is $3^{2019} + (-3)^{2019} \pmod{7}$.
RuiyangWu 2018-10-23 19:40:15
so is the answer 0, then?
motorfinn 2018-10-23 19:40:15
Would they then sum to 0?
sbudaraj 2018-10-23 19:40:22
WOAH OMG IT CANCELS.≥ its 0
Krypton36 2018-10-23 19:40:22
0
DPatrick 2018-10-23 19:40:26
And now we don't have to break a sweat at all!
DPatrick 2018-10-23 19:40:30
$3^{2019} + (-3)^{2019} \equiv 3^{2019} - 3^{2019} \equiv 0 \pmod{7}$.
DPatrick 2018-10-23 19:40:37
So the answer is $\boxed{0}$.
Justin04 2018-10-23 19:40:55
That's very slick
DPatrick 2018-10-23 19:41:07
Indeed. I like it when I don't have to do a lot of computation. There's another quick way to solve the problem, using a little bit of algebra.
DPatrick 2018-10-23 19:41:12
How can we factor $a^n + b^n$ when we know $n$ is odd?
DPatrick 2018-10-23 19:41:30
If we're not sure of the general case, we can try a small example.
BBBBMMMMLLLLE 2018-10-23 19:41:40
a^3+b^3
asdf334 2018-10-23 19:41:42
a^3 + b^3?
DPatrick 2018-10-23 19:41:49
Sure -- How does $a^3 + b^3$ factor?
champion999 2018-10-23 19:42:08
(a+b)(a^2-ab+b^2)
asdf334 2018-10-23 19:42:08
(a + b)(a^2 - ab + b^2)
Mathisfun04 2018-10-23 19:42:08
(a+b)(a^2-ab+b^2)
Puddles_Penguin 2018-10-23 19:42:08
(a+b)(a^2-ab+b^2)
dajeff 2018-10-23 19:42:08
$(a+b)(a^2-ab+b^2)$
DPatrick 2018-10-23 19:42:12
It factors as

$$a^3 + b^3 = (a+b)(a^2-ab+b^2).$$

DPatrick 2018-10-23 19:42:22
And more generally,

$$a^n + b^n = (a+b)(a^{n-1} - a^{n-2}b + a^{n-3}b^2 - a^{n-4}b^3 + \cdots - ab^{n-2} + b^{n-1}).$$
DPatrick 2018-10-23 19:42:34
This only works when $n$ is odd (since we need it to end with a $+$ sign at $b^{n-1}$).
DPatrick 2018-10-23 19:43:00
So in particular, in our example:

$$2019^{2019} + 2020^{2019} = (2019+2020)(\text{some big number}).$$
champion999 2018-10-23 19:43:15
=0 b/c 2019+2020=0 mod 7
Mathisfun04 2018-10-23 19:43:17
we know 2019+2020=3+4=0mod7!
DPatrick 2018-10-23 19:43:25
Right: that's good enough!

$2019 + 2020 = 4039$ is a multiple of $7$!. Specifically, $4039 = 7 \cdot 577$.

So the whole thing is a multiple of $7$. Hence the remainder is $0$.
DPatrick 2018-10-23 19:43:46
On to #2:
DPatrick 2018-10-23 19:43:51
2. If $n$ is the fifth power of a positive integer, which of the following could be the number of positive integer divisors (or factors) of $n$? (Including $1$ and $n$)

(a) $451$ (b) $452$ (c) $453$ (d) $454$ (e) $455$
aops008 2018-10-23 19:44:25
Use prime factorization
asdf334 2018-10-23 19:44:43
so if n were prime, there would be 6
DPatrick 2018-10-23 19:44:52
Right, primes are probably the key.
DPatrick 2018-10-23 19:45:10
And to slightly clarify what asdf334 said, I think you mean that if $n = p^5$ where $p$ is some prime, then there are $6$ factors.
DPatrick 2018-10-23 19:45:27
What's another easy sort of number to compute the number of factors of?
DPatrick 2018-10-23 19:45:44
Remember, the phrase "could be" in the problem means that we just have to find a single example that works.
PCampbell 2018-10-23 19:45:55
$p^{10}$
DPatrick 2018-10-23 19:46:09
Right, or more generally any 5th power of a prime power.
Blackhawk 2018-10-23 19:46:25
2^450 has 451 divisors
DPatrick 2018-10-23 19:46:27
Aha!
DPatrick 2018-10-23 19:46:37
If $p$ is prime, then $p^{5k} = (p^k)^5$ has $5k+1$ factors.
DPatrick 2018-10-23 19:46:55
And as Blackhawk's example shows, $\boxed{(a)}$ $451$ clearly works when $k = 90$.
asdf334 2018-10-23 19:47:07
2^10 * 3^40 also has 451
DPatrick 2018-10-23 19:47:15
Right: certainly there are lots of examples.
DPatrick 2018-10-23 19:47:37
It requires just a little more work to show that the other answer choices can't happen, but it's not too difficult and I think I'll leave it for you to explore if you like.
DPatrick 2018-10-23 19:48:12
And you can probably prove the more general statement that the number of divisors of an $n$th power must be equivalent to $1 \pmod{n}$.
DPatrick 2018-10-23 19:48:31
(The simplest example is that a perfect square always has an odd number of factors.)
DPatrick 2018-10-23 19:48:40
Next up:
DPatrick 2018-10-23 19:48:46
3. How many solutions are there to $\sin(4x) = \cos(2x)$ in $[0,2\pi]$? ($x$ in radians)
DPatrick 2018-10-23 19:49:01
There are a couple of ways we can approach this.
aops008 2018-10-23 19:49:35
Double angle formula
Blackhawk 2018-10-23 19:49:35
graph it
PCampbell 2018-10-23 19:49:44
Use the identity $\sin(2u)=2\sin(u)\cos(u)$, where $u=2x$.
DPatrick 2018-10-23 19:49:59
Those are the two ways that I thought of.
DPatrick 2018-10-23 19:50:14
I always like to try to answer questions like this by sketching a graph if it's easy enough.
DPatrick 2018-10-23 19:50:24
And I think this one probably *is* easy enough.
DPatrick 2018-10-23 19:50:30
DPatrick 2018-10-23 19:50:42
$y = \sin(4x)$ is in blue. Note it starts at $(0,0)$ and makes $4$ complete cycles between $x=0$ and $x=2\pi$.
DPatrick 2018-10-23 19:50:47
$y = \cos(2x)$ is in red. Note it starts at $(0,1)$ and makes $2$ complete cycles between $x=0$ and $x=2\pi$.
DPatrick 2018-10-23 19:51:01
And your sketch doesn't have to be as accurate as mine to see what's going on.
potato36 2018-10-23 19:51:04
So we simply count the interseciotns
aops008 2018-10-23 19:51:10
So it's 8
asdf334 2018-10-23 19:51:10
8 solutions!
DPatrick 2018-10-23 19:51:26
Indeed, I count $\boxed{8}$ intersection points.
aops008 2018-10-23 19:51:34
How do we do it with double angle formula
DPatrick 2018-10-23 19:51:40
Good question -- let's see.
DPatrick 2018-10-23 19:51:50
We use the trig identity $\sin(2\theta) = 2\sin(\theta)\cos(\theta)$.
DPatrick 2018-10-23 19:51:56
Then our equation becomes

$$2\sin(2x)\cos(2x) = \cos(2x).$$
DPatrick 2018-10-23 19:52:12
So there are two types of solutions to this: what are they?
kdep 2018-10-23 19:52:43
factor out cos(2x)
geniusofart 2018-10-23 19:52:43
one is cos(2x)=0
DPatrick 2018-10-23 19:52:52
Right. One solution is $\cos(2x) = 0$.
geniusofart 2018-10-23 19:52:57
and the other is cos(2x) is cancel from both sides
WLongtin 2018-10-23 19:52:59
cos(2x) = 0 or sin(2x) = 1/2
asdf334 2018-10-23 19:53:02
sin(2x) = 1/2
DPatrick 2018-10-23 19:53:20
Exactly: if the $\cos$ term is nonzero, we divide by it and get $2\sin(2x) = 1$, so $\sin(2x) = \frac12$ is the other set of solutions.
DottedCaculator 2018-10-23 19:53:36
4 solutions for each
DPatrick 2018-10-23 19:54:23
Exactly.
DPatrick 2018-10-23 19:54:31
$\cos(2x) = 0$ has two solutions with $0 \le 2x \le \pi$: either $2x = \frac\pi2$ or $2x = \frac{3\pi}{2}$.
DPatrick 2018-10-23 19:54:47
So it has four solutions with $0 \le 2x \le 2\pi$.
DPatrick 2018-10-23 19:55:02
$\sin(2x) = \frac12$ has two solutions with $0 \le 2x \le \pi$: either $2x = \frac\pi6$ or $2x = \frac{5\pi}{6}$. So again, four with $0 \le 2x \le 2\pi$.
motorfinn 2018-10-23 19:55:10
So we achieve our same end result of 8
DPatrick 2018-10-23 19:55:20
Right, that's $4+4 = \boxed{8}$ solutions total.
DPatrick 2018-10-23 19:55:56
The first three problems were all roughly equal in difficulty: about 1/3 of students taking Round 2 got each of them correct.
DPatrick 2018-10-23 19:56:15
The next two problems (4 and 5) were actually the easiest: about half got #4, which is...
DPatrick 2018-10-23 19:56:23
4. What is the next term in this geometric sequence: $\sqrt2$, $\sqrt[3]{2}$, $\sqrt[6]{2}$ ?
DPatrick 2018-10-23 19:56:44
This may be hard to read on your screen: the second term is the cube-root of $2$, and the third term is the sixth-root of $2$.
DPatrick 2018-10-23 19:57:08
And since they're so hard to read, and to work with, what's a better way to write them to make them easier to work with?
motorfinn 2018-10-23 19:57:23
Does it have something to do with raising to fractional powers?
geniusofart 2018-10-23 19:57:23
fractional powers
asdf334 2018-10-23 19:57:23
make it into exponents
moab33 2018-10-23 19:57:26
$2^\frac{1}{2}, 2^\frac{1}{3}…$
DPatrick 2018-10-23 19:57:29
We can write them as fractional powers of $2$:

$$2^{\frac12},\, 2^{\frac13},\, 2^{\frac16},\, \underline{\phantom{2^{\frac{x}{y}}}}$$
DPatrick 2018-10-23 19:57:38
What goes in the blank?
KnightatNight 2018-10-23 19:57:58
1
spartacle 2018-10-23 19:57:58
1
WLongtin 2018-10-23 19:57:58
1
Puddles_Penguin 2018-10-23 19:57:58
1
smart_person_2000IQ 2018-10-23 19:57:58
1
1
Puddles_Penguin 2018-10-23 19:57:58
Is it 1?
2^0=1
asdf334 2018-10-23 19:57:58
1.
PCampbell 2018-10-23 19:57:58
$2^{\frac{0}{6}}=1$
DPatrick 2018-10-23 19:58:02
Right!
DPatrick 2018-10-23 19:58:23
If the powers of $2$ form a geometric sequence, then the exponents must form an arithmetic sequence!
DPatrick 2018-10-23 19:58:43
Or you could note that the common ratio of the geometric sequence is $2^{\frac16}$ -- specifically, we're multiplying by $2^{-\frac16}$ to get from one term to the next.
DPatrick 2018-10-23 19:58:55
...which decreases the exponent by $-\frac16$ each time.
DPatrick 2018-10-23 19:59:04
So the next term is $2^0$, or $\boxed{1}$.
DPatrick 2018-10-23 19:59:40
On to #5, which turned out to be the easiest problem of the set.
DPatrick 2018-10-23 19:59:46
5. If $a$ is a positive real number, in how many points can the graphs of $y=ax$ and $y=x^2+1$ intersect?

(a) $0$ only (b) $0$ or $1$ only (c) $0$ or $2$ only (d) $1$ or $2$ only (e) $0$, $1$, or $2$
asdf334 2018-10-23 20:00:33
ax = x^2 + 1
champion999 2018-10-23 20:00:33
Graph it!
cai40 2018-10-23 20:00:33
We should draw the graph of y=x^2+1
DPatrick 2018-10-23 20:00:45
Indeed, just like the trig problem, we can solve this using algebra or by sketching graphs.
DPatrick 2018-10-23 20:00:49
Let's do the algebra first.
DPatrick 2018-10-23 20:00:57
We're trying to count the number of $x$'s such that $ax = x^2 + 1$.
DPatrick 2018-10-23 20:01:03
This rearranges to $x^2 - ax + 1 = 0$.
DPatrick 2018-10-23 20:01:14
How do we determine how many (real) solutions this has?
champion999 2018-10-23 20:01:26
Look at the discriminant
asdf334 2018-10-23 20:01:26
sbudaraj 2018-10-23 20:01:26
TAKE THE DETERMINANT
nawakre 2018-10-23 20:01:26
PCampbell 2018-10-23 20:01:26
dajeff 2018-10-23 20:01:26
discriminant
DPatrick 2018-10-23 20:01:38
We can write the solutions explicitly using the quadratic formula.
DPatrick 2018-10-23 20:01:48
$x = \dfrac{a \pm \sqrt{a^2-4}}{2}$
DPatrick 2018-10-23 20:02:08
And as many of you pointed out, it's the discriminant $a^2 - 4$ that determines how many solutions there are.
Assassino9931 2018-10-23 20:02:27
x^2 - ax + 1 = 0 has discriminant a^2 - 4 which can be both negative, 0 and positive
novus677 2018-10-23 20:02:41
This is a quadratic and has 0,1, or 2 solutions
kdep 2018-10-23 20:02:45
discriminant must be greater than zero for it to be real
DPatrick 2018-10-23 20:02:50
If $a^2 - 4 < 0$, then there are no solutions.

If $a^2 - 4 = 0$, then there is 1 solution.

If $a^2 - 4 > 0$, then there are 2 solutions.
DPatrick 2018-10-23 20:02:59
But these can all happen!
DPatrick 2018-10-23 20:03:11
If $a < 2$, then there are no solutions.

If $a = 2$, then there is 1 solution.

If $a > 2$, then there are 2 solutions.
JotatD 2018-10-23 20:03:20
0,1,2
Hermain 2018-10-23 20:03:20
so it must be e because it's the only one with 3 options
DottedCaculator 2018-10-23 20:03:20
DPatrick 2018-10-23 20:03:23
So the answer is $\boxed{\text{(e)}}$.
DPatrick 2018-10-23 20:03:40
And we could also solve this by sketching graphs.
DPatrick 2018-10-23 20:03:49
The graph of $y = x^2 + 1$ is an upwards-opening parabola with vertex at $(0,1)$:
DPatrick 2018-10-23 20:03:53
DPatrick 2018-10-23 20:04:04
The graph of $y = ax$ (with $a > 0$) is a line through the origin $(0,0)$ with positive slope.
DPatrick 2018-10-23 20:04:25
Is it clear that such a line could intersect in $0$, $1$, or $2$ points?
DPatrick 2018-10-23 20:04:40
If $a$ is small, then the line will miss the parabola completely:
DPatrick 2018-10-23 20:04:44
DPatrick 2018-10-23 20:04:53
If $a$ is big, then we'll cross the parabola twice:
DPatrick 2018-10-23 20:04:57
DPatrick 2018-10-23 20:05:06
And can we glance and touch the parabola exactly once!
JotatD 2018-10-23 20:05:11
1 WHEN IS TANGENT
motorfinn 2018-10-23 20:05:31
Yes, if we make it tangent
KSS 2018-10-23 20:05:31
When tangent
DPatrick 2018-10-23 20:05:32
Yes. Without doing any algebra, you can think of rotating the red line from the first image counterclockwise. At some point it will exactly touch the parabola.
DPatrick 2018-10-23 20:05:37
DPatrick 2018-10-23 20:05:47
So the answer is $\boxed{\text{(e)}}$.
DPatrick 2018-10-23 20:06:11
Now the problems get a bit harder. Here's #6:
DPatrick 2018-10-23 20:06:16
6. Express $\displaystyle\sum_{n=1}^{10}\frac{2}{n(n+2)} - \sum_{n=1}^{10}\frac{1}{n(n+1)}$ as a fraction in lowest terms.
DPatrick 2018-10-23 20:06:36
That $\displaystyle\sum$ symbol might be confusing.
DPatrick 2018-10-23 20:06:43
It means "sum." In particular, $\displaystyle\sum_{n=1}^{10}$ means the sum of all the terms where we plug in $n=1$, $n=2$, $n=3$, all the way up to $n=10$.
DPatrick 2018-10-23 20:06:51
That is,

$\sum_{n=1}^{10}\frac{2}{n(n+2)} = \frac{2}{1(3)} + \frac{2}{2(4)} + \frac{2}{3(5)} + \cdots + \frac{2}{10(12)}.$
DPatrick 2018-10-23 20:07:00
Wow, that seems like a pain to add up.
novus677 2018-10-23 20:07:07
partial fraction decomposition and telescoping
arjvik 2018-10-23 20:07:07
PFD?
DPatrick 2018-10-23 20:07:18
Fortunately, there's a little trick that helps with this, called partial fraction decomposition.
DPatrick 2018-10-23 20:07:51
Basically, we want to write $\dfrac{2}{n(n+2)}$ as a sum or difference of two separate fractions, one with denominator $n$ and one with denominator $n+2$.
DPatrick 2018-10-23 20:08:05
It's a little bit of guess-and-check to figure it out.
novus677 2018-10-23 20:08:22
$\frac{1}{n}-\frac{1}{n+2}$
DPatrick 2018-10-23 20:08:29
That's right:

$$\frac{2}{n(n+2)} = \frac{1}{n} - \frac{1}{n+2}$$
DPatrick 2018-10-23 20:08:50
You can put it over a common denominator to check, the $n$'s will cancel out and we'll just have $2$ in the numerator.
DPatrick 2018-10-23 20:09:03
So let's write it out for our first sum:

$$\sum_{n=1}^{10} \frac{2}{n(n+2)} = \sum_{n=1}^{10}\left(\frac{1}{n} - \frac{1}{n+2}\right)$$
DPatrick 2018-10-23 20:09:11
It's not clear that this helps...
DPatrick 2018-10-23 20:09:30
But if we write it without the $\displaystyle\sum$ notation it's a lot easier to see what's going on.
DPatrick 2018-10-23 20:09:37
$$\left(\frac11-\frac13\right) + \left(\frac12-\frac14\right) + \left(\frac13-\frac15\right) + \left(\frac14 - \frac16\right) + \cdots$$
DPatrick 2018-10-23 20:10:06
Notice anything interesting?
mathlogician 2018-10-23 20:10:18
It telescopes
PCampbell 2018-10-23 20:10:18
Term cancellation
nawakre 2018-10-23 20:10:18
some fractions cancel out
sbudaraj 2018-10-23 20:10:18
TELESCOPE
asdf334 2018-10-23 20:10:18
it cancels
phoenix9 2018-10-23 20:10:20
they cancel out!!!
harsha12345 2018-10-23 20:10:24
most terms cancel ouy\
asdf334 2018-10-23 20:10:27
you are left with 1/1, -1/11, 1/2, and -1/12?
DPatrick 2018-10-23 20:10:30
The $-\dfrac13$ in the first term will cancel with the $\dfrac13$ in the third term!
DPatrick 2018-10-23 20:10:36
The $-\dfrac14$ in the second term will cancel with the $\dfrac14$ in the fourth term!
DPatrick 2018-10-23 20:10:40
And so on!
DPatrick 2018-10-23 20:10:43
The only terms that don't cancel are $\dfrac11 + \dfrac12 - \dfrac{1}{11} - \dfrac{1}{12}$.
DPatrick 2018-10-23 20:11:00
Let's leave it like this for now -- remember this is only the first sum in our expression. Some of these might cancel further with terms from the second sum.
motorfinn 2018-10-23 20:11:03
Can we do the same for the second?
WLongtin 2018-10-23 20:11:03
so do the same for the second one
DPatrick 2018-10-23 20:11:14
So now we try to compute $\displaystyle\sum_{n=1}^{10} \frac{1}{n(n+1)}$. We can use the same sort of idea.
DPatrick 2018-10-23 20:11:31
This one is a little simpler:

$$\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}.$$
DPatrick 2018-10-23 20:11:41
So the sum becomes:

$$\left(\frac11 - \frac12\right) + \left(\frac12 - \frac13\right) + \left(\frac13 - \frac14\right) + \cdots$$
kcbhatraju 2018-10-23 20:11:45
Telescoping sum for second as well!
asdf334 2018-10-23 20:12:00
1/1 and -1/11
JotatD 2018-10-23 20:12:00
another cancelation
DottedCaculator 2018-10-23 20:12:00
1/1-1/11
cai40 2018-10-23 20:12:09
we end up wwith 1/1-1/11
DPatrick 2018-10-23 20:12:10
All the terms cancel except $\dfrac11 - \dfrac{1}{11}$.
DPatrick 2018-10-23 20:12:16
So our entire expression is $$\left(\dfrac11 + \dfrac12 - \dfrac{1}{11} - \dfrac{1}{12}\right) - \left(\dfrac11 - \dfrac{1}{11}\right).$$
DPatrick 2018-10-23 20:12:33
That's great -- even more cancellation!
asdf334 2018-10-23 20:12:38
when you subtract it from the first term, you get $\frac{1}{2}-\frac{1}{12}$
kdep 2018-10-23 20:12:38
1/2 - 1/12
motorfinn 2018-10-23 20:12:41
1/2-1/12
motorfinn 2018-10-23 20:12:41
so 5/12
PCampbell 2018-10-23 20:12:41
so $\frac{1}{2} - \frac{1}{12}$
DPatrick 2018-10-23 20:12:44
What's left is just $\dfrac12 - \dfrac{1}{12}$.
DPatrick 2018-10-23 20:12:52
And this is just $\dfrac{6}{12} - \dfrac{1}{12} = \boxed{\dfrac{5}{12}}$.
DPatrick 2018-10-23 20:13:09
This tactic of writing each term of a sum as a difference of two terms, in order to get mass cancellation, is called a telescoping sum.
DPatrick 2018-10-23 20:13:34
On to #7:
DPatrick 2018-10-23 20:13:38
7. The regular octagon pictured has side length $5$. What is the nearest integer to the length of $AB$?
DPatrick 2018-10-23 20:13:41
DPatrick 2018-10-23 20:13:57
Hmmm...any ideas?
RuiyangWu 2018-10-23 20:14:22
draw triangles
KSS 2018-10-23 20:14:22
Make some triangles?
asdf334 2018-10-23 20:14:22
make a right triangle
cai40 2018-10-23 20:14:22
PYTHAGOREAN THEOROM?
asdf334 2018-10-23 20:14:22
with AB as hypotenuse
sbudaraj 2018-10-23 20:14:22
Draw right triangle CAB
RuiyangWu 2018-10-23 20:14:22
right triangle hypotenuse
motorfinn 2018-10-23 20:14:22
We could use Pythagorean Theorem
DPatrick 2018-10-23 20:14:28
One idea is that $AB$ is the hypotenuse of the green right triangle:
DPatrick 2018-10-23 20:14:30
DPatrick 2018-10-23 20:14:40
One leg is easy: $AX = 5$.
DPatrick 2018-10-23 20:14:44
But what is $XB$?
WLongtin 2018-10-23 20:15:24
yes and also a small 45 45 90 triangle around each vertex
Vexaria 2018-10-23 20:15:24
make another 45 45 90 triangle with side 5 as hypt
amuthup 2018-10-23 20:15:24
draw a square around the octagon
PCampbell 2018-10-23 20:15:24
Connect the top vertices to $XB$ such that the connections are perpendicular
DPatrick 2018-10-23 20:15:39
There's a couple of ways to do this, but I think they're essentially the same work.
DPatrick 2018-10-23 20:15:48
I drew a couple of perpendiculars:
DPatrick 2018-10-23 20:15:52
DPatrick 2018-10-23 20:15:59
Now $XB$ is broken up into 3 segments.
DPatrick 2018-10-23 20:16:06
The middle segment has the same length as $YZ$, which is $5$.
DPatrick 2018-10-23 20:16:31
And the two outside segments are each legs of a 45-45-90 triangle with hypotenuse $5$.
skrublord420 2018-10-23 20:16:39
Project other vertices onto $XB$ to find that $XB = 5/\sqrt{2} + 5 + 5/\sqrt{2} = 5 + 5\sqrt{2}.$
WLongtin 2018-10-23 20:16:39
5 + 2 * 5/root(2)
motorfinn 2018-10-23 20:16:39
5+5sqrt2
DPatrick 2018-10-23 20:16:47
Right. Each is $\frac{5}{\sqrt2}$, and together they are $2 \cdot \frac{5}{\sqrt2} = 5\sqrt2$.
DPatrick 2018-10-23 20:16:51
So combined, $XB = 5 + 5\sqrt2$.
DPatrick 2018-10-23 20:17:04
This might be more convenient as $XB = 5(1 + \sqrt2$).
motorfinn 2018-10-23 20:17:08
Now we use pythagorean theorem
harsha12345 2018-10-23 20:17:08
now pythagorean theorem
DPatrick 2018-10-23 20:17:14
Right. $AB$ is the hypotenuse of a right triangle with legs $5$ and $5(1+\sqrt2)$.
DPatrick 2018-10-23 20:17:29
Therefore, $AB = 5\sqrt{1^2 + (1+\sqrt2)^2}$.
DPatrick 2018-10-23 20:17:41
This simplifies to $AB = 5\sqrt{1 + (1 + 2\sqrt2 + 2)} = 5\sqrt{4 + 2\sqrt2}$.
DPatrick 2018-10-23 20:17:45
Yikes. What integer is this closest to?
WLongtin 2018-10-23 20:18:03
AB^2 is very close to 169
DPatrick 2018-10-23 20:18:18
Indeed, it's hard to tell straight away, but it's easier to work with if we square it.
DPatrick 2018-10-23 20:18:23
$AB^2 = 25(4 + 2\sqrt2) = 100 + 50\sqrt2$.
DPatrick 2018-10-23 20:18:37
Now we can use the fact that $\sqrt2 \approx 1.4$. (Hopefully that approximation is good enough.) This gives $AB^2 \approx 100 + 50(1.4) = 170$.
bibilutza 2018-10-23 20:18:51
13
DottedCaculator 2018-10-23 20:18:51
13
JotatD 2018-10-23 20:18:51
13 then?
qwertykeyboard 2018-10-23 20:18:51
so AB is close to 13
DPatrick 2018-10-23 20:18:58
That is just about $13^2 = 169$, so $AB \approx \boxed{13}$ looks like the answer.
DPatrick 2018-10-23 20:19:09
If we wanted to be extra-careful, we could show that $(12.5)^2 < AB^2 < (13.5)^2$. But I'll skip that for now.
mikebreen 2018-10-23 20:19:15
There's a connection with the Fibonacci sequence.
DPatrick 2018-10-23 20:19:36
Interesting...I didn't know that!
mikebreen 2018-10-23 20:19:57
If the side length was 8, AB is close to 21, ... We couldn't figure out why, though.
DPatrick 2018-10-23 20:20:08
DPatrick 2018-10-23 20:20:32
On to #8:
DPatrick 2018-10-23 20:20:37
8. The real polynomial $p(x) = x^3 - x^2 + bx + c$ has $2+i$ as one of its roots. What is the sum of the $x$- and $y$-intercepts of the graph of $y = p(x)$? (no $b$ or $c$ in your answer)
DPatrick 2018-10-23 20:21:00
In case you don't know, $i$ is the imaginary number with the property that $i^2 = -1$. (If you haven't worked much with imaginary numbers before, the solution to this problem may be hard to follow.)
DPatrick 2018-10-23 20:21:23
What do we know about complex (non-real) solutions to real polynomials?
skonar 2018-10-23 20:21:34
2-i is also a root
motorfinn 2018-10-23 20:21:34
If 2+i is a root, 2-i is a root
kdep 2018-10-23 20:21:34
2-i is also a root
novus677 2018-10-23 20:21:34
$2-i$ is also a root
WLongtin 2018-10-23 20:21:34
so $2-i$ is a root as well
champion999 2018-10-23 20:21:34
they occur in conjugate pairs
bibilutza 2018-10-23 20:21:34
you must have the conjugate $2-1$
Vexaria 2018-10-23 20:21:39
2-i is also a root
crazi4math001 2018-10-23 20:21:39
The other root is the conjugate, or $(2-i)$.
DPatrick 2018-10-23 20:21:44
They come in conjugate pairs! That is, if $2+i$ is a root, then $2-i$ must also be a root.
DPatrick 2018-10-23 20:22:04
The polynomial is a cubic. We know $2 \pm i$ are two of the roots. Can we determine the third root?
champion999 2018-10-23 20:22:26
vieta gives us the third root
crazi4math001 2018-10-23 20:22:26
Vieta's?
KSS 2018-10-23 20:22:28
Can we use vieta for it
DPatrick 2018-10-23 20:22:34
Yes -- can you elaborate?
DPatrick 2018-10-23 20:22:52
What Vieta formula specifically is useful here?
novus677 2018-10-23 20:23:17
the sum of the roots is 1
Puddles_Penguin 2018-10-23 20:23:17
Sum is 1
DPatrick 2018-10-23 20:23:29
Right!
DPatrick 2018-10-23 20:24:00
One of Vieta's formulas tells us that the sum of the roots of monic polynomial is $-1$ times the coefficient of the $x^{n-1}$ term.
DPatrick 2018-10-23 20:24:21
"monic" means the polynomial starts with an $x^n$ with coefficient $1$.
DPatrick 2018-10-23 20:24:31
So in this example, since the coefficient of $x^2$ is $-1$, we know that the sum of the roots is $1$.
asdf334 2018-10-23 20:24:41
3rd root is -3
skonar 2018-10-23 20:24:41
$2+i+2-i=4$ so other root is $-3$
motorfinn 2018-10-23 20:24:41
So the third root is -3
JotatD 2018-10-23 20:24:41
-3 is the third root
DPatrick 2018-10-23 20:24:56
Thus, if $2 \pm i$ are two of the roots, the third root must be $-3$ so that $(2+i) + (2-i) + (-3) = 1$.
Puddles_Penguin 2018-10-23 20:25:05
So -3 is x-intercept
DPatrick 2018-10-23 20:25:15
Right, now we know the $x$-intercept! The $x$-intercept is where the graph crosses the $x$-axis, so it's where $y = 0$.
DPatrick 2018-10-23 20:25:26
But the only real root is $x=-3$. So $(-3,0)$ is the $x$-intercept.
motorfinn 2018-10-23 20:25:36
We want the sum of the values
motorfinn 2018-10-23 20:25:36
For both x, and y intercepts
DPatrick 2018-10-23 20:25:43
Right, we still need to find the $y$-intercept.
DPatrick 2018-10-23 20:25:49
How do we do that?
Vexaria 2018-10-23 20:26:10
use prod of roots, which equals -c
skonar 2018-10-23 20:26:10
we need c bc p(0)=c
Puddles_Penguin 2018-10-23 20:26:15
Maybe you can use vietas to find c
WLongtin 2018-10-23 20:26:15
we need $c$
DPatrick 2018-10-23 20:26:32
If we plug in $x=0$, we get $y = p(0) = c$. So $(0,c)$ is the $y$-intercept.
DPatrick 2018-10-23 20:26:48
And we can find $c$ by using Vieta's formula for the product of the roots!
exal 2018-10-23 20:26:53
-c = product of roots
DPatrick 2018-10-23 20:27:01
Right. $c$ is the negative of the product of the roots! (It's negative because the polynomial has odd degree.)
DPatrick 2018-10-23 20:27:10
That is, $c = -(2+i)(2-i)(-3)$.
skonar 2018-10-23 20:27:23
c=15
JotatD 2018-10-23 20:27:23
15!
DPatrick 2018-10-23 20:27:28
And $(2+i)(2-i) = 4 - i^2 = 4 - (-1) = 5$.
DPatrick 2018-10-23 20:27:32
So $c = -(5)(-3) = 15$. Therefore, $(0,15)$ is the $y$-intercept.
DottedCaculator 2018-10-23 20:27:45
buzhidao 2018-10-23 20:27:45
So our final answer is 12.
mathChamp06 2018-10-23 20:27:47
DPatrick 2018-10-23 20:27:50
And the final answer is thus $(-3) + 15 = \boxed{12}$.
DPatrick 2018-10-23 20:28:10
If you haven't seen Vieta's Formulas before, they are well worth learning. They come up in a lot of polynomial problems.
DPatrick 2018-10-23 20:28:27
But you have to be really really careful with the signs!
DPatrick 2018-10-23 20:28:55
On to #9, which was the hardest of the regular problems. (#10 was not a "regular" problem as we'll soon see.)
DPatrick 2018-10-23 20:29:00
9. You roll two fair six-sided dice and your opponent rolls one die. What is the probability that the maximum of the numbers shown on the top faces of your two dice is strictly higher that the number shown on the top face of your opponent's die?
DPatrick 2018-10-23 20:29:22
Anybody recognize what board game this scenario is from?
PCampbell 2018-10-23 20:29:37
Risk
nawakre 2018-10-23 20:29:37
risk?
DPatrick 2018-10-23 20:29:41
If you've ever played the board game Risk, you may recognize this as what happens in the game when 2 armies attack 1 army.
DPatrick 2018-10-23 20:29:59
Let's call a roll where the maximum of my two dice is greater than my opponent's die a winner, and all other rolls losers.
DPatrick 2018-10-23 20:30:12
We want the probability of a winner.
DPatrick 2018-10-23 20:30:22
First, how many rolls in total are there?
Vexaria 2018-10-23 20:30:41
6^3 = 216
happyyouni 2018-10-23 20:30:41
216
DPatrick 2018-10-23 20:30:45
Each of the three dice has $6$ possible outcomes, so there are $6^3 = 216$ possible rolls.
DPatrick 2018-10-23 20:30:52
Is it easier to count winners or losers?
BestAOPS 2018-10-23 20:31:04
losers?
crazi4math001 2018-10-23 20:31:04
Losers
DPatrick 2018-10-23 20:31:11
To count winners, we have to count rolls where my first die is greater than my opponent's die OR my second die is greater than my opponent's die.
DPatrick 2018-10-23 20:31:14
To count losers, we have to count rolls where my first die is less than or equal to my opponent's die AND my second die is less than or equal to my opponent's die.
DPatrick 2018-10-23 20:31:27
Usually, counting "AND" conditions is easier. We can often count "OR" using casework, but if they cases overlap (and they do in this problem) it can get a little tricky.
DPatrick 2018-10-23 20:31:37
So let's count losers. How can we count them?
sbudaraj 2018-10-23 20:31:45
y not just split up into 6 cases and then it becomes easy
motorfinn 2018-10-23 20:32:01
Casework
DPatrick 2018-10-23 20:32:02
Indeed, we can do casework based on what my opponent rolls.
DPatrick 2018-10-23 20:32:07
For example, if my opponent rolls a $1$, how many of my rolls are losers?
sbudaraj 2018-10-23 20:32:27
1
Owen1204 2018-10-23 20:32:27
1
bibilutza 2018-10-23 20:32:27
1
DPatrick 2018-10-23 20:32:30
I lose only if I roll a $1$ on both my dice. So only $1$ roll is a loser.
DPatrick 2018-10-23 20:32:35
How about if my opponent rolls a $2$?
sbudaraj 2018-10-23 20:32:59
4
mathChamp06 2018-10-23 20:32:59
4
popcorn1 2018-10-23 20:32:59
4
cai40 2018-10-23 20:32:59
4
skonar 2018-10-23 20:32:59
4 rolls are losers
piplupdragon 2018-10-23 20:32:59
4
DPatrick 2018-10-23 20:33:04
I lose only if I roll a $1$ or a $2$ on both my dice. So $2^2 = 4$ rolls are losers.
mathChamp06 2018-10-23 20:33:17
doesn't it just become the sum of the first 6 perfect squares?
DPatrick 2018-10-23 20:33:20
Aha, good!
popcorn1 2018-10-23 20:33:23
1,4,9,16,...
DPatrick 2018-10-23 20:33:27
If my opponent rolls $n$, then I lose if I roll $n$ or less on both dice. This happens in $n^2$ ways.
DPatrick 2018-10-23 20:33:33
So the number of losers is $1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2$.
DPatrick 2018-10-23 20:33:49
(And note that if my opponent rolls a $6$, I'm doomed. All $36$ of my rolls are losers.)
DPatrick 2018-10-23 20:33:58
This is $1+4+9+16+25+36 = 91$ rolls that are losers.
Puddles_Penguin 2018-10-23 20:34:14
Is it 125/216?
skonar 2018-10-23 20:34:17
125/216
DPatrick 2018-10-23 20:34:24
Therefore, $216 - 91 = 125$ rolls are winners, and the probability of winning is $\boxed{\dfrac{125}{216}}$.
popcorn1 2018-10-23 20:34:34
But thats 5^3/6^3
buzhidao 2018-10-23 20:34:34
125 is a nice number
motorfinn 2018-10-23 20:34:34
or (5/6)^3
DPatrick 2018-10-23 20:34:49
Indeed, that's the first thing I noticed too. It's an odd coincidence that the answer is $\dfrac{5^3}{6^3}$. One might wonder if, given a $k$-sided die, the answer is always $\dfrac{(k-1)^3}{k^3}$.
DPatrick 2018-10-23 20:34:59
But it's not. It's just a coincidence.
DPatrick 2018-10-23 20:35:09
(We checked.)
DPatrick 2018-10-23 20:35:30
And finally, #10, which is a little bit different.
DPatrick 2018-10-23 20:35:35
10. A partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers. For example, the number $3$ has three partitions: $3$ (the number itself is a partition with one addend), $2+1$, and $1+1+1$ (the order of the addends doesn't matter). How many partitions does $101$ have?
DPatrick 2018-10-23 20:35:46
This is the tiebreaker question.
DPatrick 2018-10-23 20:35:53
No one is expected to get the exact answer.
DPatrick 2018-10-23 20:36:07
But this will break ties if two or more students tie on 1-9 in any region (more about that later).
WLongtin 2018-10-23 20:36:20
ramanujan!
Puddles_Penguin 2018-10-23 20:36:20
Ramanujan know this
DPatrick 2018-10-23 20:36:42
Indeed, Ramanujan and his collaborator Hardy studied this question quite a bit and came up with a formula to approximate this.
DPatrick 2018-10-23 20:36:51
But first, any guesses? And any ideas how we might go about estimating this number?
Hermain 2018-10-23 20:37:06
stars and bars?
math-legend 2018-10-23 20:37:06
I got some crazy answer like $$2^101$$
Owen1204 2018-10-23 20:37:06
wouldn't it just be 2^101?
skonar 2018-10-23 20:37:06
sticks and stones
DPatrick 2018-10-23 20:37:11
Well...that's a related problem.
DPatrick 2018-10-23 20:37:25
An easier problem is the number of ordered partitions. That is, in our example above $2+1$ and $1+2$ would count as different partitions of $3$ if we were counting ordered partitions.
DPatrick 2018-10-23 20:37:44
This is a lot easier to count.
DPatrick 2018-10-23 20:37:49
For example, suppose we want an ordered partition of $6$.
DPatrick 2018-10-23 20:37:55
We draw $6$ dots in a row:

;
DPatrick 2018-10-23 20:37:59
Then we put walls between the dots to break them up into groups.
DPatrick 2018-10-23 20:38:07
For example:

;

This corresponds to the ordered partition $1+3+2$.
DPatrick 2018-10-23 20:38:22
So, since there are 5 spaces between dots where we could put a wall, there are $2^5 = 32$ ordered partitions of $6$.
asdf334 2018-10-23 20:38:34
1+3+2 is the same as 1+2+3
asdf334 2018-10-23 20:38:40
overcounting
DPatrick 2018-10-23 20:38:45
Right: this is a substantial overcount. There are only eleven unordered partitions of $6$:

$6$

$5+1$

$4+2$

$4+1+1$

$3+3$

$3+2+1$

$3+1+1+1$

$2+2+2$

$2+2+1+1$

$2+1+1+1+1$

$1+1+1+1+1+1$
DPatrick 2018-10-23 20:38:52
And we can see the overcount more clearly if we keep track of how many ways each unordered partition can be ordered
DPatrick 2018-10-23 20:38:56
$$\begin{array}{l|l} \text{Unordered} & \text{# of orderings} \\ \hline 6 & 1 \\ 5+1 & 2 \\ 4+2 & 2 \\ 4+1+1 & 3 \\ 3+3 & 1 \\ 3+2+1 & 6 \\ 3+1+1+1 & 4 \\ 2+2+2 & 1 \\ 2+2+1+1 & 6 \\ 2+1+1+1+1 & 5 \\ 1+1+1+1+1+1 & 1 \end{array}$$
DPatrick 2018-10-23 20:39:04
The numbers in the right column add up to $32$, the number of ordered partitions.
motorfinn 2018-10-23 20:39:14
Similarly, we have 100 spaces for 101 numbers
DPatrick 2018-10-23 20:39:20
Indeed, if we line up $101$ dots in a row:
DPatrick 2018-10-23 20:39:24
DPatrick 2018-10-23 20:39:35
We can put walls into any of the $100$ slots between dots and get a partition:
DPatrick 2018-10-23 20:39:47
DPatrick 2018-10-23 20:39:50
It's a little hard to tell, but this is the ordered partition $4 + 8 + 46 + 25 + 1 + 17$.
WLongtin 2018-10-23 20:40:02
but the over counting will be more severe
motorfinn 2018-10-23 20:40:02
But that's overcounting
DPatrick 2018-10-23 20:40:06
Since there are $100$ slots, there are $2^{100}$ ordered partitions.
DPatrick 2018-10-23 20:40:17
But this gives lots of different unordered partitions. For example, the partition above can be ordered in $6! = 720$ ways. That is, there are $720$ different ordered partitions that all correspond to the same unordered partition.
DPatrick 2018-10-23 20:40:24
And I don't know of a good way to account for all of the overcounting.
DPatrick 2018-10-23 20:40:36
At least we have an upper bound. And $2^{100} = (2^{10})^{10} \approx (10^3)^{10} = 10^{30}$.
DPatrick 2018-10-23 20:40:45
But the overcounting is massive. For example, if I had a partition with $12$ different parts, then (assuming the parts are all different) it is overcounted by a factor of $12!$, which is about $500$ million.
DPatrick 2018-10-23 20:41:09
The best I could do was to try to figure out the "average" partition.
DPatrick 2018-10-23 20:41:33
I figured, using expected value, that the average ordered partition of $101$ has 26 1's, 12 2's, 6 3's, 3 4's, 2 5's, one unique higher
DPatrick 2018-10-23 20:41:45
So the overcounting is by about $\dfrac{50!}{26!12!6!3!2!} \approx 10^{25}$.
DPatrick 2018-10-23 20:42:07
So my guess would have been $10^{30} / 10^{25} = 10^5 = 100{,}000$.
DPatrick 2018-10-23 20:42:21
Turns out this is bogus and is way way too low.
DPatrick 2018-10-23 20:42:33
Let's see what Ramanujan and Hardy did -- they're way smarter than me.
DPatrick 2018-10-23 20:42:52
The Hardy-Ramanujan (1918) asymptotic formula is $$p(n) \sim \dfrac{1}{4n\sqrt3}\exp(c\sqrt{n}),$$ where $\exp(x) = e^x$ is the natural exponential (where $e = 2.71828\ldots$) and $c = \pi\sqrt{\frac23}$.
DPatrick 2018-10-23 20:43:22
As a reminder, if you'd like to learn more about Srinivasa Ramanujan and his mathematical achievements (much of which were in collaboration with G. H. Hardy), please attend our "Spirit of Ramanujan" Math Jam next Tuesday at this same time!
spartacle 2018-10-23 20:43:27
not sure this is much better
DPatrick 2018-10-23 20:43:32
True, but it's workable at least.
DPatrick 2018-10-23 20:43:42
Plugging in $n=101$ gives

$$p(101) \approx \frac{1}{404\sqrt3}\exp\left(\pi\sqrt\frac{202}{3}\right).$$
DPatrick 2018-10-23 20:44:04
To approximate without a computer, I would note that $404\sqrt3 \approx 700$ and $\pi\sqrt\frac{202}{3} \approx 26$, so this is about $\dfrac{e^{26}}{700}$.
DPatrick 2018-10-23 20:44:17
And to approximate the exponential, note $2 < e < 3$ but is closer to $3$.
DPatrick 2018-10-23 20:44:31
And then $2^{26} \approx (10^{3})^{2.6} \approx 10^8$ and $3^{26} \approx (3^2)^{13} \approx 10^{13}$, so maybe $e^{26} \approx 10^{11}$ is a decent approximation.
DPatrick 2018-10-23 20:44:44
Dividing by $700$ gives $1.4 \cdot 10^8 = 140{,}000{,}000$ as my approximation.
DPatrick 2018-10-23 20:44:53
That's not terrible. The actual answer is $\boxed{214{,}481{,}126}$.
WLongtin 2018-10-23 20:45:09
maybe some kind of recursive formula giving partitions of $n$ in terms of partitions of $n-1$
DPatrick 2018-10-23 20:45:24
That's another approach. A simple recurrence is $p(n) = p(n-1) + \text{partitions of$n$that don't use$1$}$.
DPatrick 2018-10-23 20:45:31
But that last part is still tricky.
motorfinn 2018-10-23 20:45:40
It would take a long time to derive such a formula
DPatrick 2018-10-23 20:45:53
Indeed. The mathematics behind the formula is not simple, to say the least.
WLongtin 2018-10-23 20:46:15
It was featured in the Ramanujan movie
skonar 2018-10-23 20:46:31
The Man Who Knew Infinity
DPatrick 2018-10-23 20:46:42
Anyway, that's it for the Round 2 problems!
mikebreen 2018-10-23 20:46:46
No one got #10 correct. We were only looking for fairly good approximations. Within a factor of 10 is very good.
DPatrick 2018-10-23 20:46:51
After the Round 2 scoring is complete, 12 students will be invited to compete in the Championship Finals, live in Baltimore at the 2019 Joint Mathematics Meetings on January 19. Travel costs to and from Baltimore will be covered by the AMS.
DPatrick 2018-10-23 20:47:02
Here's how the 12 finalists will be determined: 10 of the 12 will be the top scorer from Round 2 in each of the following regions:
DPatrick 2018-10-23 20:47:05
DPatrick 2018-10-23 20:47:18
The other two contestants will be the top scorer in the United Kingdom and the top scorer in the Baltimore metro area (or, I suppose, the second-highest scorer, if the highest scorer in Region 2 happens to be from Baltimore).
DPatrick 2018-10-23 20:47:31
The Championship Finals are held live in front of an audience at the Joint Mathematics Meetings, and are also live streamed on the web. (You can watch the archives of past years' finals on the WWTBAM website.) Contestants will compete directly against each other in semi-final rounds, with the semi-final winners advancing to a Jeopardy!-style buzz-in final round to determine a champion.
DPatrick 2018-10-23 20:47:47
And I'll be there too!
DPatrick 2018-10-23 20:47:55
All of the finalists will receive prizes (in addition to the free trip to Baltimore!), and the champion will win \$10,000.
DPatrick 2018-10-23 20:48:30
mikebreen 2018-10-23 20:48:41
Emails to qualifiers probably going out tomorrow.
DPatrick 2018-10-23 20:49:06
Thanks for coming tonight. Hopefully I'll see many of you next week at our Spirit of Ramanujan Math Jam too!
asdf334 2018-10-23 20:49:15
how can i signup next year for the competition?
DPatrick 2018-10-23 20:49:32
I don't think you can yet, but you can probably go to the AMS website I just linked to above to sign up to get on the mailing list.
mikebreen 2018-10-23 20:49:39
mikebreen 2018-10-23 20:49:49
paoffice@ams.org
motorfinn 2018-10-23 20:49:58
What are the qualifications for taking this competition?
DPatrick 2018-10-23 20:50:15
You just need to be a student (high school or lower) in the US, Canada, or the UK.
DPatrick 2018-10-23 20:51:02
Details are on the AMS website or your teacher can email the address that Mike just posted.
DPatrick 2018-10-23 20:51:30
The AMS website will also have the livestream of the Finals in January. We'll announce it on AoPS too.
mathChamp06 2018-10-23 20:52:38
is this the end of the class then?
DPatrick 2018-10-23 20:53:02
I think so -- thanks to everyone for coming and to our special guests Mike, Bill, and Ken from the AMS for joining us. (Ken had to leave early.)
DPatrick 2018-10-23 20:53:13
Ken will also be with us next week for Spirit of Ramanujan.
mikebreen 2018-10-23 20:53:21
Thanks, everyone. Great problem solving.
TPiR 2018-10-23 20:53:26
Thanks everyone. Great job all the way around.
DPatrick 2018-10-23 20:53:37
Have a good night!