| Transcript
for the Math
Jam "USAMTS Round 3 Math Jam"
on Jan 14. |
| Math Jam hosted by DPatrick
(Dave Patrick ). |
DPatrick19:30:18
Let's get started with Problem 1.
DPatrick19:30:23
DPatrick19:30:53
I tried to draw this, but quickly gave up.
VDLmath19:31:10
This is a geometric sequence
McDutchy19:31:10
Construct an infinite geometric series
12345678919:31:10
There are 6 exposed faces in the first stage, then 5 exposed faces in each successive stage.
DPatrick19:31:33
Right -- one way to approach this is to count the cubes, and in doing so construct a geometric sequence for the volume.
stardust19:31:38
first cube has a volume of 1
shopaholic34319:31:38
There is a geometric sequence to this. So the first cube has a volume of 1...
DPatrick19:31:46
There is 1 big cube of side length 1.
McDutchy19:32:14
Second group of cubes is 6 cubes, vol 1/3^3 each
andersonw19:32:14
Six cubes of side length 1/3
12345678919:32:14
the cubes in the next stage have volume 6(1/3)^3
DPatrick19:32:22
There are 6 cubes of side length 1/3.
lingomaniac8819:32:27
next is 1/27, then 1/729, and so on
naveen7619:32:27
The next set of cubes added each has a volume of 1/27
DPatrick19:32:45
So we have 6 cubes with volume (1/3)^3.
VDLmath19:32:52
then 30 cubes of side length 1/9
McDutchy19:32:52
next stage is 5 times previous count of cubes
DPatrick19:33:07
Right...each smaller cube has 5 exposed faces, so we have 5 times as many cubes of the next smaller size.
DPatrick19:33:16
So there are 5*6 cubes of side length 1/9.
zatomics19:33:32
6*5^(n-1) cubes of side (1/3^n) in general
DPatrick19:33:50
Exactly...we get 5 times as many cubes of the next smaller size each time we iterate the cube-gluing procedure.
DPatrick19:34:01
For instance, at the next step, there are 5*5*6 cubes of side length 1/27.
12345678919:34:09
Set up a summation and add 1 to the result
DPatrick19:34:15
Right, we can now sum up all the volumes.
DPatrick19:34:19
worthawholebean19:34:40
So we're multiplying the total volume by 5/27 every time
naveen7619:34:40
So the initial term of the sequence is 6/27 and the rate is 5/27
worthawholebean19:34:40
Geometric series!
DPatrick19:34:56
Indeed, we can rearrange the sum a little bit, and it's more obviously a geometric series:
DPatrick19:34:59
McDutchy19:35:15
now sum,
naveen7619:35:21
We apply the formula a/(1-r) where a is the first term and r is the rate
DPatrick19:35:29
Indeed, the infinite sum is (5/27)/(1-5/27) = 5/22.
DPatrick19:35:47
So the entire volume is 1 + (6/5)(5/22) = 28/22 = 14/11.
DPatrick19:36:17
I actually did the problem myself slightly differently.
worthawholebean19:36:29
Did we need to prove that the cubes didn't overlap?
DPatrick19:36:56
No. It's true that a fully rigorous solution would have to prove this, but we're not going to require this.
DPatrick19:37:19
Here's how I solved it: I looked at the problem "fractically".
DPatrick19:37:23
ooops..
DPatrick19:37:28
I meant to say "fractally"
DPatrick19:37:36
There's a cube with side length 1 in the middle, and then attached are 6 infinite cubey things.
DPatrick19:37:58
Each cubey thing has "base" side length 1/3, and has 5 smaller infinite cubey things attached to it.
DPatrick19:38:07
Each smaller cubey thing has side length 1/3 that of the larger one it's attached to, so it has volume (1/3)^3 = 1/27 that of the larger one.
DPatrick19:38:17
Let the volume of a cubey thing by C.
DPatrick19:38:28
DPatrick19:38:49
So 27C = 1 + 5C, hence C = 1/22.
DPatrick19:38:56
There are 6 of them attached to the big cube of volume 1, so the volume is 1 + 6C = 28/22 = 14/11.
DPatrick19:39:16
Of course, this is exactly the same thing as we did before.
DPatrick19:39:31
Let's move on to Problem 2:
DPatrick19:39:37
DPatrick19:39:52
(I'll post the grid, but it's too wide for the window...)
DPatrick19:39:58
shopaholic34319:40:24
The smallest grid(meaning smallest numbers) has a center of 4...because you need to cover each of the four 2x2 grids at least once.
Xantos C. Guin19:40:24
The order which Gene chooses the squares doesn't matter
lingomaniac8819:40:24
no matter which 2x2 block is chosen, the number in the middle is always incremented
12345678919:40:24
The amount of times that Gene picks a 2 x 2 square is equal to the number in the center square, because it is part of all four 2 x 2 grids
chenhsi19:40:24
We can see that he has at least 4 steps and at most 12 steps.
stardust19:40:24
at least 4 moves, no more than 12
krsattack19:40:24
depends only on corner squares
.cpp19:40:24
We only need to consider the corners and center.
DPatrick19:40:35
Right...these are all the key observations.
DPatrick19:40:47
The center square is always the largest, and is the total of the number of steps.
DPatrick19:40:54
The corner squares are just the number of times that that particular 2x2 square is chosen.
12345678919:41:01
denoting A to be the amount of times that we choose the top-left 2 x 2 grid, B to be the amount of times we choose the top-right, C, D, ...., we can write expressions for each box in the 3 x 3 grid
DPatrick19:41:08
Indeed we can!
DPatrick19:41:13
DPatrick19:41:29
We can see that a grid is uniquely determined by a,b,c,d.
Mgccl19:41:44
so we get... a+b+c+d <=12 and a,b,c,d>=1
DPatrick19:41:51
Right. Since we need every number to be between 1 and 12 (inclusive), we need that a,b,c,d are all positive, and a+b+c+d <= 12.
DPatrick19:42:06
How do we find the number of solutions to this equation?
DPatrick19:42:15
(or, I should say, inequality)
lingomaniac8819:42:31
balls and urns
samath19:42:31
balls and urns
Xantos C. Guin19:42:31
balls and urns argument
worthawholebean19:42:36
Balls and urns
DPatrick19:42:56
OK...we'll probably want a "balls and urns" argument (which I'll explain in a minute if you're not familiar with it)...
DPatrick19:43:09
...but I'd rather have an equation instead of an inequality. How can we get one?
redcomet4619:43:34
let there be some dummy variable k such that a+b+c+d+k = 13... now use the placing dividers between 1's argument.
perfect62819:43:34
Add in nonnegative e, so that a+b+c+d+E=12
worthawholebean19:43:34
a+b+c+d+k=12
samath19:43:38
add e -- (12-a-b-c-d)
DPatrick19:44:01
We could do casework, solving a+b+c+d = 4,5,6,...,up to 12, but it's a lot simpler if we add a fifth positive integer e.
DPatrick19:44:11
Then we simply need to find the number of solutions (in positive integers) to a+b+c+d+e = 13.
DPatrick19:44:28
Note that if e is *positive*, then we're summing to 13, not to 12.
DPatrick19:44:49
So we need the number of ways that five ordered, positive integers can sum to 13.
DPatrick19:45:14
This is sometimes called "balls and urns", since it counts the number of ways that we can place 13 identical balls into 5 different boxes, in which we're not allowed to leave any box empty.
McDutchy19:45:34
(12 c 4)
krsattack19:45:34
13 1's to place... 12 dividers, 4 to choose
DPatrick19:45:58
Right. This can be solved via a clever gadget sometimes called "stars and bars" or a "divider" approach.
DPatrick19:46:04
Put 13 stars in a row: * * * * * * * * * * * * *
DPatrick19:46:14
Then we need to insert 4 bars into the 12 gaps between the stars.
For example:
* * | * * * | * | * * * | * * * *
corresponds to a=2, b=3, c=1, d=3, and e=4.
DPatrick19:46:40
Every different choice of 4 slots to put the bars in will give us a different solution.
DPatrick19:47:00
So there are C(12,4) = 495 solutions, and thus 495 possible grids.
zatomics19:47:25
what about rotational symmetry?
DPatrick19:47:37
We don't consider it ... the problem didn't say to consider it.
lotsofmath19:47:43
what's the C thing?
DPatrick19:47:46
Binomial coefficient:
DPatrick19:48:00
andersonw19:48:21
Will we still get full credit for the problem if we considered all the different possible values of a+b+c+d one at a time?
DPatrick19:48:29
Certainly. It will (of course) lead to the same answer.
DPatrick19:48:44
The underlying mathematics behind why it's the same answer is sometimes called the "Hockey Stick Identity".
McDutchy19:48:59
What's that?
DPatrick19:49:05
I'll let you look it up. :)
tenniskidperson319:49:09
it's on aopswiki
DPatrick19:49:15
Let's move on to Problem 3:
DPatrick19:49:21
lingomaniac8819:49:55
Let g(x) = f(x) - 2007
krsattack19:49:55
Consider g(x) = f(x) - 2007
tenniskidperson319:49:55
let g(x)=f(x)-2007
DPatrick19:50:00
Sure.
DPatrick19:50:13
It's usually easier to work with roots of a polynomial, so let g(x) = f(x) - 2007. Note that g(x) has integer coefficients too.
zatomics19:50:26
consider instead g(x) = f(x) - 2007, because then we know 200 and 7 are roots of g, and thus (x-200)(x-7) | g(x)
DPatrick19:50:37
Right. Thus g(x) = (x-7)(x-200)h(x) for some polynomial h with integer coefficients.
DPatrick19:51:01
Now what?
McDutchy19:51:04
is it necessary to prove h has integer coefficients?
DPatrick19:51:21
You need to at least state it. I don't know if we'll require a formal proof.
DPatrick19:51:50
The "proof" is that when you divide by x-7 (say, using synthetic division), there's no way to produce non-integer coefficients.
krsattack19:52:20
f(0) = 2007 + 1400h(x)
worthawholebean19:52:20
Plug in f(0)
Duelist19:52:27
f(0)=-1400h(x)+2007
DPatrick19:52:34
Yeah, careful with the signs!
DPatrick19:52:45
I'd take it step-by-step to be careful.
DPatrick19:52:56
We know that g(0) = 1400*h(0).
DPatrick19:53:04
But the constant term of h is an integer, so g(0) = 1400c for some integer c.
worthawholebean19:53:31
Plug it into the inequality and solve for c, which is an integer.
zatomics19:53:38
c has to = -1
DPatrick19:53:45
Right. The only way that this can be between 0 and 2007 is if c=-1.
tenniskidperson319:54:03
so f(0)=607
lingomaniac8819:54:05
therefore f(0) = 1400*(-1)+2007 = 607
DPatrick19:54:12
And thus, f(0) = -1400+2007 = 607.
DPatrick19:54:25
So the answer is 607.
DPatrick19:54:43
Note that, in this problem, it is definitely incorrect to assume that f(x) must be quadratic or that h(x) must be a constant polynomial.
DPatrick19:54:58
The problem says that you have to prove that f(0) does not depend on the choice of polynomial.
Shadow Hunter19:55:26
you can show that f(x) must be a unique quadratic
DPatrick19:56:16
That's true: you can show that if f is quadratic, then it must be -(x-7)(x-200)+2007.
Laplace's_Demon19:56:23
It can actually have any degree
DPatrick19:56:51
Indeed, since h(x) can be anything with constant term -1, there are infinitely many possible f(x)'s.
Duelist19:57:07
Must one justify that g(x) = (x-200)(x-7)(h(x)) by referring to a theorem, or is it self-explanatory?
DPatrick19:57:31
It's somewhat inbetween. You don't need to quote a theorem by name, but you need to at least mention that h(x) must have integer coefficients.
DPatrick19:57:44
Let's move on to Problem 4.
DPatrick19:57:50
worthawholebean19:58:15
Define the set precisely.
zatomics19:58:15
get rid of 2007, first thing
andersonw19:58:15
We can take factor out a 2007
krsattack19:58:20
(2007, 101) = 1, so we can divide by 2007
redcomet4619:58:23
factor 2007 out then write as sum of powers of 10000
DPatrick19:58:26
Right.
DPatrick19:58:32
DPatrick19:58:42
And 101 is relatively prime to 2007, so 101 divides the number if and only if 101 divides (1+10^4+10^8+...+10^(4k)).
CatalystOfNostalgia19:59:00
10^4k == 1 mod 101
VDLmath19:59:05
10^4 equals (9999+1)
VDLmath19:59:05
and 9999 is divislbe by 101
McDutchy19:59:05
10^4=1 mod 101
DPatrick19:59:11
Yes. There are a number of ways to proceed from here.
DPatrick19:59:26
The easiest is probably to observe that 10^4 = (101-1)^2 = 1 (mod 101).
DPatrick19:59:36
So 1, 10^4, 10^8, etc. are all 1 (mod 101).
DPatrick19:59:44
And how do we finish from here?
lingomaniac8820:00:07
so if we have 101n of them for some positive integer n, the number is a multiple of 101
krsattack20:00:07
every 101 terms, the sum is divisible by 101
tenniskidperson320:00:07
1+1+1... mod 101
DPatrick20:00:17
Right. Therefore the sum of the first 101 terms is a multiple of 101, and thus so is the sum of the first 202 terms, the first 303 terms, and so on.
DPatrick20:00:34
So the 101st, 202nd, 303rd, etc. elements of the set are all divisible by 101.
DPatrick20:01:10
An interesting challenge is to generalize this problem as much as you can. That is, there's not much too special about the numbers "101" and "2007".
DPatrick20:01:17
How much more general can you make the problem statement?
DPatrick20:01:30
I'll let you think about that on your own.
DPatrick20:01:42
Let's finish up with Problem 5:
DPatrick20:01:47
worthawholebean20:02:35
For part a, use radii sum/distance of centers
andersonw20:02:35
We can prove that the sum of the radii of any two such circles is greater than or equal to the distances between their centers
McDutchy20:02:43
part a: 2 circles intersect at more than 1 point iff the distance between their centers < sum of radii
DPatrick20:03:00
Right. For part (a), two circles intersect at at most 1 point if and only if the distance between their centers is at least the sum of their radii.
DPatrick20:03:16
So suppose that p/q and p'/q' are the x-coordinates of the centers of two distinct circles.
CatalystOfNostalgia20:03:40
time for algebra
DPatrick20:03:44
Yes.
DPatrick20:03:49
DPatrick20:04:01
DPatrick20:04:19
CatalystOfNostalgia20:04:39
square both sides
andersonw20:04:39
expand and square
DPatrick20:04:44
We can square both sides so that this is equivalent to showing that:
DPatrick20:04:48
worthawholebean20:05:19
difference of squares if we subtract second term on LHS
DPatrick20:05:41
Yes, the algebra is much nicer if we first move all the terms with q^2,q'^2 in the denominator to the right side
DPatrick20:05:47
Xantos C. Guin20:06:07
Then multiply through by q^2q'^2
DPatrick20:06:38
I definitely do not want to take square roots here, because that term inside the square on the LHS might be positive or negative.
DPatrick20:06:53
Instead, I'll clear denominators and simplify:
DPatrick20:06:59
worthawholebean20:07:21
Both integer, so they must be >0
DPatrick20:07:33
The left side is a nonnegative integer, so it only fails to be at least 1 if it is 0.
krsattack20:07:38
true unless p/q = p'/q'
lingomaniac8820:07:42
which is false if and only if pq' = p'q
DPatrick20:07:58
Right. The left side is 0 if and only if pq' = p'q. But this would mean that p/q = p'/q', which cannot happen.
DPatrick20:08:02
...since we started with distinct circles.
DPatrick20:08:25
So any two circles intersect in at most 1 point.
DPatrick20:08:48
In fact, we have the equality condition too: two circles with centers are x-coordinates p/q and p'/q' are tangent if and only if |pq' - p'q| = 1.
DPatrick20:08:59
...but we don't need that, it's just an interesting observation.
DPatrick20:09:03
What about the circles centered at (0,1/2) and (1,1/2)?
Xantos C. Guin20:09:17
The circles at (0,1/2) and (1,1/2) are (p,q) = (0,1) and (1,1) respectively
napoleon633420:09:22
you can put them in p, q form
CatalystOfNostalgia20:09:24
well you just make p=0, q=1
lingomaniac8820:09:27
we can represent those as 0/1 and 1/1
DPatrick20:09:35
Right. The same argument holds where we let q=1. (p=0 in the first circle, p=1 in the second)
DPatrick20:09:47
So that takes care of part (a).
DPatrick20:09:57
On to part (b).
DPatrick20:10:02
How can we sum up the area?
Shadow Hunter20:10:14
carefully
DPatrick20:10:17
napoleon633420:10:23
Euler's Phi Function
andersonw20:10:23
count up the possible circles for each q?
lingomaniac8820:10:29
for every q, there are phi(q) circles
DPatrick20:10:31
Right.
DPatrick20:10:47
For each q, there are phi(q) of them, where phi(q) is the number of integers less than q that are relatively prime to q.
DPatrick20:10:59
(That's called the Euler Phi function.)
Xantos C. Guin20:11:05
The area of the circle (p,q) is pi/(4q^2)
DPatrick20:11:09
andersonw20:11:15
multiply the number of circles by their area
DPatrick20:11:23
Right, we can now sum it up.
DPatrick20:11:30
Therefore the total area over all the circles (including the two large circles, and factoring out pi/4), is:
DPatrick20:11:33
DPatrick20:12:07
Now there are several ways to proceed, including quoting some high-powered theorems.
DPatrick20:12:14
But I always like the lo-tech solutions.
DPatrick20:12:22
What's the formula for phi(q)?
krsattack20:12:50
n(1-1/p_1)(1-1/p_2)...
Duelist20:12:50
n(1-1/p1)(1-1/p2)...
DPatrick20:12:55
Right.
worthawholebean20:13:03
q(1-1/p_1)(1-1/p_2)... where p_n are the prime factors of q
123456789_220:13:03
with prime factors a, b, c, it's (1-1/a)(1-1/b)(1-1/c) times the number
Xantos C. Guin20:13:03
q(1-1/p1)(1-1/p2)...
DPatrick20:13:10
DPatrick20:13:37
(If you've not seen this before, it's a good exercise to try to figure out why it works.)
DPatrick20:13:43
Therefore, our area is:
DPatrick20:13:45
DPatrick20:13:57
(My q's became n's, sorry.)
DPatrick20:14:07
Of course, we can cancel a factor of n:
DPatrick20:14:11
DPatrick20:14:20
DPatrick20:14:37
How can we simplify that sum/product?
DPatrick20:15:05
One way is to try to "factor" all the terms that are going to have a particular (1-1/p) term.
DPatrick20:15:34
In particular, the values of n that are going to only have a single (1-1/p) are the terms where n = p^k for some positive integer k. So let's first focus on summing those.
DPatrick20:16:05
(So, for right now, I'm only worrying about the n's that are powers of a single prime p.)
DPatrick20:16:15
DPatrick20:16:41
Note that f(p) is just the terms of the sum where n=p^k for some positive integer k.
lingomaniac8820:16:47
infinite geometric series
DPatrick20:16:57
Indeed, we can algebraically simplify this:
DPatrick20:17:03
DPatrick20:17:37
So now we've got a nice expression for the terms of the sum where n is a power of p.
DPatrick20:17:46
But what about the rest of the n's? How do we get those terms?
DPatrick20:18:21
We multiply!
DPatrick20:18:29
DPatrick20:19:11
...because it's going to have a (1-1/2)(1-1/3) term out front, and then there will be a corresponding product 1/2^a*1/3^b coming from the infinite geometric series terms.
DPatrick20:19:42
We can get every possible n this way.
DPatrick20:19:49
DPatrick20:20:29
(By the way, if you're lost now, don't worry about it too much. This is a hard proof. Just try to follow as much as you can, and go back and re-read it more slowly after we're done.)
DPatrick20:20:43
DPatrick20:21:05
Now we do a little more algebra with those (1+f(p)) terms:
DPatrick20:21:09
DPatrick20:21:35
The rest of the proof is just cleaning up the algebra:
DPatrick20:21:42
VDLmath20:22:06
which is what we need
DPatrick20:22:12
Exactly.
DPatrick20:22:54
There are some alternate ways to do all the messy algebra and number theory. You might check the message board for some other ideas.
DPatrick20:23:24
By the way, the circles in this problem are called Ford Circles, and you can do a web search or look in Wikipedia to learn more about them.
DPatrick20:23:34
That's it for Round 3.
DPatrick20:23:40
We are currently processing the Round 3 submissions. We hope to have this completed this week. Your scores and feedback should be available in early February.
VDLmath20:23:49
when will round 4 problems be posted up?
DPatrick20:23:56
Round 4 problems should be posted later this month (probably the last week of January) on the USAMTS web site. The deadline for submitting your Round 4 solutions is March 11.
123456789_220:24:04
So we will receive our checkmarks sometime this week?
DPatrick20:24:18
Yes -- we're processing them as we speak, and they should hopefully all be in the system later this week.
chenhsi20:24:30
when do round 2 solutions appear
DPatrick20:24:38
I'm told this week. I don't know for sure.
Duelist20:24:41
When sending latex solutions, is it okay if you only sent the pdf file?
DPatrick20:24:44
Yes, that's fine.
Aquila20:24:58
How are you going to score problem 5?
DPatrick20:25:10
We have not decided on any grading rubrics for Round 3 yet.
DPatrick20:25:25
That's it for tonight -- thanks for coming and good luck on Round 4!
