Math Jams

DPatrick 2015-03-21 19:00:28
Welcome to the 2015 AIME I Math Jam!

DPatrick 2015-03-21 19:00:35
I'm Dave Patrick, and I'll be leading our discussion tonight.

DPatrick 2015-03-21 19:00:41
Before we get started I would like to take a moment to explain our virtual classroom to those who have not previously participated in a Math Jam or one of our online classes.

DPatrick 2015-03-21 19:00:51
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 instructors, who may choose to share your comments with the room.

DPatrick 2015-03-21 19:01:01
This helps keep the class organized and on track. This also means that only well-written comments will be dropped into the classroom, so please take time writing responses that are complete and easy to read.

DPatrick 2015-03-21 19:01:16
There are a lot of students here! As I said, only a relatively small fraction of the well-written comments will be passed to the entire group. Please do not take it personally if your responses 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 2015-03-21 19:01:31
Also, we won't always be going through the math quite as thoroughly as we do in our classes -- I can't teach all the necessary 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 always to try do so in our regular online 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 2015-03-21 19:01:59
We do have two teaching assistants with us tonight to help answer your questions: Luis (Duelist) and Alex (BOGTRO). (Or at least we're supposed to have 2 -- Alex must be running late.)

DPatrick 2015-03-21 19:02:14
They can answer questions by whispering to you or by opening a window with you to chat 1-on-1. However, due to the large size of the session tonight, they may not be able to get to you right away (or at all). Repeating your question over and over is more likely to annoy us than to get it answered faster, so please, just ask your question once and be patient, and please understand that we may not be able to answer all the questions tonight.

DPatrick 2015-03-21 19:02:36
Please also remember that the purpose of this Math Jam is to work through the solutions to AIME problems, and not to merely present the answers. "Working through the solutions" includes discussing problem-solving tactics. Also on occasion we may stop to prove things that you wouldn't necessary need to prove while doing the contest.

DPatrick 2015-03-21 19:02:48
So please, when a question is posted, do not simply respond with the final answer. That's not why we're here. We're going to work through the problems step-by-step, and comments that skip key steps or jump ahead in the problem, without providing explanation or motivation, won't be acknowledged.

AlcumusGuy 2015-03-21 19:02:51
will rrusczyk also be teaching tonight?

mathboxboro 2015-03-21 19:02:51
how about rruczyk?

DPatrick 2015-03-21 19:03:01
I think he's here just to keep an eye on me...

DPatrick 2015-03-21 19:03:19
Before we get started, I have a question for those of you who took the test: What was your favorite question on the test? What was your least favorite?

DPatrick 2015-03-21 19:04:19
A lot of you liked 12, which was pretty nice too I agree. My favorites were 5 and 11 because they were a little different.

DPatrick 2015-03-21 19:04:30
My least favorite was #9, which also seems to be a popular choice for least favorite.

DPatrick 2015-03-21 19:04:47
But we'll get to them all...let's get started! We're going to do all of 1 through 15, in order.

DPatrick 2015-03-21 19:04:55
1. The expressions \[A=1\times2+3\times4+5\times6+\cdots+37\times38+39\] and \[B=1+2\times3+4\times5+\cdots+38\times39\]are obtained by writing multiplication and addition operators in an alternating pattern between successive integers. Find the positive difference between integers $A$ and $B$.

DPatrick 2015-03-21 19:05:15
You'll notice the current problem will also be at the top of the window. You can resize that top area by dragging the horizontal bar.

akim99 2015-03-21 19:05:40
Group into terms

Tommy2000 2015-03-21 19:05:40
Group up products in the subtraction!

Darn 2015-03-21 19:05:40
Group corresponding terms in the two sums seems like a good idea (find a pattern)

AKAL3 2015-03-21 19:05:40
make some nice groupings for the differences

math_boy 2015-03-21 19:05:40
B is obviously greater, so we want B - A

urmilla 2015-03-21 19:05:40
Do B-A.

DPatrick 2015-03-21 19:05:48
$B$ looks bigger because it has that $38 \times 39$ term at the end.

DPatrick 2015-03-21 19:06:03
So let's compute $B-A$. (If we're wrong about it being bigger, we'll just get a negative number.)

DPatrick 2015-03-21 19:06:22
As some of you mentioned, there are a lot of common factors. So let's pair them up to make it easy to subtract, like so:

DPatrick 2015-03-21 19:06:27
\[\begin{array}{ccccccccccccc}
\phantom{-}(B&=&1&+&2\times3&+&4\times5&+&6\times7&+&\cdots&+&38\times39 &&\phantom{39})\\
-(A&=& & &1\times2&+&3\times4&+&5\times6&+&\cdots&+&37\times38&+&39)\\
\end{array}\]

DPatrick 2015-03-21 19:06:49
Then what happens?

Eugenis 2015-03-21 19:07:13
$B-A=-38+(2\times 2)+(2\times 4)+(2\times 6)+\cdots +(2\times 36)+(2\times 38)$

IMGUNNA 2015-03-21 19:07:13
common factors

cumo99 2015-03-21 19:07:13
factor

MSTang 2015-03-21 19:07:13
-38 + 2*(2+4+6+...+38)

pieslinger 2015-03-21 19:07:13
stuff cancels nicely

summitwei 2015-03-21 19:07:13
The middle terms are all multiples of 4

DPatrick 2015-03-21 19:07:20
Subtracting gives
\[\begin{array}{ccccccccccccc}
\phantom{-}(B&=&1&+&2\times3&+&4\times5&+&6\times7&+&\cdots&+&38\times39 &&\phantom{39})\\
-(A&=& & &1\times2&+&3\times4&+&5\times6&+&\cdots&+&37\times38&+&39)\\
\hline
B-A&=&1&+&2\times2&+&4\times2&+&6\times2&+&\cdots&+&38\times2 &-&39\\
\end{array}\]

DPatrick 2015-03-21 19:07:32
That's nice. Except for the first and the last terms, the middle terms are all multiples of 4.

supercomputer 2015-03-21 19:07:43
-38+4(sum from 1 to 19)

jam10307 2015-03-21 19:07:48
factor out 4

nosaj 2015-03-21 19:07:48
So factor out a 4 from middle terms

akim99 2015-03-21 19:07:51
which is $ 4(1+2+...+19) -38$

DPatrick 2015-03-21 19:07:56
Exactly:
\[
B-A = 1 + 4(1+2+3+\cdots+19)-39.
\]

ryanyz10 2015-03-21 19:08:26
4(190) - 38

Tommy2000 2015-03-21 19:08:26
$760-38=\boxed{722}$

csmath 2015-03-21 19:08:26
which is thus 190*4-38

C-bass 2015-03-21 19:08:26
=4(19 x 20 / 2) -38

MiamiHeat88 2015-03-21 19:08:32
4x190 - 38 = 760 - 38 = 722

urmilla 2015-03-21 19:08:32
722

stan23456 2015-03-21 19:08:32
which is 722.

DPatrick 2015-03-21 19:08:40
Right, now we're done:
\[
B-A = 1 + 4 \cdot \frac{19(20)}{2} - 39 = 1 + 760 - 39 = \boxed{722}.
\]

DPatrick 2015-03-21 19:08:59
Pretty nice #1 to get us warmed up, I thought.

DPatrick 2015-03-21 19:09:10
On to #2:

DPatrick 2015-03-21 19:09:15
2. The nine delegates to the Economic Cooperation Conference include 2 officials from Mexico, 3 officials from Canada, and 4 officials from the United States. During the opening session, three of the delegates fall asleep. Assuming that the three sleepers were determined randomly, the probability that exactly two of the sleepers are from the same country is $\frac mn$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

simon1221 2015-03-21 19:09:48
total ways is 9C3

MathDog0809 2015-03-21 19:09:48
9 choose three

urmilla 2015-03-21 19:09:48
first off 9C3 ways in total to pick the sleepers

DPatrick 2015-03-21 19:10:07
I like starting with the denominator in probability problems, since it's usually easy and on occasion provides insight.

DPatrick 2015-03-21 19:10:14
We must choose 3 people from the 9, so $\binom93 = \frac{9 \cdot 8 \cdot 7}{3!} = 84$ ways possible.

DPatrick 2015-03-21 19:10:34
And now we have to decide how to count the numerator.

spartan168 2015-03-21 19:11:03
Complimentary Counting!

fluffyanimal 2015-03-21 19:11:03
Casework or complementary counting both work

Sciolympian 2015-03-21 19:11:03
could we also do complementary counting?

DPatrick 2015-03-21 19:11:14
You could count this directly by casework, but I found complementary counting to be easier.

DPatrick 2015-03-21 19:11:19
What has to happen if it's not exactly two sleepers from the same country?

ninjataco 2015-03-21 19:11:59
1 sleeper from each country, or 3 from the same country

bli1999 2015-03-21 19:11:59
One from each country, or three from one country

AlcumusGuy 2015-03-21 19:11:59
one sleeper from each country or all three from same country

summitwei 2015-03-21 19:11:59
Either all from different countries or all from the same country

distortedwalrus 2015-03-21 19:11:59
either three from the same country, or all from different countries

willabc 2015-03-21 19:11:59
all three are from the same country or they are all from different countries

math_boy 2015-03-21 19:11:59
all three are from different countries, or all three the same

hesa57 2015-03-21 19:11:59
All the sleepers are from the same country or all are from different countries

DPatrick 2015-03-21 19:12:05
Right: either there's 1 sleeper from each country, or all 3 are from the same country.

DPatrick 2015-03-21 19:12:12
And both of these are really easy to count.

DPatrick 2015-03-21 19:12:15
In how many ways can we select 1 person from each country?

amburger66 2015-03-21 19:12:32
1 from each country: 2*3*4

AKAL3 2015-03-21 19:12:32
2*3*4

FTW 2015-03-21 19:12:32
2*3*4

swirlykick 2015-03-21 19:12:32
2*3*4=24

rocket13jg 2015-03-21 19:12:32
2*3*4=24

BFYSharks 2015-03-21 19:12:32
2*3*4

Darn 2015-03-21 19:12:32
First count cases where all are different: $2\times3\times4=24$

PencilPal 2015-03-21 19:12:32
2*3*4 = 24

football017 2015-03-21 19:12:32
2*3*4=24?

DPatrick 2015-03-21 19:12:39
We just multiply the choices for each person: $2 \cdot 3 \cdot 4 = 24$.

DPatrick 2015-03-21 19:12:45
In how many ways can we have all 3 sleepers from the same country?

morninglight 2015-03-21 19:13:08
1+4=5

brightknight 2015-03-21 19:13:08
4+1=5

eyux 2015-03-21 19:13:08
3C3+4C3=5

whatshisbucket 2015-03-21 19:13:08
4C3+3C3

william122 2015-03-21 19:13:08
1+4=5

xyuqing 2015-03-21 19:13:08
1+4=5

cumo99 2015-03-21 19:13:08
3C3 + 4C3 = 5

DPatrick 2015-03-21 19:13:12
Either we have all 3 Canadians, or we have 3 of the 4 Americans (which amounts to choosing an American to stay awake).

DPatrick 2015-03-21 19:13:21
Thus there are $1+4 = 5$ ways all 3 can be from the same country.

spartan168 2015-03-21 19:13:36
So 24 + 5 = 29

akim99 2015-03-21 19:13:36
24+5=29, which is what we DON'T want

DPatrick 2015-03-21 19:13:43
Right, this makes $24+5 = 29$ ways to not have what we want.

ryanyz10 2015-03-21 19:13:58
84 - 29 = 55... 55/84 so answer is 139?

danusv 2015-03-21 19:13:58
SO we have 1-29/84 = 55/84

hesa57 2015-03-21 19:13:58
$\frac{84-29}{84}$

princess-of-mathland 2015-03-21 19:13:58
1-29/84=55/84

DPatrick 2015-03-21 19:14:04
Thus there are $84 - 29 = 55$ ways to have what we want, and the probability is $\dfrac{55}{84}$.

nosaj 2015-03-21 19:14:13
so the probability is $\frac{55}{84}$, giving us an answer of 139

DPatrick 2015-03-21 19:14:16
This is already in lowest terms, so our answer is $55 + 84 = \boxed{139}$.

DPatrick 2015-03-21 19:14:42
Ok, onwards:

DPatrick 2015-03-21 19:14:47
3. There is a prime number $p$ such that $16p + 1$ is the cube of a positive integer. Find $p$.

Tommy2000 2015-03-21 19:15:06
Convert words to algebra!

p2pcmlp 2015-03-21 19:15:06
16p+1=n^3

MSTang 2015-03-21 19:15:06
16p + 1 = n^3

nosyarg 2015-03-21 19:15:06
16p+1=x^3

Eugenis 2015-03-21 19:15:06
Well we can start by making equations

stan23456 2015-03-21 19:15:06
let 16p+1=n^3, for some integer n.

DPatrick 2015-03-21 19:15:11
We can let $16p + 1 = n^3$, where $n$ is an integer. What's next?

jam10307 2015-03-21 19:15:33
difference o cubes

C-bass 2015-03-21 19:15:33
subtract 1 from both sides

bli1999 2015-03-21 19:15:33
Difference of cubes

AlcumusGuy 2015-03-21 19:15:33
Rewrite as 16p = n^3 - 1 = (n-1)(n^2 + n + 1)

hlasker1 2015-03-21 19:15:33
subtract the 1 and simplify the difference of cubes

azmath333 2015-03-21 19:15:33
16p = n^3 - 1^3

csmath 2015-03-21 19:15:33
Then we can do 16p = n^3-1

SilverPersian1 2015-03-21 19:15:33
-1 from both sides

DPatrick 2015-03-21 19:15:40
Good idea. We can write this as $16p = n^3 - 1$, which is nice because we can factor $n^3 - 1$ as a difference of cubes: $$16p = (n-1)(n^2 + n + 1).$$

DPatrick 2015-03-21 19:15:47
Hmm, we'd like to say that one of these factors is equal to $p$. Any observations that might help us in that direction?

whatshisbucket 2015-03-21 19:16:24
n^2+n+1 is always odd

brightknight 2015-03-21 19:16:24
n^2+n+1 is odd

MSTang 2015-03-21 19:16:24
n^2 + n + 1 is always odd

stan23456 2015-03-21 19:16:24
n^2+n+1 is odd

Tommy2000 2015-03-21 19:16:24
n^2+n+1 is always odd so n-1=16

zebrae 2015-03-21 19:16:24
n^2+n+1 is always odd, so n has to be 17

mjoshi 2015-03-21 19:16:24
n-1 = 16, so that n^2+n+1 is prime

mssmath 2015-03-21 19:16:24
n^2+n+1 is always odd

donot 2015-03-21 19:16:24
The last term is always odd

DPatrick 2015-03-21 19:16:37
Right: note that $n^2+n+1 = n(n+1) + 1$, so $n(n+1)$ is the product of an odd and an even, regardless of what $n$ is. Thus the second term is always odd.

DPatrick 2015-03-21 19:16:50
Therefore, since $p \not= 2$ (because 33 is certainly not the cube of a positive integer!), $p$ must be odd, so we must have $16 = n-1$ and $p = n^2 + n + 1$.

raxu 2015-03-21 19:17:21
n=17, p=307

cdl031apos 2015-03-21 19:17:21
n=17

Epic777 2015-03-21 19:17:21
n=17, p=307

brainiac1 2015-03-21 19:17:21
and 307=17^2+17+1 is prime

DPatrick 2015-03-21 19:17:33
Yes. Thus $n=17$ and $$p = n^2 + n + 1 = 17^2 + 17 + 1 = 289 + 17 + 1 = \boxed{307}.$$

DPatrick 2015-03-21 19:17:46
(You might check that 307 is prime as a check of your answer. Happily, it is!)

DPatrick 2015-03-21 19:18:07
Next, our first geometry problem:

DPatrick 2015-03-21 19:18:12
4. Point $B$ lies on line segment $\overline{AC}$ with $AB = 16$ and $BC = 4$. Points $D$ and $E$ lie on the same side of line $AC$ forming equilateral triangles $\triangle ABD$ and $\triangle BCE$. Let $M$ be the midpoint of $\overline{AE}$, and $N$ be the midpoint of $\overline{CD}$. The area of $\triangle BMN$ is $x$. Find $x^2$.

maverick8 2015-03-21 19:18:25
Draw a diagram!

rlz 2015-03-21 19:18:25
An accurate diagram is important!

simon1221 2015-03-21 19:18:25
make a diagram

tdeng 2015-03-21 19:18:25
diagram

MiamiHeat88 2015-03-21 19:18:25
draw it

DPatrick 2015-03-21 19:18:29
We can try to sketch a picture of all this. (Having a ruler on contest day really helps!)

DPatrick 2015-03-21 19:18:33

DPatrick 2015-03-21 19:18:54
A fairly good diagram might lead to a conjecture using this picture...

WhaleVomit 2015-03-21 19:19:08
MNB looks like equilateral!

C-bass 2015-03-21 19:19:08
mbn is equilateral?????

whatshisbucket 2015-03-21 19:19:08
BMN looks equilateral

akim99 2015-03-21 19:19:08
Hmmm $NMB$ looks equilateral

william122 2015-03-21 19:19:08
its an equilateral triangle!

Darn 2015-03-21 19:19:08
$\triangle MNB$ is equilateral

fluffyanimal 2015-03-21 19:19:08
looks equilateral

PencilPal 2015-03-21 19:19:08
equilateral

Jz2435 2015-03-21 19:19:08
MNB is equilateral

NikhilP 2015-03-21 19:19:08
MNB is equalateral

DPatrick 2015-03-21 19:19:15
One thing a really good sketch helps with is that you might notice that $BMN$ looks equilateral. That might help us later, if we can prove it.

DPatrick 2015-03-21 19:19:25
How are we going to keep track of where all these points are?

AKAL3 2015-03-21 19:19:46
coord bash

BFYSharks 2015-03-21 19:19:46
Coordinates

howie2000 2015-03-21 19:19:46
coordinate plane

Sciolympian 2015-03-21 19:19:46
using coordinates

temp8909 2015-03-21 19:19:46
analytic geometry

RedPhoenix 2015-03-21 19:19:46
Could we use coordinates?

morninglight 2015-03-21 19:19:46
coordinates!

math_boy 2015-03-21 19:19:46
coordinate plane

spartan168 2015-03-21 19:19:46
coordinate bashing lol

xyuqing 2015-03-21 19:19:46
Coordinates

summitwei 2015-03-21 19:19:46
Coordinates!

DPatrick 2015-03-21 19:19:54
I agree; I used coordinates. Coordinates are good of keeping track of collinear points (like $A$, $B$, $C$), especially when the lengths are known, and they're good for computing midpoints.

DPatrick 2015-03-21 19:20:08
So let's set $A = (0,0)$, $B = (16,0)$, and $C = (20,0)$.

DPatrick 2015-03-21 19:20:23
What are $D$ and $E$?

MSTang 2015-03-21 19:21:03
D = (8, 8sqrt(3)) and E = (18, 2sqrt(3))

urmilla 2015-03-21 19:21:03
D(8,8sqrt3); E(18,2sqrt3)

ryanyz10 2015-03-21 19:21:03
8, 8sqrt(3) is D

rocket13jg 2015-03-21 19:21:03
D(8, 8root3), E(18, 2root3)

ryanyz10 2015-03-21 19:21:03
E is 18, 2sqrt(3)

ninjataco 2015-03-21 19:21:03
D (8, 8sqrt3) and E (18, 2sqrt3)

DPatrick 2015-03-21 19:21:08
$D$'s $x$-coordinate is halfway between $A$ and $B$, and $D$'s $y$-coordinate is the height of $ABD$, which is $\sqrt3/2$ times $AB$.

DPatrick 2015-03-21 19:21:16
So $D = (8,8\sqrt3)$.

DPatrick 2015-03-21 19:21:23
By similar logic, $E = (18,2\sqrt3)$.

akim99 2015-03-21 19:21:35
Now find the midpoints

spartan168 2015-03-21 19:21:39
Midpoint Formula!

jam10307 2015-03-21 19:21:39
midpt formula

DPatrick 2015-03-21 19:21:43
Right. To compute a midpoint, we average the coordinates.

24iam24 2015-03-21 19:22:07
so M(9, √3) and N(14, 4√3)

Eugenis 2015-03-21 19:22:07
m= $(9,\sqrt{3})$

DPatrick 2015-03-21 19:22:11
So, $M$ is the average of $E = (18,2\sqrt3)$ and $A = (0,0)$. Hence $M = (9,\sqrt3)$.
Similarly, $N$ is the average of $D = (8,8\sqrt3)$ and $C=(20,0)$. Hence $N = (14,4\sqrt3)$.

DPatrick 2015-03-21 19:22:19
So our triangle $BMN$ has vertices $(16,0)$, $(9,\sqrt3)$, and $(14,4\sqrt3)$.

hesa57 2015-03-21 19:22:47
Distance formula

brightknight 2015-03-21 19:22:47
distance formula for side lengths

bli1999 2015-03-21 19:22:47
Distance formula

amburger66 2015-03-21 19:22:47
using distance formula, we can confirm that it's equilateral

stan23456 2015-03-21 19:22:47
we can prove that its equilateral

Sciolympian 2015-03-21 19:22:47
calculate side lengths now

princess-of-mathland 2015-03-21 19:22:47
By distance formula, each side is sqrt52

raxu 2015-03-21 19:22:47
And by distance formula, BMN is equilateral with side length sqrt(52).

DPatrick 2015-03-21 19:23:01
Right. We suspected it was equilateral...

DPatrick 2015-03-21 19:23:07
...and we can verify from directly computation that each side has length $\sqrt{52}$:
\begin{align*}
BM &= \sqrt{7^2 + (\sqrt3)^2} = \sqrt{49+3} = \sqrt{52}, \\
BN &= \sqrt{2^2 + (4\sqrt3)^2} = \sqrt{4+8} = \sqrt{52}, \\
MN &= \sqrt{5^2 + (3\sqrt3)^2} = \sqrt{25+27} = \sqrt{52}.
\end{align*}

DPatrick 2015-03-21 19:23:16
So $BMN$ is an equilateral triangle with side length $\sqrt{52}$. What is its area?

MSTang 2015-03-21 19:23:35
52sqrt(3)/4 = 13sqrt(3)

legolego 2015-03-21 19:23:35
13sqrt3

mathboxboro 2015-03-21 19:23:35
13root3

MathDog0809 2015-03-21 19:23:35
13sqrt3?

cumo99 2015-03-21 19:23:35
13\sqrt{3}

csmath 2015-03-21 19:23:35
13sqrt(3)

IMGUNNA 2015-03-21 19:23:35
13sqrt3

DPatrick 2015-03-21 19:23:39
The area is $\dfrac{s^2\sqrt3}{4} = \dfrac{52\sqrt3}{4} = 13\sqrt3$.

DPatrick 2015-03-21 19:23:45
And the final answer is this area squared, or $13^2 \cdot 3 = 169 \cdot 3 = \boxed{507}$.

DPatrick 2015-03-21 19:24:11
I should mention, as many of you did, that you could use the Shoelace Theorem to compute the area from the coordinates; for example:
\[
\left|\frac12\begin{vmatrix} -7 & \sqrt3 \\ -2 & 4\sqrt3 \end{vmatrix}\right| = \left|\frac12(-28\sqrt3 + 2\sqrt3)\right| = 13\sqrt3.
\]

DPatrick 2015-03-21 19:24:30
(If you don't know the Shoelace Theorem, I encourage you to look it up when we're done!)

DPatrick 2015-03-21 19:25:00
But since we suspected the triangle was equilateral, and it was pretty easy to verify that it was, I found that to be a bit easier and less computational.

DPatrick 2015-03-21 19:25:19
On to #5:

DPatrick 2015-03-21 19:25:27
5. In a drawer Sandy has 5 pairs of socks, each pair a different color. On Monday Sandy selects two individual socks at random from the 10 socks in the drawer. On Tuesday Sandy selects 2 of the remaining 8 socks at random and on Wednesday two of the remaining 6 socks at random. The probability that Wednesday is the first day Sandy selects matching socks is $\frac mn$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

DPatrick 2015-03-21 19:25:49
You could certainly solve this problem with some careful casework, but there's a clever trick we can use to make this problem a lot easier.

ryanyz10 2015-03-21 19:26:07
work backwards?

nosaj 2015-03-21 19:26:07
It is easier to do this problem backwards (pick Wednesday first)

AlcumusGuy 2015-03-21 19:26:07
you can rearrange the days

william122 2015-03-21 19:26:07
work backwards

xyuqing 2015-03-21 19:26:07
Do the last day first

DPatrick 2015-03-21 19:26:11
Right!

DPatrick 2015-03-21 19:26:14
Generally in counting (or probability, which is really just counting most of the time), we want to deal with the most restrictive condition first.

DPatrick 2015-03-21 19:26:22
Here, the most restrictive condition is that the socks match on Wednesday.

DPatrick 2015-03-21 19:26:29
So let's pretend that Wednesday comes first!

DPatrick 2015-03-21 19:26:36
Now if you're thinking "Wait a minute, we can't do that -- Monday clearly comes first!": imagine that Sandy lays out all of her socks in a row for the week, then just takes the first 2 socks on Monday, the next two socks on Tuesday, and so on. It doesn't matter in what order she places socks in her row -- all 10 socks will eventually get placed.

DPatrick 2015-03-21 19:26:54
So, pretending that Wednesday is first, what's the probability that she gets a match?

BFYSharks 2015-03-21 19:27:12
Probability 1/9

jigglypuff 2015-03-21 19:27:12
1/9

summitwei 2015-03-21 19:27:12
1/9

RedPhoenix 2015-03-21 19:27:12
1/9

Studiosa 2015-03-21 19:27:12
1/9

temp8909 2015-03-21 19:27:12
1/9

whatshisbucket 2015-03-21 19:27:12
1/9

doodlemaster7 2015-03-21 19:27:12
1/9

NikhilP 2015-03-21 19:27:12
1/9

DPatrick 2015-03-21 19:27:19
Sure: no matter what first socks she picks, exactly 1 of the remaining 9 socks will match. So the probability of a match is $\frac19$.

DPatrick 2015-03-21 19:27:29
With the 8 remaining socks, what's the probability that she does NOT get a match on Monday?

ninjataco 2015-03-21 19:27:52
6/7

Matt17 2015-03-21 19:27:52
6/7

raxu 2015-03-21 19:27:52
6/7

jigglypuff 2015-03-21 19:27:52
6/7

nosyarg 2015-03-21 19:27:52
6/7

dtxiong 2015-03-21 19:27:52
6/7

mjoshi 2015-03-21 19:27:52
6/7

meteor88 2015-03-21 19:27:52
6/7

DPatrick 2015-03-21 19:28:10
Right, it's the reverse of Wednesday: no matter what first sock she picks, there are 1 matching sock and 6 non-matching socks remaining.

DPatrick 2015-03-21 19:28:14
So the probability of a non-match on Monday (given that we already have a match on Wednesday) is $\frac67$.

DPatrick 2015-03-21 19:28:22
Now what's the probability of a non-match on Tuesday?

DPatrick 2015-03-21 19:28:36
Note there are 6 socks left: 2 matching pairs, and 2 non-matching extras (the two that match Monday's socks).

fluffyanimal 2015-03-21 19:28:58
13/15

xyuqing 2015-03-21 19:28:58
13/15

RedPhoenix 2015-03-21 19:28:58
13/15

raxu 2015-03-21 19:28:58
1-2/(6C2)=13/15

bli1999 2015-03-21 19:28:58
1-2/15=13/15

whatshisbucket 2015-03-21 19:28:58
13/15

Studiosa 2015-03-21 19:28:58
13/15

DPatrick 2015-03-21 19:29:05
Exactly. Out of the $\binom62 = 15$ pairs that she could choose, 2 match and 13 don't.

DPatrick 2015-03-21 19:29:10
Thus the probability of a non-match on Tuesday is $\frac{13}{15}$.

ryanyz10 2015-03-21 19:29:30
multiply them

csmath 2015-03-21 19:29:30
then we can just multiply these all

akim99 2015-03-21 19:29:30
Time to multiply

DPatrick 2015-03-21 19:29:38
Right: the overall probability is
\[
\frac{1}{9} \cdot \frac{6}{7} \cdot \frac{13}{15} = \frac{26}{315}.
\]
(A factor of 3 cancels when we convert to lowest terms.)

DPatrick 2015-03-21 19:29:48
And the final answer is $26 + 315 = \boxed{341}$.

DPatrick 2015-03-21 19:30:19
Again, the moral of the story: generally in counting (or probability, which is really just counting most of the time), we want to deal with the most restrictive condition first.

DPatrick 2015-03-21 19:30:37
OK, we're one-third of the way home! On to #6:

DPatrick 2015-03-21 19:30:42
6. Points $A,B,C,D,$ and $E$ are equally spaced on a minor arc of a circle. Points $E,F,G,H,I,$ and $A$ are equally spaced on a minor arc of a second circle with center $C$ as shown in the figure below. The angle $\angle ABD$ exceeds $\angle AHG$ by $12^{\circ}$. Find the degree measure of $\angle BAG$.

DPatrick 2015-03-21 19:30:45

mathtastic 2015-03-21 19:31:15
on the actual contest the points weren't dotted

nosaj 2015-03-21 19:31:15
Wait; on the actual test the points didn't have dots.

DPatrick 2015-03-21 19:31:33
That's weird, because the copy that the AMC sent me does have dots!

AlcumusGuy 2015-03-21 19:31:59
Let x = arc AB, y = arc AI

summitwei 2015-03-21 19:31:59
Call angle ABC $\alpha$ and AIH $\beta$

DPatrick 2015-03-21 19:32:09
Sure, let's set up some variables. Let's make the 4 top arcs each be $x$ (degrees), and the bottom 5 arcs each be $y$ (degrees).

DPatrick 2015-03-21 19:32:22
How can we relate $x$ and $y$?

Tommy2000 2015-03-21 19:32:51
First relate ABD and AHG

math_boy 2015-03-21 19:32:51
<ABD = <AHG + 12

xyuqing 2015-03-21 19:32:51
C is a center.

p2pcmlp 2015-03-21 19:32:51
find ABD and AHG

Tommy2000 2015-03-21 19:32:51
Express ABD iand AHG in terms of x and y

DPatrick 2015-03-21 19:32:57
There seem to be two ways:
- using the data given in the problem that $C$ is the center of the bottom arc's circle
- using the data given in the problem about the two angles that differ by $12^\circ$.

DPatrick 2015-03-21 19:33:08
The hope is: each of these should give us an equation relating $x$ and $y$ (hopefully) -- then we'll have 2 equations in 2 variables, so we'll be able to solve the system!

DPatrick 2015-03-21 19:33:18
What does $C$ being the center of the bottom arc's circle tell us?

nosaj 2015-03-21 19:33:46
ECA=5y

BFYSharks 2015-03-21 19:33:46
Angle ECA = 5y

DPatrick 2015-03-21 19:33:51
Right. $\angle ACE$ is a central angle that intercepts the entire bottom arc.

DPatrick 2015-03-21 19:33:57
So $\angle ACE = 5y$.

DPatrick 2015-03-21 19:34:06
But how can we use the top arc to compute $\angle ACE$ in terms of $x$?

nosaj 2015-03-21 19:34:37
However, $\angle ECA$ is also $\frac{360-4x}{2}$ it inscribes that arc.

wangth100 2015-03-21 19:34:37
$ /angle{ACE} = 180-2x $

ryanyz10 2015-03-21 19:34:37
inscribed angle

Tommy2000 2015-03-21 19:34:37
$180-2x$

viv7000 2015-03-21 19:34:37
ACE is (360-4x)/2

rlz 2015-03-21 19:34:37
(360-4x)/2

maverick8 2015-03-21 19:34:37
360-4x divided by 2

stan23456 2015-03-21 19:34:37
180-2x

mathboxboro 2015-03-21 19:34:37
180-2x

DPatrick 2015-03-21 19:34:44
Arc ${AE}$ is 4x, so $\angle ACE$ is inscribed in the top circle, intercepting an arc of size $360 - 4x$.

DPatrick 2015-03-21 19:34:54
Thus $\angle ACE = \frac12(360 - 4x) = 180 - 2x$.

DPatrick 2015-03-21 19:35:08
Great: this gives us the equation \[5y = 180 - 2x.\]

DPatrick 2015-03-21 19:35:18
Now on to the other data: $\angle ABD = \angle AHG + 12$.

DPatrick 2015-03-21 19:35:23
What's $\angle ABD$?

mathboxboro 2015-03-21 19:35:53
(360-3x)/2

ryanyz10 2015-03-21 19:35:53
(360 - 3x)/2

rlz 2015-03-21 19:35:53
(360-3x)/2

RedPhoenix 2015-03-21 19:35:53
180 - 3x/2

brainiac1 2015-03-21 19:35:53
180-3x/2

william122 2015-03-21 19:35:53
1/2(360-3x)

azmath333 2015-03-21 19:35:53
180 degrees - 3x/2

DPatrick 2015-03-21 19:35:59
Yes. It intercepts an arc of size $360 - 3x$ from the top circle, so $\angle ABD = \frac12(360-3x) = 180 - \frac32x$.

DPatrick 2015-03-21 19:36:12
What's $\angle AHG$?

ninjataco 2015-03-21 19:36:34
(360-3y)/2

dtxiong 2015-03-21 19:36:34
1/2(360-3y)

swe1 2015-03-21 19:36:34
(360-3y)/2

bli1999 2015-03-21 19:36:34
180-3y/2

whatshisbucket 2015-03-21 19:36:34
(360-3y)/2

DPatrick 2015-03-21 19:36:41
Basically the same idea: It intercepts an arc of $360 - 3y$ of the bottom circle, so $\angle AHG = \frac12(360 - 3y) = 180 - \frac32y$.

DPatrick 2015-03-21 19:36:49
So we have the equation
\[
180 - \frac32x = 180 - \frac32y + 12.
\]

MathDog0809 2015-03-21 19:37:01
find x and y!

C-bass 2015-03-21 19:37:01
solve system?

DPatrick 2015-03-21 19:37:14
Right, our plan worked! We've got two linear equations in $x$ and $y$, so we can solve for them.

jigglypuff 2015-03-21 19:37:27
difference of 8

dragon21 2015-03-21 19:37:34
simplified is y-x=8

DPatrick 2015-03-21 19:37:42
The second equation simplifies to $3x = 3y - 24$, or $x = y - 8$.

Studiosa 2015-03-21 19:38:01
x=20 y=28

rocket13jg 2015-03-21 19:38:01
x=20, y=28

ninjataco 2015-03-21 19:38:01
x=20, y=28

DPatrick 2015-03-21 19:38:06
Substituting this back into the first equation gives
\[
5y = 180 - 2(y-8) = 196 - 2y.
\]

DPatrick 2015-03-21 19:38:13
So $7y = 196$, and $y = 28$. And then $x = y-8 = 20$.

DPatrick 2015-03-21 19:38:26
To finish, we want to compute $\angle BAG$:

DPatrick 2015-03-21 19:38:29

DPatrick 2015-03-21 19:38:36
That angle doesn't nicely intercept one circle or the other, so what can we do?

nosaj 2015-03-21 19:38:52
Note that $\angle BAG = \angle BAE + \angle EAG$.

Matt17 2015-03-21 19:38:52
Make line from A to E to split angle

temp8909 2015-03-21 19:38:52
BAE+EAG

csmath 2015-03-21 19:38:52
Make it the sum of 2 angles

mathtastic 2015-03-21 19:38:52
$\angle BAE+\angle GAE$

AKAL3 2015-03-21 19:38:52
draw AE

nsd 2015-03-21 19:38:52
sum if BAE and EAG

DPatrick 2015-03-21 19:39:00
No problem -- we can draw in $\overline{AE}$ so that we break up the angle into two angles, each of which intercepts an arc of a single circle:

DPatrick 2015-03-21 19:39:05

maverick8 2015-03-21 19:39:33
BAG=BAE+EAG=3x/2+2y/2

Sciolympian 2015-03-21 19:39:33
inscribed angle formula

csmath 2015-03-21 19:39:33
So it's just y + 3x/2

mathtastic 2015-03-21 19:39:33
$\frac{3x+2y}{2}$

DPatrick 2015-03-21 19:39:40
The top part intercepts an arc of $3x$, so $\angle BAE = \frac32(x) = \frac32(20) = 30$.

DPatrick 2015-03-21 19:39:47
The bottom part intercepts an arc of $2y$, so $\angle EAG = \frac12(2y) = y = 28$.

xyuqing 2015-03-21 19:40:05
30+28=58

yuvi18 2015-03-21 19:40:05
58

summitwei 2015-03-21 19:40:05
058

DPatrick 2015-03-21 19:40:06
And thus,
\[
\angle BAG = \angle BAE + \angle EAG = 30 + 28 = \boxed{058}.
\]

DPatrick 2015-03-21 19:40:43
From one algebra-laced geometry problem to another, here's #7:

DPatrick 2015-03-21 19:40:47
7. In the diagram below, $ABCD$ is a square. Point $E$ is the midpoint of $\overline{AD}$. Points $F$ and $G$ lie on $\overline{CE}$ and $H$ and $J$ lie on $\overline{AB}$ and $\overline{BC}$, respectively, so $FGHJ$ is a square. Points $K$ and $L$ lie on $\overline{GH}$, and $M$ and $N$ lie on $\overline{AD}$ and $\overline{AB}$, respectively, so that $KLMN$ is a square. The area of $KLMN$ is 99. Find the area of $FGHJ$.

DPatrick 2015-03-21 19:40:51

DPatrick 2015-03-21 19:41:02
What strikes you about this picture?

AlcumusGuy 2015-03-21 19:41:25
Similar triangles!

Darn 2015-03-21 19:41:25
Similar triangles

trumpeter 2015-03-21 19:41:25
similar triangles!

fluffyanimal 2015-03-21 19:41:25
similar triangles everywhere

ninjataco 2015-03-21 19:41:25
a bunch of similar $1-2-\sqrt{5}$ right triangles!

princess-of-mathland 2015-03-21 19:41:25
Similar triangles!!!

raxu 2015-03-21 19:41:25
Note that all the triangles we see are similar.

eyux 2015-03-21 19:41:25
theres a lot of similar triangles

torquoiseworld 2015-03-21 19:41:25
similar triangles

math_boy 2015-03-21 19:41:25
SIMILAR TRIANGLES

cumo99 2015-03-21 19:41:25
similar triangles

WhaleVomit 2015-03-21 19:41:25
similar triangles

gaberen 2015-03-21 19:41:25
So many similar triangles

MiamiHeat88 2015-03-21 19:41:25
it has a lot of similar triangles

brainiac1 2015-03-21 19:41:25
the similar triangles

maverick8 2015-03-21 19:41:25
Similar Triangles

Epic777 2015-03-21 19:41:25
Lots of similar triangles

hlasker1 2015-03-21 19:41:25
similar triangles

BFYSharks 2015-03-21 19:41:25
Similar triangles

morninglight 2015-03-21 19:41:25
Similar triangles

stan23456 2015-03-21 19:41:25
so many 1-2-sqrt5 triangles.

DPatrick 2015-03-21 19:41:36
Yeah, there are tons of similar triangles lying about.

DPatrick 2015-03-21 19:41:46
$ED$ is half of $DC$, so all of the triangles have sides in the ratio $1 : 2 : \sqrt{5}$.

DPatrick 2015-03-21 19:42:08
And, conveniently, sides $AB$ and $BC$ of the big square are made up of pieces of smaller triangles, each of which also has a side of one of our smaller squares. So we can relate these pieces to the sides of the squares, and use $AB = BC$ to set up an equation.

DPatrick 2015-03-21 19:42:30
In particular, let's set $x$ to be the be the side of the square $FGHJ$. We'll try to use $AB = BC$ to set up an equation for $x$.

DPatrick 2015-03-21 19:42:41
What's $AB$ in terms of $x$?

DPatrick 2015-03-21 19:43:42
We have to break up $AB = AN + NH + HB$ in order to compute it.

DPatrick 2015-03-21 19:43:46
What's $AN$?

Studiosa 2015-03-21 19:44:11
3 sqrt(11)/sqrt(5)

MSTang 2015-03-21 19:44:11
sqrt(99)/5

ninjataco 2015-03-21 19:44:11
$\sqrt{99}/\sqrt{5}$

summitwei 2015-03-21 19:44:11
sqrt 99/sqrt 5

MSTang 2015-03-21 19:44:11
sqrt(99) / sqrt(5)

MiamiHeat88 2015-03-21 19:44:11
(sqrt99)/(sqrt5)

bli1999 2015-03-21 19:44:11
sqrt99/sqrt5

DPatrick 2015-03-21 19:44:15
$AN$ is the "1" side of $AMN$, where the "$\sqrt5$" side is $MN = \sqrt{99}$. (Let's leave it as $\sqrt{99}$ rather than $3\sqrt{11}$ until we have a compelling reason to change it.)

DPatrick 2015-03-21 19:44:22
Thus $AN = \dfrac{\sqrt{99}}{\sqrt5}$.

DPatrick 2015-03-21 19:44:30
How about $NH$?

MiamiHeat88 2015-03-21 19:44:38
we should use a variable for MN and plug in the value when we are done computing

DPatrick 2015-03-21 19:45:02
We could certainly have done that...it's not a bad idea at all. If it were any more complicated than $\sqrt{99}$ I certainly would have done that.

rlz 2015-03-21 19:45:21
$\frac{\sqrt{5*99}}{2}$

hwl0304 2015-03-21 19:45:21
sqrt99*sqrt5/2

IMGUNNA 2015-03-21 19:45:21
sqrt99 * sqrt 5 / 2

azmath333 2015-03-21 19:45:21
$\frac{\sqrt{99\cdot 5}}{2}$

chaoshadow37 2015-03-21 19:45:28
NH= sqrt(99)*sqrt(5)/2

DPatrick 2015-03-21 19:45:29
$NH$ is the "$\sqrt5$" side of $NHK$, where the "2" side is $\sqrt{99}$.

DPatrick 2015-03-21 19:45:37
Thus $NH = \dfrac{\sqrt{5}\cdot\sqrt{99}}{2}$.

DPatrick 2015-03-21 19:45:45
Finally, what's $HB$?

ninjataco 2015-03-21 19:46:10
$2x/\sqrt{5}$

rocket13jg 2015-03-21 19:46:10
2x/sqrt5

SHARKYBOY 2015-03-21 19:46:10

FTW 2015-03-21 19:46:10
2x/sqrt5

nosaj 2015-03-21 19:46:10
$x \times \frac{2}{\sqrt5}$

whatshisbucket 2015-03-21 19:46:10
2x/sqrt5

eswa2000 2015-03-21 19:46:10
2x/sqrt{5}

24iam24 2015-03-21 19:46:10
x*2/√5

DPatrick 2015-03-21 19:46:15
$HB$ is the "2" side of $BHJ$, where the "$\sqrt{5}$" side is $x$.

DPatrick 2015-03-21 19:46:20
Thus $HB = \dfrac{2x}{\sqrt5}$.

DPatrick 2015-03-21 19:46:26
Adding these up gives
\[
AB = AN + NH + HB = \frac{\sqrt{99}}{\sqrt5} + \frac{\sqrt5 \cdot \sqrt{99}}{2} + \frac{2x}{\sqrt5}.
\]

DPatrick 2015-03-21 19:46:40
Looks messy, but maybe nice things will happen later.

DPatrick 2015-03-21 19:46:44
OK, how about $BC = BJ + JC$?

FTW 2015-03-21 19:47:10
Bj = x/sqrt5

nosaj 2015-03-21 19:47:10
$BJ=\frac{x}{\sqrt5}$

csmath 2015-03-21 19:47:10
We can do BJ = x/sqrt(5)

whatshisbucket 2015-03-21 19:47:10
BJ=x/sqrt5

MSTang 2015-03-21 19:47:29
BJ = x/sqrt(5) and JC = x * sqrt(5)/2

ryanyz10 2015-03-21 19:47:29
x/sqrt(5) + xsqrt(5)/2

maverick8 2015-03-21 19:47:29
$BC=BJ+JC=x/sqrt(5)+xsqrt(5)/2 $

azmath333 2015-03-21 19:47:29
$\frac{x}{\sqrt{5}} + \frac{x\sqrt{5}}{2}$

maverick8 2015-03-21 19:47:29
BC=BJ+JC=x/sqrt(5)+xsqrt(5)/2

Darn 2015-03-21 19:47:29
$\frac{x\sqrt{5}}{2}+\frac{x}{\sqrt{5}}$

DPatrick 2015-03-21 19:47:33
$BJ$ is the "1" side of $BJH$ where the "$\sqrt5$" side is $x$. So $BJ = \dfrac{x}{\sqrt5}$.

DPatrick 2015-03-21 19:47:38
$JC$ is the "$\sqrt5$" side of $CJF$ where the "2" side is $x$. So $JC = \dfrac{\sqrt5 \cdot x}{2}$.

DPatrick 2015-03-21 19:47:44
Thus
\[
BC = BJ + JC = \dfrac{x}{\sqrt5} + \dfrac{\sqrt5 \cdot x}{2}.
\]

ninjataco 2015-03-21 19:47:59
now we can set AB=BC and solve for x

nsd 2015-03-21 19:47:59
AB = BC

24iam24 2015-03-21 19:47:59
then equate them because AB=BC

DPatrick 2015-03-21 19:48:03
So using $AB = BC$, we get the equation:
\[
\frac{\sqrt{99}}{\sqrt5} + \frac{\sqrt5 \cdot \sqrt{99}}{2} + \frac{2x}{\sqrt5} = \dfrac{x}{\sqrt5} + \dfrac{\sqrt5 \cdot x}{2}.
\]

DPatrick 2015-03-21 19:48:21
How do we solve this?

whatshisbucket 2015-03-21 19:48:30
multiply by 2sqrt5

nosaj 2015-03-21 19:48:30
multiply both sides by $2\sqrt5$ cause fractions eww

stan23456 2015-03-21 19:48:30
multiply by 2sqrt5

nosyarg 2015-03-21 19:48:30
clear the denominators?

danusv 2015-03-21 19:48:30
multiply by 2 root 5

DPatrick 2015-03-21 19:48:35
I'd multiply through by $2\sqrt5$ to clear the denominators. Happily, that gets rid of the $\sqrt5$'s as well:
\[
2\sqrt{99} + 5\sqrt{99} + 4x = 2x + 5x.
\]

DPatrick 2015-03-21 19:48:45
Wow, that turned out nice!

csmath 2015-03-21 19:49:16
3x = 7sqrt (99)

C-bass 2015-03-21 19:49:16
x = 7sqrt(11)

summitwei 2015-03-21 19:49:16
So x=7sqrt11

ryanyz10 2015-03-21 19:49:16
x = 7sqrt(99)/3

IMGUNNA 2015-03-21 19:49:16
7sqrt99 = 3x

DPatrick 2015-03-21 19:49:30
Right. We have just $7\sqrt{99} = 3x$. That gives $x = 7\sqrt{11}$.

maverick8 2015-03-21 19:49:45
x^2=539

RedPhoenix 2015-03-21 19:49:45
x = 7 rt 11, so x^2 is 539

SHARKYBOY 2015-03-21 19:49:45

DPatrick 2015-03-21 19:49:53
Thus $x^2 = 49 \cdot 11 = \boxed{539}$ is our answer.

DPatrick 2015-03-21 19:50:24
Enough geometry for a little while...on to #8:

DPatrick 2015-03-21 19:50:28
8. For a positive integer $n$, let $s(n)$ denote the sum of the digits of $n$. Find the smallest positive integer $n$ satisfying $s(n)=s(n+864)=20$.

DPatrick 2015-03-21 19:50:43
How many digits does the target number have?

doodlemaster7 2015-03-21 19:51:01
we know that n has to be a 3 digit number

spartan168 2015-03-21 19:51:01
At least 3

summitwei 2015-03-21 19:51:01
3 because this is AIME

hwl0304 2015-03-21 19:51:01
0<n<999 so 3

brainiac1 2015-03-21 19:51:01
3 digits

DPatrick 2015-03-21 19:51:06
Since each digit of $n$ contributes at most 9 to $s(n)$, we know $n$ must have at least 3 digits.

DPatrick 2015-03-21 19:51:12
And since it's the AIME and $n$ is our final answer, we know that $n$ has exactly 3 digits!

DPatrick 2015-03-21 19:51:26
What does $s(n)=s(n+864)$ tell us about what happens when we add? What must happen when we add in order for the digit sum not to change?

MSTang 2015-03-21 19:51:59
carrying

chaoshadow37 2015-03-21 19:51:59
it has to regroup

rlz 2015-03-21 19:51:59
Carrying

eswa2000 2015-03-21 19:51:59
there's carry over's

ooooo1 2015-03-21 19:51:59
exactly two digits carry over when we add

xyuqing 2015-03-21 19:51:59
2 carries

Sciolympian 2015-03-21 19:51:59
2 carries since each carry subtracts 9 from digit sum and 864 has digit sum of 18

kuilin 2015-03-21 19:51:59
carrying

DPatrick 2015-03-21 19:52:06
We have to carry. In fact, every time we carry, we reduce one digit by 10 and increase the next digit by 1. Therefore, carrying reduces the digit sum by 9.

DPatrick 2015-03-21 19:52:27
Since 8+6+4=18, we have to carry exactly twice when we add 864 to $n$, in order to subtract 18 from the digit sum and leave it overall unchanged.

nosaj 2015-03-21 19:52:39
Do casework based on which place values carry.

DPatrick 2015-03-21 19:52:49
Indeed -- is there any digits that we know must carry?

dragon21 2015-03-21 19:53:05
The smallest possible is 299

zacchro 2015-03-21 19:53:05
hundreds digit has to carry

MSTang 2015-03-21 19:53:05
Hundreds - since n >= 299

nosaj 2015-03-21 19:53:05
Yes hundreds

AlcumusGuy 2015-03-21 19:53:05
hundreds

mathbeida 2015-03-21 19:53:05
hundreds

fluffyanimal 2015-03-21 19:53:05
hundreds

willabc 2015-03-21 19:53:05
hundreds digit must carry

DPatrick 2015-03-21 19:53:13
Right. Since $20=9+9+2$, the smallest the hundreds digit can possibly be is 2, so the hundreds digit must carry.

DPatrick 2015-03-21 19:53:19
We have two cases now: we carry the hundreds and tens digits, or the hundreds and ones digit.

DPatrick 2015-03-21 19:53:30
Which one is likely to be more fruitful?

Studiosa 2015-03-21 19:53:59
hundreds and tens

mathperson9 2015-03-21 19:53:59
Hundreds and tehns

ninjataco 2015-03-21 19:53:59
hundreds and tens

temp8909 2015-03-21 19:53:59
hundreds and tens

Sciolympian 2015-03-21 19:53:59
hundreds and tens

ryanyz10 2015-03-21 19:53:59
hundreds and tens?

chaoshadow37 2015-03-21 19:53:59
hundreds and tens

Ramanan369 2015-03-21 19:53:59
hundreds and tens

DPatrick 2015-03-21 19:54:13
The ones digit of $n$ can be much larger without carrying than the tens digit. Therefore we can make the sum of the tens and ones digit largest (and thus the entire number smallest, which is our goal) by carrying from the tens digit.

DPatrick 2015-03-21 19:54:20
So what's the smallest $n$ with $s(n)=20$ and such that $n+864$ carries in the tens and hundreds digits?

bli1999 2015-03-21 19:54:45
695

whatshisbucket 2015-03-21 19:54:45
695

xyuqing 2015-03-21 19:54:45
695!

hlasker1 2015-03-21 19:54:45
695

Royalreter1 2015-03-21 19:54:45
695

maverick8 2015-03-21 19:54:45
The last digit should be 5

PencilPal 2015-03-21 19:54:45
695

DPatrick 2015-03-21 19:55:10
Exactly. We want the units digit as large as possible (so that the tens and hundreds digits can be small). The largest it can be without carrying when we add is 5.

DPatrick 2015-03-21 19:55:26
That leaves 15 left, and to make the number smaller, we want as much as possible in the tens digits.

DPatrick 2015-03-21 19:55:31
So that gives the number 695.

DPatrick 2015-03-21 19:55:52
(To check, 695 + 864 = 1559 has digit sum of 20 too.)

DPatrick 2015-03-21 19:56:01
Just to check that our intuition was correct: what's the smallest $n$ with $s(n)=20$ and such that $n+864$ carries in the ones and hundreds digits?

xyuqing 2015-03-21 19:56:35
929

nosyarg 2015-03-21 19:56:35
929

MSTang 2015-03-21 19:56:35
929

zacchro 2015-03-21 19:56:35
929

tenniskidperson3 2015-03-21 19:56:35
929

kingsave3166 2015-03-21 19:56:35
929

DPatrick 2015-03-21 19:57:03
Right. 2 is the smallest tens digit we can have to avoid carrying (remember we'll get an extra +1 from the carry in the units digit). So 929 is the only such number.

Studiosa 2015-03-21 19:57:15
bigger than 695

MathDog0809 2015-03-21 19:57:15
bigger than 695

DPatrick 2015-03-21 19:57:29
Right. Our intuition for which case to look in was correct, and the answer is $\boxed{695}$.

DPatrick 2015-03-21 19:57:51
Well, we can't avoid it any longer...on to #9:

DPatrick 2015-03-21 19:57:55
9. Let $S$ be the set of all ordered triples of integers $(a_1,a_2,a_3)$ with $1\leq a_1,a_2,a_3\leq10$. Each ordered triple in $S$ generates a sequence according to the rule \[a_n=a_{n-1} \cdot |a_{n-2}-a_{n-3}|\] for $n\geq4$. Find the number of such sequences for which $a_n=0$ for some $n$.

AlcumusGuy 2015-03-21 19:58:38
We need $a_{n-2} = a_{n-3}$ at some point.

DPatrick 2015-03-21 19:59:13
Right: the value of $a_n$ is zero whenever $a_{n-2}=a_{n-3}$. That's the only way we can get our first zero: getting two consecutive terms equal.

nosyarg 2015-03-21 19:59:55
if 2 consecutive terms differ by one that will happen

raxu 2015-03-21 20:00:01
We can start listing the possibilities: a_1=a_2, a_2=a_3, ...

maverick8 2015-03-21 20:00:01
The difference between 2 consecutive terms can be 1

DPatrick 2015-03-21 20:00:25
Right. One possibility is we start out that way from the beginning -- we definitely hit zero quickly if $a_2$ is equal to either $a_1$ or $a_3$:

DPatrick 2015-03-21 20:00:30
\begin{align*}
&1,1,5,0,0\ldots\\
&6,6,2,0,0\ldots\\
&3,8,8,40,0,\ldots\\
&5,2,2,6,0,\ldots
\end{align*}

DPatrick 2015-03-21 20:00:55
But we can also get two equal terms if we have two consecutive terms that differ by 1.

DPatrick 2015-03-21 20:01:03
When $|a_{n-2}-a_{n-3}|=1$ that forces
\[a_n=a_{n-1}|a_{n-2}-a_{n-3}|=a_{n-1}\cdot1=a_{n-1}\]

DPatrick 2015-03-21 20:01:13
So we get two consecutive equal values, and that forces a zero value down the line.

DPatrick 2015-03-21 20:01:21
We can see some examples of this:

DPatrick 2015-03-21 20:01:24
\begin{align*}
&1,2,3,3,3,0,\ldots\\
&1,2,5,5,15,0,\ldots\\
&9,1,2,16,16,224,0\ldots\\
&5,3,2,4,4,8,0\ldots
\end{align*}

DPatrick 2015-03-21 20:01:47
So perhaps we have a conjecture:
There are no zeros if and only if $|a_2 - a_1| \ge 2$ and $|a_3 - a_2| \ge 2$.

rlz 2015-03-21 20:02:20
There are more sneaky cases

supercomputer 2015-03-21 20:02:20
7, 5, 1

mathtastic 2015-03-21 20:02:20
try $1,3,5$

mssmath 2015-03-21 20:02:27
1,3,1

brightknight 2015-03-21 20:02:27
531 doesnt work

DPatrick 2015-03-21 20:02:36
Yeah... wait a second. What about this example:\[1,3,1,2,4,4,8,0,\ldots\]That one fails!

Studiosa 2015-03-21 20:02:49
how do you find the sneaky cases systematically?

DPatrick 2015-03-21 20:03:06
That's a really good question. The way I found them is to try to prove my earlier "conjecture".

DPatrick 2015-03-21 20:03:22
I made the leap to try to show that if
\begin{align*}
|a_2-a_1|&\geq2\\
|a_3-a_2|&\geq2
\end{align*}
then $|a_n-a_{n-1}|\geq2$ for all $n$.

DPatrick 2015-03-21 20:03:57
...and if this happens, then we can never hit 0.

DPatrick 2015-03-21 20:04:07
If you were to try to prove this, how would you likely proceed?

MSTang 2015-03-21 20:04:25
induction

danusv 2015-03-21 20:04:25
Induction!

xyuqing 2015-03-21 20:04:25
Induction?

ws5188 2015-03-21 20:04:25
induction

chaoshadow37 2015-03-21 20:04:25
induction?

kingsave3166 2015-03-21 20:04:29
itd probably be induction

DPatrick 2015-03-21 20:04:33
We can try to prove this by induction. We've already got two base cases. So suppose it's true that $|a_k - a_{k-1}| \ge 2$ for all $k < n$ for some $n$.

DPatrick 2015-03-21 20:04:45
Then
\[
a_n = a_{n-1}|a_{n-2} - a_{n-3}| \ge 2a_{n-1}.
\]

DPatrick 2015-03-21 20:05:08
This means that $a_n - a_{n-1} \ge 2a_{n-1} - a_{n-1} = a_{n-1}$. But how do we know that that's greater than 2?

summitwei 2015-03-21 20:05:24
WE DONT

MSTang 2015-03-21 20:05:24
we don't

DPatrick 2015-03-21 20:05:32
Well, what if we go back one more step:
\[
a_{n-1} = a_{n-2} \cdot |a_{n-3} - a_{n-4}| \ge 2a_{n-2} \ge 2,
\]
since all the $a$'s are positive.

DPatrick 2015-03-21 20:05:42
So we're done...right?

AlcumusGuy 2015-03-21 20:06:20
no, you can't go back further because of base case

summitwei 2015-03-21 20:06:20
What if we can't go back a step?

mssmath 2015-03-21 20:06:20
For n sufficiently large

DPatrick 2015-03-21 20:06:44
That's the problem. What I did doesn't work for $n=4$ in particular, since then the $a_{n-4}$ that I tried to use in my last line doesn't exist!

DPatrick 2015-03-21 20:07:30
And if we back up a step, we see the root of the flaw. For $n=4$, we needed $a_3 \ge 2$ (that was the point of the last step).

DPatrick 2015-03-21 20:07:35
But what if $a_3 = 1$?

Studiosa 2015-03-21 20:07:57
conjecture doesn't work then

AlcumusGuy 2015-03-21 20:08:05
then you get the sneaky case

nosaj 2015-03-21 20:08:05
Then if the first 2 terms differ by 2 it goes to zero

rlz 2015-03-21 20:08:05
That's the sneaky case

DPatrick 2015-03-21 20:08:45
Exactly. My proof fails when $a_3 = 1$ and $|a_2 - a_1| = 2$, because we get $a_4 = 2$.

eyux 2015-03-21 20:08:49
so in all other cases, the conjecture holds?

csmath 2015-03-21 20:08:49
How do you know that it is the only exception?

DPatrick 2015-03-21 20:08:59
Because that's the only place where my proof fails!

DPatrick 2015-03-21 20:09:13
Indeed, when we fix that flaw, we have a theorem: there are no zeros if and only if all of the following inequalities hold:
\begin{align*}
|a_2-a_1|&\geq2,\\
|a_3-a_2|&\geq2,\\
|a_4-a_3|&\geq2.
\end{align*}

Sciolympian 2015-03-21 20:09:34
now the counting!

DPatrick 2015-03-21 20:09:40
Right. Now we need to count. Ugh.

DPatrick 2015-03-21 20:10:02
Let's try to count all the triples that satisfy all three inequalities above. Then, at the end, we have to remember to subtract this count from 1000 to get the number of triples that generate a sequence with a zero term.

mssmath 2015-03-21 20:10:30
The first two cases are easy then bash

DPatrick 2015-03-21 20:10:40
Right. Let's use casework on the value of $a_2$ and count how many triples $(a_1,a_2,a_3)$ satisfy the first two inequalities. Then we'll worry about the which might fail on the third. (Remember the third inequality is pretty hard to fail if the first two work.)

DPatrick 2015-03-21 20:10:52
If $a_2=1$, how many triples satisfy the first two inequalities?

BFYSharks 2015-03-21 20:11:24
64

mssmath 2015-03-21 20:11:24
64

summitwei 2015-03-21 20:11:24
64

TheStrangeCharm 2015-03-21 20:11:24
64

CornSaltButter 2015-03-21 20:11:31
8^2=64

DPatrick 2015-03-21 20:11:32
If $a_2=1$ then we need to have $a_1,a_3\geq3$. That gives $8\cdot8=64$ good triples.

DPatrick 2015-03-21 20:11:39
Symmetrically, if $a_2=10$ we need to have $a_1,a_3\leq8$. That gives $8 \times 8 = 64$ more good triples.

DPatrick 2015-03-21 20:12:28
And for each $2\leq a_2\leq9$, how many triples satisfy the first two inequalities?

xyuqing 2015-03-21 20:12:39
49

kingsave3166 2015-03-21 20:12:39
49

ohmcfifth 2015-03-21 20:12:39
49?

thequantumguy 2015-03-21 20:12:50
49

DPatrick 2015-03-21 20:12:53
If $2\leq a_2\leq9$ then we need $a_1$ and $a_3$ to avoid $\{a_2-1,a_2,a_2+1\}$. That gives us $7\cdot7 = 49$ total triples for each $a_2$.

DPatrick 2015-03-21 20:13:06
So summing these cases up, we've got $2 \cdot 64 + 8 \cdot 49 = 520$ triples satisfying the first two inequalities.

DPatrick 2015-03-21 20:13:14
But how many of these fail the third?

C-bass 2015-03-21 20:13:33
not very many

DPatrick 2015-03-21 20:13:36
Right. Recall that $a_4 = a_3 \cdot |a_2 - a_1|$, so $|a_4 - a_3| = a_3 \cdot \left(|a_2 - a_1| - 1\right)$.

DPatrick 2015-03-21 20:13:58
So $|a_4 - a_3| = 0$ only where $|a_2 - a_1| = 1$, but this isn't true from any of our 520 triples.

DPatrick 2015-03-21 20:14:01
How many, though, have $|a_4 - a_3| = 1$?

DPatrick 2015-03-21 20:14:08
For this, we need $|a_2 - a_1| = 2$ and $a_3 = 1$. How many are there?

Sciolympian 2015-03-21 20:14:45
14 triples

dantx5 2015-03-21 20:14:45
14

DPatrick 2015-03-21 20:15:00
There are two for each $3 \le a_2 \le 8$ (setting $a_1 = a_2 \pm 2$), but just one for $a_2 = 9 \text{ or } 10$ (setting $a_1 = a_2 - 2$). (Note none of our 520 triples have $a_2 = 1$ or $2$ because $|a_2 - a_3| \ge 2$.)

DPatrick 2015-03-21 20:15:22
So we have to exclude $2 \cdot 6 + 2 = 14$ triples from our count, leaving $520 - 14 = 506$ triples satisfying all three inequalities.

DPatrick 2015-03-21 20:15:31
Is that our final answer?

mathtastic 2015-03-21 20:15:44
take complement

csmath 2015-03-21 20:15:44
So the answer is 494

RedPhoenix 2015-03-21 20:15:44
answer is 494

csmath 2015-03-21 20:15:44
1000-506

Tommy2000 2015-03-21 20:15:47
no 1000-506=494 is the answer

DPatrick 2015-03-21 20:15:58
Remember, we counted the sequences that don't contain zero. We need the sequences that do contain 0. There are $10^3$ total sequences so there are $1000-506=\boxed{494}$ sequences that contain 0.

DPatrick 2015-03-21 20:16:34
That problem was pretty ugly. I think it was the hardest problem of all 15 on the contest. It's too easy to miscount and/or miss cases.

DPatrick 2015-03-21 20:16:58
We played with it a lot around the office trying to find a nicer solution. We did not succeed.

DPatrick 2015-03-21 20:17:19
I think after that problem, we should take a brief break. Let's resume in about 4 minutes at :21 past!

DPatrick 2015-03-21 20:21:10
OK, on to the double-digit problems!

DPatrick 2015-03-21 20:21:14
10. Let $f(x)$ be a third-degree polynomial with real coefficients satisfying \[ \lvert f(1)\rvert = \lvert f(2) \rvert = \lvert f(3)\rvert = \lvert f(5)\rvert = \lvert f(6)\rvert = \lvert f(7)\rvert = 12.\] Find $\lvert f(0)\rvert$.

mathtastic 2015-03-21 20:21:35
GRAPH IT

nosyarg 2015-03-21 20:21:35
draw a curve?

nosaj 2015-03-21 20:21:35
Draw the graph of the cubic polynomial.

DPatrick 2015-03-21 20:21:39
A good step here is to draw a generic graph of a cubic polynomial.

DPatrick 2015-03-21 20:21:43

DPatrick 2015-03-21 20:21:55
(Note that this cubic has leading coefficient positive. But because of the absolute values, we could just multiply by -1 if necessary to make it look like this.)

rlz 2015-03-21 20:22:04
It can be 12 in at most 3 places

mathtastic 2015-03-21 20:22:04
draw lines $y=\pm 12$

jam10307 2015-03-21 20:22:04
i drew 2 lines

DPatrick 2015-03-21 20:22:09
Yes, let's draw in two horizontal lines, to represent $y=12$ and $y=-12$:

DPatrick 2015-03-21 20:22:13

DPatrick 2015-03-21 20:22:31
This is a very generic picture, but how does this help us?

AKAL3 2015-03-21 20:22:51
1,5,6 are equal

rlz 2015-03-21 20:22:51
There's a - + + - - + pattern

summitwei 2015-03-21 20:22:51
3 of the roots are 12 and 3 are -12

dantx5 2015-03-21 20:22:51
determines order

Studiosa 2015-03-21 20:22:51
know the alternation of positives and negatives

FTW 2015-03-21 20:22:51
it shows us what sign each solution is

CornSaltButter 2015-03-21 20:22:51
So f(1)=f(5)=f(6)=-12 and f(2)=f(3)=f(7)=12

DPatrick 2015-03-21 20:22:55
It looks like that, going from left-to-right, we must have -12, 12, 12, -12, -12, 12.

DPatrick 2015-03-21 20:23:09
In fact this is the case. It actually requires some calculus-ness to prove this rigorously. But (I hope) it's clear enough from the diagram.

DPatrick 2015-03-21 20:23:15
And we don't actually have to prove it anyway: we can just assume it, and if we can find an $f$ that works, we're done.

DPatrick 2015-03-21 20:23:33
So let's assume, based on very good evidence, that
\[
f(2) = f(3) = f(7) = 12
\]
and
\[
f(1) = f(5) = f(6) = -12.
\]

akim99 2015-03-21 20:23:36
We want $|f(0)|$ so it won't matter if it's flipped or not

DPatrick 2015-03-21 20:23:49
Right: the top three as I wrote them might be -12 and the bottom three 12, but it doesn't matter.

DPatrick 2015-03-21 20:23:58
How do we proceed from here?

ryanyz10 2015-03-21 20:24:24
say g(x) = f(x) + 12

ninjataco 2015-03-21 20:24:24
f(x)+12=c(x-1)(x-5)(x-6) and f(x)-12=c(x-2)(x-3)(x-7)

Darn 2015-03-21 20:24:24
Create a new polynomial with those roots, then subtract/add

Ramanan369 2015-03-21 20:24:30
f(x)=a(x-2)(x-3)(x-7)+12

DPatrick 2015-03-21 20:24:48
Right. Consider the cubic $g(x) = f(x) - 12$. We know this has its roots at 2, 3, and 7.

DPatrick 2015-03-21 20:24:56
So $g(x) = c(x-2)(x-3)(x-7)$ for some constant $c$. Thus
\[
f(x) = c(x-2)(x-3)(x-7) + 12.
\]

DPatrick 2015-03-21 20:25:22
This is super-important: once you know all $n$ roots of a degree $n$ polynomial, then (up to a constant) you know the polynomial!

DPatrick 2015-03-21 20:25:44
And using the other three values, we similarly get
\[
f(x) = c(x-1)(x-5)(x-6) - 12.
\]

DPatrick 2015-03-21 20:26:01
It's the same $c$ in both equations, because it's the coefficient of the $x^3$ term of $f(x)$.

DPatrick 2015-03-21 20:26:15
Now what?

pieslinger 2015-03-21 20:26:39
plug in 0

Ramanan369 2015-03-21 20:26:39
plug in 0

MSTang 2015-03-21 20:26:39
Compare constant terms to get $c$

24iam24 2015-03-21 20:26:39
plug in 0 and solve for c

swe1 2015-03-21 20:26:39
equate constant terms

Sciolympian 2015-03-21 20:26:39
solve for c

DPatrick 2015-03-21 20:26:46
We can compute $f(0)$ using either expression:
\[
f(0) = c(-2)(-3)(-7) + 12 = -42c + 12,
\]
and
\[
f(0) = c(-1)(-5)(-6) - 12 = -30c - 12.
\]

dtxiong 2015-03-21 20:27:11
-30c-12=-42c-12

ninjataco 2015-03-21 20:27:11
c=2

BFYSharks 2015-03-21 20:27:11
c=2

william122 2015-03-21 20:27:11
c=2

DPatrick 2015-03-21 20:27:12
But of course, these have to be equal!
So $-42c+12 = -30c -12$.
This gives $24 = 12c$, so $c=2$.

nosaj 2015-03-21 20:27:35
so $c=2$ and $|f(0)|=\boxed{072}$, and we are done.

maverick8 2015-03-21 20:27:35
Answer is 72

xyuqing 2015-03-21 20:27:35
072

nosyarg 2015-03-21 20:27:35
072

DPatrick 2015-03-21 20:27:38
And thus $f(0) = -42(2) + 12 = -72$, so $|f(0)| = \boxed{072}$ is our answer.

DPatrick 2015-03-21 20:27:50
(As a check, you can verify that $2(x-2)(x-3)(x-7)+12 = 2(x-1)(x-5)(x-6)-12 = 2x^3 - 24x^2 + 82x - 72$ is the cubic that works.)

DPatrick 2015-03-21 20:28:10
On to #11:

DPatrick 2015-03-21 20:28:14
11. Triangle $ABC$ has positive integer side lengths with $AB = AC$. Let $I$ be the intersection of the bisectors of $\angle B$ and $\angle C$. Suppose $BI = 8$. Find the smallest possible perimeter of $\triangle ABC$.

DPatrick 2015-03-21 20:28:29
Of course, let's start with a diagram.

DPatrick 2015-03-21 20:28:33

DPatrick 2015-03-21 20:28:39
I've labeled $\angle IBC = x$ and the midpoint $M$ of the base $\overline{BC}$. Note that $I$ lies on $\overline{AM}$ because the triangle is isosceles.

DPatrick 2015-03-21 20:29:00
What's $BC$ in terms of $x$?

brightknight 2015-03-21 20:29:25
16cos(x)

ninjataco 2015-03-21 20:29:25
16cos x

ryanyz10 2015-03-21 20:29:25
16cosx

william122 2015-03-21 20:29:25
BC=16cosx

yimingz89 2015-03-21 20:29:25
$16\cos(x)$

C-bass 2015-03-21 20:29:25
16cosx

dyang 2015-03-21 20:29:25
16cosx

DPatrick 2015-03-21 20:29:30
We know that $\cos x = \frac{BM}{8}$ from right triangle $BMI$, so $BC = 2BM = 16 \cos x$.

crastybow 2015-03-21 20:30:00
since BC is an integer, cos x = k/16, with k an integer

DPatrick 2015-03-21 20:30:09
Exactly. Since $BC$ is a positive integer, we must have $\cos x = \frac{k}{16}$ for some $1 \le k \le 16$. (Then $BC = k$.)

DPatrick 2015-03-21 20:30:22
But there's more! $0^\circ < x < 45^\circ$, so what bounds does that put on $k$?

crastybow 2015-03-21 20:31:02
12 <= k < 16

wangth100 2015-03-21 20:31:02
$ k \ge 12 $ (since $ k $ is an integer)

DPatrick 2015-03-21 20:31:12
We must have $1 > \cos x > \frac{1}{\sqrt2} \approx 0.707$, so $k$ must be 12, 13, 14, or 15.

DPatrick 2015-03-21 20:31:27
Next: what is $AB$ is terms of $k$?

DPatrick 2015-03-21 20:31:56
There are a few steps to this...maybe getting $AB$ in terms of $x$ is a start.

BFYSharks 2015-03-21 20:32:12
k/(2cos2x)

DPatrick 2015-03-21 20:32:20
Using triangle $ABM$, we have $\cos 2x = \dfrac{BM}{AB}$, so $AB = \dfrac{BM}{\cos 2x} = \dfrac{k}{2\cos 2x}$.

xyuqing 2015-03-21 20:32:46
use cos (2x) = 2cos(x)^2-1

nosaj 2015-03-21 20:32:46
Use double angle formula

brainiac1 2015-03-21 20:32:46
and use the double angle formula

C-bass 2015-03-21 20:32:46
double angle identity?

brightknight 2015-03-21 20:32:46
cos2x=2cos^2-1

william122 2015-03-21 20:32:46
cos2x=cos^2x-1!

DPatrick 2015-03-21 20:32:53
And then $\cos 2x = 2\cos^2 x - 1$ by the double-angle formula, so
\[
\cos 2x = 2\left(\frac{k}{16}\right)^2 - 1 = \frac{k^2 - 128}{128}.
\]

DPatrick 2015-03-21 20:33:08
This gives $AB = \dfrac{k}{2\cos 2x} = \dfrac{64k}{k^2 - 128}$.

DPatrick 2015-03-21 20:33:17
For which $k$ in 12, 13, 14, 15 is this an integer?

Darn 2015-03-21 20:33:35
12

zachman99323 2015-03-21 20:33:35
only $12$ works, which is silly

RedPhoenix 2015-03-21 20:33:35
12

akim99 2015-03-21 20:33:35
12

bli1999 2015-03-21 20:33:35
12

AkshajK 2015-03-21 20:33:35
12

DPatrick 2015-03-21 20:33:40
$k=12$ works! We get $AB = \dfrac{64(12)}{16} = 48$.

DPatrick 2015-03-21 20:33:50
I'll save us time and tell you that none of the other $k$'s give an integer for $AB$.

DPatrick 2015-03-21 20:33:58
So not only does $k=12$ give the minimum perimeter -- it's actually the only triangle that works!

william122 2015-03-21 20:34:06
48*2+12=108

wangth100 2015-03-21 20:34:06
so the answer is $ \boxed{108} $.

DPatrick 2015-03-21 20:34:10
The perimeter is $48 + 48 + 12 = \boxed{108}$.

xyuqing 2015-03-21 20:34:33
Why would they ask minimum?

DPatrick 2015-03-21 20:34:54
Not sure why they phrased it that way. Their solution is essentially identical to what we just did.

DPatrick 2015-03-21 20:35:09
On to #12:

DPatrick 2015-03-21 20:35:12
12. Consider all 1000-element subsets of the set $\{1,2,3,\ldots,2015\}$. From each such subset choose the least element. The arithmetic mean of all of these least elements if $\frac pq$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.

AlcumusGuy 2015-03-21 20:35:44
Look at how many times each number is the minimum element.

nosaj 2015-03-21 20:35:44
Find the number of subsets with smallest element 1,2,3,...,1016.

summitwei 2015-03-21 20:35:44
Calculate # of subsets where min is 1, 2, 3, etc.

swe1 2015-03-21 20:35:44
2015C1000 subsets total

DPatrick 2015-03-21 20:35:52
Right. To start, there are $\dbinom{2015}{1000}$ ways to choose an 1000-element subset from a set of 2015 elements.

DPatrick 2015-03-21 20:35:56
Let's hope we don't have to compute that number.

DPatrick 2015-03-21 20:36:08
We can count how many of them there are with each minimum element.

DPatrick 2015-03-21 20:36:12
How many of them have 1 as the minimum element?

dyang 2015-03-21 20:36:30
2014 C 999

blueberry7 2015-03-21 20:36:30
(2014 C 999)

mjoshi 2015-03-21 20:36:30
2014C999

ninjataco 2015-03-21 20:36:30
2014C999

kingsave3166 2015-03-21 20:36:30
2014 choose 999

rocket13jg 2015-03-21 20:36:30
2014 choose 999

flyrain 2015-03-21 20:36:30
2014 choose 999

mssmath 2015-03-21 20:36:30
(2004 choose 999)

Epic777 2015-03-21 20:36:30
2014 choose 999

DPatrick 2015-03-21 20:36:35
We have to choose 999 more elements from $\{2,3,\ldots,2015\}$. So there are $\dbinom{2014}{999}$ of these sets.

DPatrick 2015-03-21 20:36:39
How many of them have 2 as the minimum element?

chaoshadow37 2015-03-21 20:36:56
2 as minimum there are 2013C999

ryanyz10 2015-03-21 20:36:56
2013C999

morninglight 2015-03-21 20:36:56
2013C999

dtxiong 2015-03-21 20:36:56
2013C999

amburger66 2015-03-21 20:36:56
(2013C999)

SHARKYBOY 2015-03-21 20:36:56
2013 choose 999

rlz 2015-03-21 20:36:56
$2013 \choose 999$

nosyarg 2015-03-21 20:36:56
2013C999

DPatrick 2015-03-21 20:37:01
We have to choose 999 more elements from $\{3,4,\ldots,2015\}$. So there are $\dbinom{2013}{999}$ of these sets.

akim99 2015-03-21 20:37:20
And so on all the way to $999 \choose 999$ for 1016

dtxiong 2015-03-21 20:37:20
pattern continues until 1016

DPatrick 2015-03-21 20:37:22
Similarly there are $\dbinom{2012}{999}$ subsets with 3 as the least element, $\dbinom{2011}{999}$ with 4 as the least element, and so on...
...down to just $\dbinom{999}{999} = 1$ with 1016 as the least element.

DPatrick 2015-03-21 20:37:44
In general, each least element $k$ gets counted $\dbinom{2015-k}{999}$ times, so the average is
\[
\frac{\dbinom{2014}{999}\cdot 1 + \dbinom{2013}{999} \cdot 2 + \dbinom{2012}{999} \cdot 3 + \cdots + \dbinom{999}{999} \cdot 1016}{\dbinom{2015}{1000}}.
\]

DPatrick 2015-03-21 20:37:55
How can we compute that numerator? (And, hopefully, what we get will cancel with a lot of the denominator!)

RedPhoenix 2015-03-21 20:38:25
We can use hockey-stick!

blueberry7 2015-03-21 20:38:25
hockey stick

mjoshi 2015-03-21 20:38:25
Hockey Stick

BFYSharks 2015-03-21 20:38:25
Hockey Stick

summitwei 2015-03-21 20:38:25
Use hockey stick repeatedly

AlcumusGuy 2015-03-21 20:38:25
Rewrite the sum in a clever way to exploit Hockey Stick.

brightknight 2015-03-21 20:38:25
Hockey-Stick Identity

eyux 2015-03-21 20:38:25
hockeystick!

willabc 2015-03-21 20:38:25
hockey stick

morninglight 2015-03-21 20:38:25
Hockey Stick!

ooooo1 2015-03-21 20:38:25
hockeystick

kingsave3166 2015-03-21 20:38:25
hockey stick identity

FTW 2015-03-21 20:38:25
hockey stick identity

Royalreter1 2015-03-21 20:38:25
Hockey Stick Theorem!

DPatrick 2015-03-21 20:38:40
It's the coefficients that makes it tricky, because if we didn't have the 1, 2, 3, etc., we could use the Hockey Stick Identity!

DPatrick 2015-03-21 20:38:45
\[
\dbinom{2014}{999} + \dbinom{2013}{999} + \dbinom{2012}{999} + \cdots + \dbinom{999}{999} = \dbinom{2015}{1000}.
\]

DPatrick 2015-03-21 20:38:56
(If you don't know this identity, look it up after class, or try to figure it out on your own.)

DPatrick 2015-03-21 20:39:05
But those coefficients are a problem...

DPatrick 2015-03-21 20:39:09
...or are they?

24iam24 2015-03-21 20:39:36
then you can repeatedly do it

Jz2435 2015-03-21 20:39:36
no they are not

C-bass 2015-03-21 20:39:36
no use it again

csmath 2015-03-21 20:39:36
WAIT apply repeatedly taking one out each time

Wave-Particle 2015-03-21 20:39:36
use it over and over

william122 2015-03-21 20:39:36
we can make it into 1016 seperate hockey sticks whose sums combine into a larger hockey stick

brainiac1 2015-03-21 20:39:36
just subtract and reuse the identity

acegikmoqsuwy2000 2015-03-21 20:39:36
Just subtract that from the numerator, and then use hockey stick again

tongzhao 2015-03-21 20:39:36
hockey stick over and over

Darn 2015-03-21 20:39:36
no just account for decrease of 1

DPatrick 2015-03-21 20:39:48
Right! We could certainly take one term from each and use the Hockey Stick Identity; that leaves us with:

DPatrick 2015-03-21 20:39:52
\[
\frac{\dbinom{2015}{1000} + \left(\dbinom{2014}{999}\cdot 0 + \dbinom{2013}{999} \cdot 1 + \dbinom{2012}{999} \cdot 2 + \cdots + \dbinom{999}{999} \cdot 1015\right)}{\dbinom{2015}{1000}}.
\]

ryanyz10 2015-03-21 20:40:08
keep doing that

ninjataco 2015-03-21 20:40:08
hockey stick again!

william122 2015-03-21 20:40:08
DO IT AGAIN!

DPatrick 2015-03-21 20:40:12
We peel one more term off of each (ignoring the first term that's 0), and that's another hockey stick:
\[
\dbinom{2013}{999} + \dbinom{2012}{999} + \cdots + \dbinom{999}{999} = \dbinom{2014}{2010}.
\]

DPatrick 2015-03-21 20:40:20
So now we have (dropping the terms that become 0):
\[
\frac{\dbinom{2015}{1000} + \dbinom{2014}{1000} + \left(\dbinom{2012}{999} \cdot 1 + \dbinom{2011}{999} \cdot 2 + \cdots + \dbinom{999}{999} \cdot 1014\right)}{\dbinom{2015}{1000}}.
\]

chaoshadow37 2015-03-21 20:40:36
Just keep using hockey stick

fluffyanimal 2015-03-21 20:40:36
moar

crastybow 2015-03-21 20:40:36
do it again

MathPro2816 2015-03-21 20:40:36
Keep doing that.

DPatrick 2015-03-21 20:40:38
And we just keep turning the crank: we peel off one binomial coefficient from each term inside the big parentheses, and apply the Hockey Stick Identity to sum them.

DPatrick 2015-03-21 20:40:45
Eventually, after applying all these hockey sticks, we end up with
\[
\frac{\dbinom{2015}{1000} + \dbinom{2014}{1000} + \dbinom{2013}{1000} + \cdots + \dbinom{1000}{1000}}{\dbinom{2015}{1000}}.
\]

summitwei 2015-03-21 20:40:59
And then you get one (gigantic) hockey stick

AlcumusGuy 2015-03-21 20:40:59
One more Hockey Stick!

BFYSharks 2015-03-21 20:40:59
One last time!

hwl0304 2015-03-21 20:40:59
Hockeystick AGAIN

fz0718 2015-03-21 20:40:59
again

DPatrick 2015-03-21 20:41:04
It's yet one last hockey stick! We end up with $\dfrac{\dbinom{2016}{1001}}{\dbinom{2015}{1000}}$.

chaoshadow37 2015-03-21 20:41:28
expand and cancel

flyrain 2015-03-21 20:41:28
and that's 2016/1001

Epic777 2015-03-21 20:41:28
2016/1001

mssmath 2015-03-21 20:41:28
2016/1001

brainiac1 2015-03-21 20:41:28
almost everything cancels

Darn 2015-03-21 20:41:28
so it's 2016/1001

Reverse_Osmosis 2015-03-21 20:41:28
now you simplify

mjoshi 2015-03-21 20:41:28
Now rewrite as factorials

DPatrick 2015-03-21 20:41:35
One safe way to simplify is to write it in terms of factorials: $\dfrac{\frac{2016!}{1001!1015!}}{\frac{2015!}{1000!1015!}}$.

DPatrick 2015-03-21 20:41:43
The 1005!'s cancel, and most of the other factorials cancel, and we're left with just $\dfrac{2016}{1001}$.

lucasxia01 2015-03-21 20:42:07
simplify to 288/143

blueberry7 2015-03-21 20:42:07
288/143

rocket13jg 2015-03-21 20:42:07
288/143

lolcreative883 2015-03-21 20:42:07
divide by 7?

DPatrick 2015-03-21 20:42:15
Canceling a factor of 7 leaves us with $\dfrac{288}{143}$ in lowest terms, so our answer is $288 + 143 = \boxed{431}$.

donot 2015-03-21 20:42:38
If you forgot Hockey Stick, is it even possible to solve this problem?

DPatrick 2015-03-21 20:43:06
There is a really clever trick to sum it in one swoop. Hint: we end up with $\dbinom{2016}{1001}$, so what's a counting argument for where that number comes from?

DPatrick 2015-03-21 20:43:14
I'll leave that for you to ponder.

DPatrick 2015-03-21 20:43:38
Although I like the problem, it is a pretty well-known problem. It was #2 on the 1981 IMO (but with general $n$ and $r$ instead of 2015 and 1000).

DPatrick 2015-03-21 20:43:56
Speaking of which, on to #13:

DPatrick 2015-03-21 20:44:02
13. With all angles measured in degrees, the product $\displaystyle\prod_{k=1}^{45} \csc^2(2k-1)^{\circ} = m^n$, where $m$ and $n$ are integers greater than 1. Find $m + n$.

brainiac1 2015-03-21 20:44:14
this is slightly conceptually similar to problem number 3.32 in the Aops Precalculus

nosaj 2015-03-21 20:44:16
Wasn't this in AoPS Precalc?

spartan168 2015-03-21 20:44:20
omg the one from the precalc book

DPatrick 2015-03-21 20:44:35
Yes, this is almost identical to Problem 3.32 from our Precalculus textbook.

DPatrick 2015-03-21 20:44:50
So naturally, the solution I'm going to lead us along is pretty much the same as the one from the book.

chezbgone 2015-03-21 20:45:06
rewrite as product of reciprocals of sines

DPatrick 2015-03-21 20:45:18
Yes, plus the product notation is a little hard to deal with, so let's write out what this really is:
\[
\frac{1}{(\sin^2 1)(\sin^2 3)(\sin^2 5)\cdots(\sin^2 87)(\sin^2 89)}.
\]
(I'm not going to write all the degree signs in this problem. Just remember that we're working in degrees.)

DPatrick 2015-03-21 20:45:37
There are some false trails you can wander down in this problem, but it's the type of problem that if you apply enough trig identities, you'll hopefully end up at the answer.

DPatrick 2015-03-21 20:45:46
We eventually want to try to get things to cancel out so that we're left with just an integer. One place to start is to try to get rid of the squares.

C-bass 2015-03-21 20:46:09
sinx = cos(90-x)

High 2015-03-21 20:46:09
sin1 = cos 89

chaoshadow37 2015-03-21 20:46:15
will changing sin 89 to cos 1 help (and sin97 to cos 3 and sin 85 to cos 5)?

DPatrick 2015-03-21 20:46:23
Let's do that: let's replace one sine in each $\sin^2 \theta$ term with $\cos(90-\theta)$:

DPatrick 2015-03-21 20:46:27
\[
\frac{1}{(\sin 1)(\cos 89)(\sin 3)(\cos 87)\cdots(\sin 87)(\cos 3)(\sin 89)(\cos 1)}.
\]

nosyarg 2015-03-21 20:46:54
double angles?

Sciolympian 2015-03-21 20:46:54
sin 89 cos 89!

mathtastic 2015-03-21 20:46:54
double angle that

mjoshi 2015-03-21 20:46:54
pair them up now

xyuqing 2015-03-21 20:46:54
Double angles?

AlcumusGuy 2015-03-21 20:46:54
now pair up the terms and use double-angle formula

DPatrick 2015-03-21 20:47:04
Good idea. The double-angle formula for sine is $\sin 2x = 2(\sin x)(\cos x)$. So $\dfrac{1}{(\sin x)(\cos x)} = \dfrac{2}{\sin 2x}$.

DPatrick 2015-03-21 20:47:14
That's helpful. We do this for all 45 pairs and we get that our expression is equal to
\[
\frac{2^{45}}{(\sin 2)(\sin 6)\cdots(\sin 174)(\sin 178)}.
\]

DPatrick 2015-03-21 20:47:27
The $2^{45}$ is probably a good sign (no pun intended) -- we need a power of an integer at the end.

crastybow 2015-03-21 20:47:44
sin(178) = sin(2)

MSTang 2015-03-21 20:47:44
sin 178 = sin 2, so we get squares again

chrislee777 2015-03-21 20:47:44
sin x = sin (180-x)

DPatrick 2015-03-21 20:47:48
Angles bigger than 90 seem unnecessary -- let's replace $\sin 178$ with $\sin 2$, $\sin 174$ with $\sin 6$, and so on.

DPatrick 2015-03-21 20:48:10
Note that the $\sin 90 = 1$ in the middle just goes away, and now our expression is
\[
\frac{2^{45}}{(\sin^2 2)(\sin^2 6)\cdots(\sin^2 82)(\sin^2 86)}.
\]
(Note there are 22 squares in the denominator now.)

DPatrick 2015-03-21 20:48:18
This is pretty similar to what we started with, but we've only got 22 terms now instead of 45, so this seems like progress.

Wave-Particle 2015-03-21 20:48:29
we can do it again!

tongzhao 2015-03-21 20:48:29
replace with cosine again?

blueberry7 2015-03-21 20:48:29
do it again

acegikmoqsuwy2000 2015-03-21 20:48:29
Do it again

blueberry7 2015-03-21 20:48:29
do the same thing

ryanyz10 2015-03-21 20:48:29
same thing again?

DPatrick 2015-03-21 20:48:39
Good idea, but the same "convert one of the sines to a cosine" trick we had before won't work in the same way as it did before, because $\sin 86$ converts to $\cos 4$, and there's no $\sin 4$ term to match it up to.

DPatrick 2015-03-21 20:49:01
But it still feels like we want to use the $\sin 2x = 2 \sin x \cos x$ identity somehow to create more cancellation.

DPatrick 2015-03-21 20:49:35
One idea is to just apply it to all the squares.

ninjataco 2015-03-21 20:49:41
sin x = sin 2x /(2cosx)

DPatrick 2015-03-21 20:49:47
Exactly. Let's try it as
\[
\dfrac{1}{\sin x} = \dfrac{2 \cos x}{\sin 2x},
\]
so that
\[
\dfrac{1}{\sin^2 x} = \dfrac{2^2 \cos^2 x}{\sin^2 2x}.
\]

DPatrick 2015-03-21 20:50:00
We apply this 22 times, so this makes our expression
\[
\frac{2^{89}(\cos^2 2)(\cos^2 6)\cdots(\cos^2 82)(\cos^2 86)}{(\sin^2 4)(\sin^2 12)\cdots(\sin^2 164)(\sin^2 172)}.
\]

DPatrick 2015-03-21 20:50:20
Did this help?

ryanyz10 2015-03-21 20:50:32
replace angles greater than 90

mjoshi 2015-03-21 20:50:32
change the 172 to 8 and so on

acegikmoqsuwy2000 2015-03-21 20:50:32
sin^2(172) = sin^2(8), etc

Sciolympian 2015-03-21 20:50:32
and convert the angles greater than 90 again

swe1 2015-03-21 20:50:32
get rid of sines bigger than 90

william122 2015-03-21 20:50:32
replace sins above 90

DPatrick 2015-03-21 20:50:41
Again, angles bigger than 90 are harder to work with, so let's make all the angles acute. Note that $\sin^2 172 = \sin^2 8$, $\sin^2 164 = \sin^2 16$, etc., so that we fill in all the missing multiples of 4 between 0 and 90.

DPatrick 2015-03-21 20:50:47
We now have:
\[
\frac{2^{89}(\cos^2 2)(\cos^2 6)\cdots(\cos^2 82)(\cos^2 86)}{(\sin^2 4)(\sin^2 8)\cdots(\sin^2 84)(\sin^2 88)}.
\]

HYP135peppers 2015-03-21 20:51:13
Now use sin(x)=cos(90-x) on numerator

bluephoenix 2015-03-21 20:51:13
They cancel because cos(90-x) = sinx

Studiosa 2015-03-21 20:51:13
things can cancel now if you do sin becomes cos thing

AlcumusGuy 2015-03-21 20:51:13
Now all the sin/cos's cancel!

crastybow 2015-03-21 20:51:13
hey look sin(88) = cos(2)

zxz 2015-03-21 20:51:13
it cancels!

crastybow 2015-03-21 20:51:13
so everything cancels

kingsave3166 2015-03-21 20:51:13
they match up!

chaoshadow37 2015-03-21 20:51:13
cos 86=sin4 so we can cancel

ooooo1 2015-03-21 20:51:13
sin88=cos2

jam10307 2015-03-21 20:51:13
they cancel

High 2015-03-21 20:51:13
cos 2 = sin 88, cos 6 = sin 84 etc. they all cancel

ninjataco 2015-03-21 20:51:13
rewrite the sines as cosines, or the cosines as sines, and they all cancel!

DPatrick 2015-03-21 20:51:21
We win: everything cancels now! $\cos^2 2 = \sin^2 88$, and $\cos^2 6 = \sin^2 84$, and so on, all the way down through to $\cos^2 86 = \sin^2 4$.

DPatrick 2015-03-21 20:51:30
So our expression is just $2^{89}$, and the final answer is $2 + 89 = \boxed{091}$.

DPatrick 2015-03-21 20:52:08
OK, on to #14:

DPatrick 2015-03-21 20:52:13
14. For each integer $n\ge 2$, let $A(n)$ be the area of the region in the coordinate plane defined by the inequalities $1\leq x < n$ and $0 \le y \le x \lfloor \sqrt{x} \rfloor$, where $\lfloor \sqrt{x} \rfloor$ is the greatest integer not exceeding $\sqrt{x}$. Find the number of values of $n$ with $2 \le n \le 1000$ for which $A(n)$ is an integer.

DPatrick 2015-03-21 20:52:37
Ick. This is a classic AIME ugly bookkeeping problem.

Sciolympian 2015-03-21 20:52:55
draw a graph first!

brainiac1 2015-03-21 20:52:55
graph it

xyuqing 2015-03-21 20:52:55
Draw a picture?

summitwei 2015-03-21 20:52:55
Graph it?

DPatrick 2015-03-21 20:52:59
Maybe sketching a graph of the region is a good place to start.

DPatrick 2015-03-21 20:53:03
What does the graph of $y = x\lfloor\sqrt{x}\rfloor$ look like?

MSTang 2015-03-21 20:53:33
Bunch of line segments with increasing slopes

zxz 2015-03-21 20:53:33
bunch of line segments

flyrain 2015-03-21 20:53:33
a graph with a bunch of gradually increasing steps

summitwei 2015-03-21 20:53:33
A bunch of lines, gradually increasing in slope

RedPhoenix 2015-03-21 20:53:33
several trapezoids

AlcumusGuy 2015-03-21 20:53:33
A collection of trapezoids

C-bass 2015-03-21 20:53:33
broken lines

DPatrick 2015-03-21 20:53:37
It's $y = x$ for $1 \le x < 4$.
It's $y = 2x$ for $4 \le x < 9$.
It's $y = 3x$ for $9 \le x < 16$.
And so on.

DPatrick 2015-03-21 20:53:44
So it's a bunch of line segments:

DPatrick 2015-03-21 20:53:47

DPatrick 2015-03-21 20:54:02
How does this help us compute $A(n)$?

raxu 2015-03-21 20:54:19
The area is a bunch of trapezoids.

kingsave3166 2015-03-21 20:54:19
trapezoid formula

Studiosa 2015-03-21 20:54:19
trapezoids

Tommy2000 2015-03-21 20:54:19
Find sum of area of trapezoids

Sciolympian 2015-03-21 20:54:19
we need the integer areas

zxz 2015-03-21 20:54:19
trapezoids

DPatrick 2015-03-21 20:54:30
Well...keep in mind we don't actually need to compute $A(n)$ -- we just need to know when it's an integer and when it's not.

DPatrick 2015-03-21 20:54:36
Let's zoom in a little bit in our picture:

DPatrick 2015-03-21 20:54:40

DPatrick 2015-03-21 20:55:13
Let's abbreviate $s(x) = \lfloor \sqrt{x} \rfloor$ so that it's easier to type. What's the area between $x = n$ and $x=n+1$ (for any integer $n \ge 1$)?

DPatrick 2015-03-21 20:55:41
Note that this region is a trapezoid of "height" 1 (in the $x$-direction) and parallel sides of length $ns(n)$ and $(n+1)s(n)$. For example, I've shaded the regions for $n=3$ (in pink) and $n=6$ (in blue) below:

DPatrick 2015-03-21 20:55:44

raxu 2015-03-21 20:56:27
(ns(n)+(n+1)s(n))/2

swe1 2015-03-21 20:56:27
s(n) * (n+1/2)

DPatrick 2015-03-21 20:56:37
Right, the area in one column is
\[
\frac12(ns(n)+(n+1)s(n)) = \frac12(2n+1)s(n).
\]

DPatrick 2015-03-21 20:57:02
Again, that's the area of the trapezoidal column between $x=n$ and $x=n+1$.

DPatrick 2015-03-21 20:57:06
What do we know about this quantity?

morninglight 2015-03-21 20:57:19
2n+1 is odd

MSTang 2015-03-21 20:57:22
Either int or int + 1/2

raxu 2015-03-21 20:57:27
Whether that area is integer or not depends on the parity of s(n), since (2n+1) is odd

vinayak-kumar 2015-03-21 20:57:27
Integer when s(n) is even, and a half integer otherwise

akim99 2015-03-21 20:57:27
To be an integer, s(n) is even

DPatrick 2015-03-21 20:57:36
$(2n+1)$ is always an odd integer, so this is an integer if $s(n)$ is even, and it's a half-integer if $s(n)$ is odd.

DPatrick 2015-03-21 20:58:01
Let's introduce some helpful terminology: let's say that $n$ is good if $A(n)$ is an integer, and bad if it's not. We're trying to count all the good integers.

DPatrick 2015-03-21 20:58:13
So now we have the formula
\[
A(n+1) = A(n) + \frac12(2n+1)s(n).
\]

DPatrick 2015-03-21 20:58:38
So the conclusion so far is: $A(n+1)$'s "goodness" stays the same as $A(n)$ if $s(n)$ is even, and flips (good to bad or vice versa) if $s(n)$ is odd.

summitwei 2015-03-21 20:58:50
Casework on the value of s(n)

DPatrick 2015-03-21 20:58:56
Right. We've made the key observation. From here on out, it's just bookkeeping.

DPatrick 2015-03-21 20:59:06
Let's start making a chart.

DPatrick 2015-03-21 20:59:18
For what values of $n$ is $s(n) = 1$?

akim99 2015-03-21 20:59:33
What's bookkepping?

william122 2015-03-21 20:59:33
what do you mean by BookKeeping?

DPatrick 2015-03-21 20:59:57
By "bookkeeping" I just mean carefully collecting a lot of data, and keeping track of it carefully to get our answer.

MSTang 2015-03-21 21:00:16
1, 2, 3

BFYSharks 2015-03-21 21:00:16
1-3

summitwei 2015-03-21 21:00:16
1,2,3

brainiac1 2015-03-21 21:00:16
1, 2, 3

C-bass 2015-03-21 21:00:16
1,2,3

jameswangisb 2015-03-21 21:00:16
1,2,3

mssmath 2015-03-21 21:00:16
1,2,3

nosyarg 2015-03-21 21:00:16
1,2,3

Th3Numb3rThr33 2015-03-21 21:00:16
1,2,3?

DPatrick 2015-03-21 21:00:24
Right. $s(n) = 1$ for $n=1,2,3$.

DPatrick 2015-03-21 21:00:41
Since $s(n)$ is odd, the goodness flips for every $n$. That is:
$A(2)$ is bad
$A(3)$ is good
$A(4)$ is bad.

DPatrick 2015-03-21 21:01:04
\[\begin{array}{c|c|c}
s(n) & n & \text{number of good } A(n) \\ \hline
1 & 1\ldots3 & 1
\end{array}\]

raxu 2015-03-21 21:01:14
A(5) to A(9) are all bad.

FractalMathHistory 2015-03-21 21:01:14
$A(5) \rightarrow A(9)$ is bad

DPatrick 2015-03-21 21:01:48
Right. For $n=4\ldots 8$, we have $s(n) =2$, so the "goodness" of the $A$'s doesn't change.

DPatrick 2015-03-21 21:01:59
Since $A(4)$ is bad, all of $A(5)\ldots A(9)$ are bad too.

DPatrick 2015-03-21 21:02:03
\[\begin{array}{c|c|c}
s(n) & n & \text{number of good } A(n) \\ \hline
1 & 1\ldots3 & 1 \\
2 & 4\ldots8 & 0
\end{array}\]

DPatrick 2015-03-21 21:02:47
It's a little confusing, since it's the parity of $s(n)$ that determines whether $A(n+1)$ "flips" or not. That +1 can be confusing, especially when we get to the end.

brainiac1 2015-03-21 21:03:01
A(10, 12, 14, 16) are all good

xyuqing 2015-03-21 21:03:01
10 good 11 bad 12 good ...

summitwei 2015-03-21 21:03:01
Then from 9 to 15 it alternates again

DPatrick 2015-03-21 21:03:12
$n = 9\ldots15$ satisfy $s(n) = 3$, and the $A'$s start flipping again.

DPatrick 2015-03-21 21:03:20
We're coming in to this block with a bad $A(9)$, so $A(10),A(12),A(14),A(16)$ are all good.

DPatrick 2015-03-21 21:03:24
\[\begin{array}{c|c|c}
s(n) & n & \text{number of good } A(n) \\ \hline
1 & 1\ldots3 & 1 \\
2 & 4\ldots8 & 0 \\
3 & 9\ldots15 & 4
\end{array}\]

DPatrick 2015-03-21 21:03:35
How about $s(n) = 4$?

RedPhoenix 2015-03-21 21:03:54
then 16-24 are all good

ryanyz10 2015-03-21 21:03:54
n = 16 - 24 are all good

dantx5 2015-03-21 21:03:54
all good

raxu 2015-03-21 21:03:54
And $A(17)\to A(25)$ are all good!

nosaj 2015-03-21 21:03:54
all good

Sciolympian 2015-03-21 21:03:54
all good

bli1999 2015-03-21 21:03:54
A(16)->A(25) are all good

mathbeida 2015-03-21 21:03:54
16 to 24 not changing pairity

DPatrick 2015-03-21 21:04:08
$n = 16\ldots24$, and since $A(16)$ is good, all the $A$'s are good in this block are good too:

DPatrick 2015-03-21 21:04:12
\[\begin{array}{c|c|c}
s(n) & n & \text{number of good } A(n) \\ \hline
1 & 1\ldots3 & 1 \\
2 & 4\ldots8 & 0 \\
3 & 9\ldots15 & 4 \\
4 & 16\ldots24 & 9
\end{array}\]

DPatrick 2015-03-21 21:04:23
So now we see the pattern.
In an odd $s(n)$ block, every other $A(n)$ is good. If we enter on a good $A(n)$, then we leave on a bad $A(n)$, and vice versa.
In an even block, all the $A(n)$ are either good or bad.

DPatrick 2015-03-21 21:04:38
More specifically, there's a cycle of 4:
If $n \equiv 1 \pmod{4}$, then we start on good, so half (rounded DOWN) are good, and we leave on bad.
If $n \equiv 2 \pmod{4}$, then we're all bad
If $n \equiv 3 \pmod{4}$, then we start on bad, so half (rounded UP) are good, and we leave on good.
If $n \equiv 0 \pmod{4}$, then all are good.

DPatrick 2015-03-21 21:05:07
So now it's just a matter of extending our chart all the way up to $n=1000$. Since $s(1000) = 31$ we'll need 31 rows unless we see a more clever pattern.

akim99 2015-03-21 21:05:31
Squares!

tongzhao 2015-03-21 21:05:31
squares?

nosyarg 2015-03-21 21:05:31
the squares?

xyuqing 2015-03-21 21:05:31
Wait, 1^2=1, 2^2=4, 3^2=9?

BFYSharks 2015-03-21 21:05:31
Perfect squares?

DPatrick 2015-03-21 21:05:37
Good guess, but sadly no.

DPatrick 2015-03-21 21:05:41
Let's at least do the next 4 rows. I'm going to add the method of counting to our chart:

DPatrick 2015-03-21 21:05:55
\[\begin{array}{c|c|c|c}
s(n) & n & \text{count} & \text{number of good } A(n) \\ \hline
1 & 1\ldots3 & \text{half rounded DOWN} & 1 \\
2 & 4\ldots8 & \text{none} & 0 \\
3 & 9\ldots15 & \text{half rounded UP} & 4 \\
4 & 16\ldots24 & \text{all} & 9 \\
5 & 25\ldots35 & \text{half rounded DOWN} & 5 \\
6 & 36\ldots48 & \text{none} & 0 \\
7 & 49\ldots63 & \text{half rounded UP} & 8 \\
8 & 64\ldots80 & \text{all} & 17
\end{array}\]

DPatrick 2015-03-21 21:06:06
Notice anything?

Eugenis 2015-03-21 21:06:28
It looks like we have some kind of recursion

chezbgone 2015-03-21 21:06:28
pattern of cycle 4

Tommy2000 2015-03-21 21:06:28
increases by 4 everytime

AlcumusGuy 2015-03-21 21:06:28
multiples of 4

bli1999 2015-03-21 21:06:28
Adds 8 to each term when it cycles through

DPatrick 2015-03-21 21:06:31
Each block of $s(n)$ counts exactly 4 more (for the ``half'' blocks) or 8 more (for the ``all'' block) than $s(n+4)$. Is that a coincidence?

temp8909 2015-03-21 21:06:49
no

mathwizard888 2015-03-21 21:06:49
no

dyang 2015-03-21 21:06:49
nope

csmath 2015-03-21 21:06:49
No!

DPatrick 2015-03-21 21:06:51
It's not, because
\begin{align*}
(n+1)^2 - n^2 &= 2n+1, \\
(n+5)^2 - (n+4)^2 &= 2n + 9,
\end{align*}
so there are always 8 more terms in the $s(n+4)$ block than in the $s(n)$ block.

DPatrick 2015-03-21 21:07:06
That simplifies things quite a bit. Each set of 4 blocks counts 16 more than the block before.

summitwei 2015-03-21 21:07:24
Arithmetic series

ryanyz10 2015-03-21 21:07:24
arithmetic sequence

csmath 2015-03-21 21:07:24
So we can just sum these as arithmetic series?

DPatrick 2015-03-21 21:07:33
Indeed.
$s(1)\ldots s(4)$ counts $1+4+9 = 14$.
$s(5)\ldots s(8)$ counts $14+16 = 30$.
etc.
$s(25)\ldots s(28)$ counts $14+6(16) = 110$.

DPatrick 2015-03-21 21:07:39
So $s(1)$ through $s(28)$ have the sum of the 7-term arithmetic series
\[
14 + 30 + 46 + \cdots + 110 = \frac72 \cdot 124 = 434.
\]

AlcumusGuy 2015-03-21 21:07:56
We have to be careful about the upper end since $n \le 1000$.

DPatrick 2015-03-21 21:08:00
Absolutely.

DPatrick 2015-03-21 21:08:11
We'll have to do the end by hand.

Th3Numb3rThr33 2015-03-21 21:08:19
Then just add s(29), s(30), s(31)?

DPatrick 2015-03-21 21:08:23
$s(29)$ runs from $29^2 = 841$ to $30^2-1 = 899$, and we take half rounded up.

DPatrick 2015-03-21 21:08:34
That's another 29 good ones, for a total so far of $434 + 29 = 463$.

DPatrick 2015-03-21 21:08:48
$s(30)$ runs from $30^2 = 900$ to $31^2-1 = 960$, but we don't take any of them.

DPatrick 2015-03-21 21:09:00
And finally, $s(31)$ runs from 961 up to 999 (since $s(n) = 999$ determines $A(1000)$). That's 39 terms. We take half rounded up, so that's another 20.

DPatrick 2015-03-21 21:09:14
This gives us a final count of $463 + 20 = \boxed{483}$.

DPatrick 2015-03-21 21:09:38
Very, very careful bookkeeping was the key to solving this problem.

akim99 2015-03-21 21:09:43
HEre we go #15

spartan168 2015-03-21 21:09:43
And now for the grand finale

DPatrick 2015-03-21 21:09:54
#15 is actually a lot shorter compared to the one we just did:

DPatrick 2015-03-21 21:09:57
15. A block of wood has the shape of a right circular cylinder with radius 6 and height 8, and its entire surface has been painted blue. Points $A$ and $B$ are chosen on the edge of one of the circular faces of the cylinder so that $\overset{\frown}{AB}$ on that face measures $120^{\circ}$. The block is then sliced in half along the plane that passes through point $A$, point $B$, and the center of the cylinder, revealing a flat, unpainted face on each half. The area of one of these unpainted faces if $a\pi + b\sqrt{c}$, where $a, b,$ and $c$ are integers and $c$ is not divisible by the square of any prime. Find $a + b + c$.

DPatrick 2015-03-21 21:10:05

DPatrick 2015-03-21 21:10:12
Everyone should thank AoPS community members Royalreter1 and chezbgone2 for posting this excellent diagram!

DPatrick 2015-03-21 21:10:29
My only contribution was to color it blue.

Royalreter1 2015-03-21 21:10:36
Wait chezbgone2 did everything, I just pasted what he told me to

DPatrick 2015-03-21 21:10:53
Most 3-D geometry problems are 2-D geometry problems in disguise, and this problem is no exception.

DPatrick 2015-03-21 21:11:01
If we smush our flat unpainted face down onto the base, what does it look like?

Tuxianeer 2015-03-21 21:11:24
a circle with two parallel chords

nosaj 2015-03-21 21:11:24
Circle with 2 120 degree chords cut off.

C-bass 2015-03-21 21:11:24
A rectangle with curved sides!

DPatrick 2015-03-21 21:11:30
It's the region of the circle that lies between two 120-degree arcs:

DPatrick 2015-03-21 21:11:39

DPatrick 2015-03-21 21:11:53
So, what's the area of the gray region that results when the white region is projected onto the base of the cylinder?

DPatrick 2015-03-21 21:12:06
How can we chop it up to find its area?

cumo99 2015-03-21 21:12:35
draw diagonals

High 2015-03-21 21:12:35
Connect A and B to its center

Darn 2015-03-21 21:12:35
Connect endpoints of arcs to center

RedPhoenix 2015-03-21 21:12:35
draw lines to the center?

Tommy2000 2015-03-21 21:12:35
draw diagonals

dantx5 2015-03-21 21:12:35
draw 4 radii to form triangles and sectors

morninglight 2015-03-21 21:12:35
4 30-60-90s and 2 equilateral triangles

ninjataco 2015-03-21 21:12:35
draw radii to A and B

sophiazhi 2015-03-21 21:12:35
connect center to A and B

brightknight 2015-03-21 21:12:35
Connect the center to A and B

DPatrick 2015-03-21 21:12:50
It's 2 copies of triangle $OAB$ (where $O$ is the center of the circle), plus 2 60-degree wedges of the circle, as shown below:

DPatrick 2015-03-21 21:12:53

DPatrick 2015-03-21 21:13:11
What's the area of $OAB$?

xyuqing 2015-03-21 21:13:38
9sqrt3

Lee541 2015-03-21 21:13:38
9sqrt3

dantx5 2015-03-21 21:13:38
9sqrt3

SHARKYBOY 2015-03-21 21:13:38
9sqrt3

summitwei 2015-03-21 21:13:38
9sqrt3

theoldaops 2015-03-21 21:13:38
9root3

swirlykick 2015-03-21 21:13:38
9sqrt3

DPatrick 2015-03-21 21:13:42
$OAB$ has height 3 and base $6\sqrt3$, so its area is $9\sqrt3$.

DPatrick 2015-03-21 21:13:56
And what's the area of one of those circular-wedge pieces?

bli1999 2015-03-21 21:14:16
6pi

brainiac1 2015-03-21 21:14:16
6pi

Sciolympian 2015-03-21 21:14:16
$6\pi$

DPatrick 2015-03-21 21:14:21
Each wedge is 1/6 of the circle, so each wedge has area $6\pi$.

DPatrick 2015-03-21 21:14:28
Thus the gray area is $2(6\pi + 9\sqrt3) = 12\pi + 18\sqrt3$.

DPatrick 2015-03-21 21:14:34
Now what? How does this flattened grey area relate to the white area that we really want?

xyuqing 2015-03-21 21:14:59
stretch it

va2010 2015-03-21 21:14:59
multiply by 5/3

nosaj 2015-03-21 21:14:59
stretch factor of 5/3

Tuxianeer 2015-03-21 21:14:59
it's $\dfrac{3}{5}$ of the white area

pieslinger 2015-03-21 21:14:59
it's a projection

csmath 2015-03-21 21:14:59
It's dilated by a factor

raxu 2015-03-21 21:14:59
The white one is 5/3 the grey one.

Th3Numb3rThr33 2015-03-21 21:14:59
the white is a stretched version of the gray

DivideBy0 2015-03-21 21:14:59
its just a rescaling

DPatrick 2015-03-21 21:15:08
It's the same basic shape, but stretched in one direction: the "horizontal" direction as we look at it above.

DPatrick 2015-03-21 21:15:19
Right now, the gray region has width 6, but what width does it have when we stretch it back to its original shape?

Tuxianeer 2015-03-21 21:15:38
$10$

akim99 2015-03-21 21:15:38
10

chaoshadow37 2015-03-21 21:15:38
10

temp8909 2015-03-21 21:15:38
10

DPatrick 2015-03-21 21:15:43
Right. It's "width" is the hypotenuse of a triangle with legs 6 (the grey width) and 8 (the height of the cylinder), as shown below:

DPatrick 2015-03-21 21:15:46

DPatrick 2015-03-21 21:15:57
So the width of the white region is 10 (the hypotenuse of the 6-8-10 right triangle shown above).

DPatrick 2015-03-21 21:16:08
Thus the gray region gets stretched by a factor of $\frac{10}{6} = \frac53$ to form the white region.

DPatrick 2015-03-21 21:16:20
Since this stretching is only along one dimension, it multiplies the area by that same factor.

nosaj 2015-03-21 21:16:37
\[\tfrac{5}{3}(12\pi + 18\sqrt{3})=20\pi+30\sqrt{3}\]

DPatrick 2015-03-21 21:16:39
So the white region's area is $\frac53(12\pi + 18\sqrt3) = 20\pi + 30\sqrt3$.

Darn 2015-03-21 21:16:57
So our answer is 20+30+3=53

akim99 2015-03-21 21:16:57
20+30+3 = 53

Th3Numb3rThr33 2015-03-21 21:16:57
20 + 30 + 3 = 53

DPatrick 2015-03-21 21:16:58
This is in the format requested by the problem, so the final answer is $20 + 30 + 3 = \boxed{053}$.

csmath 2015-03-21 21:17:13
That was quite a straightforward 15.

spartan168 2015-03-21 21:17:13
that was fast

Darn 2015-03-21 21:17:13
wait that was easy for a #15

DPatrick 2015-03-21 21:17:33
It was fairly easy for a #15, if you just remember the usual advice: most 3D geometry problems are just 2D geometry problems in disguise!

DPatrick 2015-03-21 21:17:42
And that's it for the Math Jam! Thanks for coming.

DPatrick 2015-03-21 21:17:49
Join us again in just 6 days, on Friday, March 27, for the AIME II Math Jam!

2015 AIME I Math Jam

Facilitator: Dave Patrick