https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Shaddoll&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T08:59:37ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=783272016 USAMO Problems/Problem 22016-04-28T23:08:02Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Prove that for any positive integer <math>k,</math><br />
<cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath><br />
is an integer.<br />
==Solution==<br />
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math> for integer <math>x</math>. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it <math>N</math>.<br />
<br />
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function(we take out groups of <math>m</math> which are just permutations of numbers <math>1</math> to <math>m</math> until there are less than <math>m</math> left, then we have <math>m</math> distinct values, which the minimum sum is attained at <math>0</math> to <math>k-1</math>). Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=1|num-a=3}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=783262016 USAMO Problems/Problem 22016-04-28T23:07:29Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Prove that for any positive integer <math>k,</math><br />
<cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath><br />
is an integer.<br />
==Solution==<br />
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math> for integer <math>x</math>. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it <math>N</math>.<br />
<br />
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function(we take out groups of <math>m</math> until there are less than <math>m</math> left, then we have <math>m</math> distinct values, which the minimum sum is attained at <math>0</math> to <math>k-1</math>). Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=1|num-a=3}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=783252016 USAMO Problems/Problem 22016-04-28T23:07:00Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Prove that for any positive integer <math>k,</math><br />
<cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath><br />
is an integer.<br />
==Solution==<br />
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math> for integer <math>x</math>. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it <math>N</math>.<br />
<br />
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function(we take out groups of <math>m</math> until there are less than <math>m</math> left, then we have <math>m</math> distinct values, which the minimum is attained at <math>0</math> to <math>m-1</math>). Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=1|num-a=3}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=783242016 USAMO Problems/Problem 22016-04-28T23:05:06Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Prove that for any positive integer <math>k,</math><br />
<cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath><br />
is an integer.<br />
==Solution==<br />
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math> for integer <math>x</math>. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it <math>N</math>.<br />
<br />
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function. Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=1|num-a=3}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=783232016 USAMO Problems/Problem 22016-04-28T23:04:17Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Prove that for any positive integer <math>k,</math><br />
<cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath><br />
is an integer.<br />
==Solution==<br />
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math>. Note that the expression is clearly rational, call it <math>N</math>.<br />
<br />
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function. Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=1|num-a=3}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=783222016 USAMO Problems/Problem 22016-04-28T23:03:59Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Prove that for any positive integer <math>k,</math><br />
<cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath><br />
is an integer.<br />
==Solution==<br />
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math>. Note that the expression is clearly rational, call it <math>N</math>.<br />
<br />
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function. Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.<br />
{{solution}}<br />
<br />
{{MAA Notice}}<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=1|num-a=3}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_6&diff=783212016 USAMO Problems/Problem 62016-04-28T23:00:24Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>==Problem==<br />
Integers <math>n</math> and <math>k</math> are given, with <math>n\ge k\ge 2.</math> You play the following game against an evil wizard.<br />
<br />
The wizard has <math>2n</math> cards; for each <math>i = 1, ..., n,</math> there are two cards labeled <math>i.</math> Initially, the wizard places all cards face down in a row, in unknown order.<br />
<br />
You may repeatedly make moves of the following form: you point to any <math>k</math> of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the <math>k</math> chosen cards and turns them back face-down. Then, it is your turn again.<br />
<br />
We say this game is <math>\textit{winnable}</math> if there exist some positive integer <math>m</math> and some strategy that is guaranteed to win in at most <math>m</math> moves, no matter how the wizard responds.<br />
<br />
For which values of <math>n</math> and <math>k</math> is the game winnable?<br />
==Solution==<br />
<br />
We first prove that the game is winnable whenever <math>n > k</math> by demonstrating a winning strategy in this case.<br />
<br />
On the <math>i</math>th move, choose the <math>k</math> cards in positions <math>i</math> through <math>i+k-1.</math> Assuming that you do not win on any earlier move, repeat this for <math>1\le i \le 2n-k+1.</math><br />
<br />
Assume that you did not win on any of the first <math>2n-k+1</math> moves, as described above. Let <math>j</math> be an integer such that <math>1\le j\le 2n-k.</math> On the <math>j</math>th move, the wizard revealed the cards in positions <math>j</math> through <math>j+k-1,</math> so you know the labels of all of these cards (just not necessarily in the right order). Then, on the <math>(j+1)</math>th move, the wizard revealed the cards in positions <math>j+1</math> through <math>j+k,</math> which means that you get to see all of the cards that were moved to positions <math>j+1</math> through <math>j+k.</math> This means that you can uniquely determine the label on card <math>j,</math> since you knew all of the labels from <math>j</math> through <math>j+k-1,</math> and the card in position <math>j</math> could not have moved anywhere else since your last move.<br />
<br />
It follows that, after the sequence of <math>2n-k+1</math> moves described above, you know the labels on the first <math>2n-k</math> cards. Since <math>n > k,</math> we have <math>2n-k \ge n+1,</math> so there must be a pair of cards with matching labels in this group of <math>2n-k</math> cards, by the Pigeonhole Principle. On your next move, you can pick a group of <math>k</math> cards that includes that pair of matching cards, and you win.<br />
<br />
We have created a strategy that is guaranteed to win in at most <math>m = 2n-k+2</math> moves. Thus, the game is winnable for all <math>n > k.</math><br />
<br />
We now prove that the game is not winnable if <math>n=k.</math> We will say that the game is in a state <math>S</math> if your knowledge about the card labels is of the following form:<br />
<br />
There exists a group of <math>n</math> cards for which you know that those <math>n</math> cards have all of the labels <math>1, 2, ..., n</math> (i.e. you know that they have all distinct labels) in some order, but you know nothing about which of those <math>n</math> cards have which labels. (Call this group of cards Group <math>A.</math>)<br />
<br />
Suppose that the game is in such a state <math>S.</math> We will now show that, regardless of your next move, you cannot guarantee victory or an escape from state <math>S.</math><br />
<br />
Clearly, the <math>n</math> cards that are not in Group <math>A</math> must also have all of the labels <math>1, 2, ..., n.</math> (You might know something about which cards have which labels, or you might not.) Call this other collection of cards Group <math>B.</math><br />
<br />
If, on the next move, you pick all of the cards from Group <math>A</math> or all of the cards from Group <math>B,</math> then you clearly will not get a matching pair. The wizard will then arbitrarily permute those cards. Thus, for those <math>n</math> chosen cards, you know their labels are all distinct, but you know nothing about which cards have which labels. Thus, you are back in state <math>S.</math><br />
<br />
Now, suppose you pick <math>x</math> cards from Group <math>A</math> and <math>n-x</math> cards from Group <math>B,</math> where <math>x</math> is an integer and <math>1\le x\le n-1.</math> Then, the cards chosen from Group <math>B</math> will form a set of labels <math>P\subset Z_n,</math> where <math>Z_n = \left\{ {1, 2, ..., n} \right\}</math> and <math>|P| = n-x.</math> However, you know nothing about which cards in Group <math>A</math> have which labels. Thus, there is no way for you to prevent the <math>x</math> cards from Group <math>A</math> to form the exact set of labels <math>Q = Z_n\setminus P.</math> In such a case, there will be no matching cards, so you will not win. Furthermore, the wizard will then arbitrarily permute these <math>n</math> cards, so you will know that they have all <math>n</math> distinct labels, but you will know nothing about which cards have which labels. Therefore, you are again in state <math>S.</math><br />
<br />
We have covered all cases, so it follows that, once you enter state <math>S,</math> you cannot guarantee escape from state <math>S</math> or victory.<br />
<br />
Now, look at the very first move you make. Obviously, you cannot guarantee victory on the first move, as you know nothing about which cards have which labels. Assuming that you do not win on the first move, the <math>n</math> cards you chose have all distinct labels. The wizard then permutes the <math>n</math> cards you chose, so you now know that those <math>n</math> cards have all distinct labels but know nothing about which cards have which labels. Therefore, if you do not win on your first move, then the game enters state <math>S,</math> and we have already proven that you cannot guarantee victory from this point.<br />
<br />
We therefore conclude that the game is not winnable if <math>n=k.</math> We proved earlier that the game is winnable if <math>n>k,</math> so the game is winnable if and only if <math>n>k\ge 2.</math><br />
==Solution 2==<br />
We claim that the game is winnable if and only if <math>n>k</math>. Suppose after the first step, the cards <math>1</math> to <math>n</math> are shuffled around. Notice that we have <math>n</math> cards that we don't know the position of (which are all cards from <math>1</math> to <math>n</math>). Now, suppose we pick <math>p</math> known cards. Note that the <math>p</math> cards are all different(since the known cards are the cards from <math>1</math> to <math>n</math>), and there is still a possibility that the other cards from the unknown cards complement and cause <math>1</math> to <math>n</math>. Therefore, we are in the same state as before, and the game is unwinnable.<br />
<br />
Now, suppose <math>n>k</math>. Denote the ith card counting from the left. We pick cards <math>1</math> to <math>k</math>, keeping track of the set of values of the cards. Then, we pick cards <math>2</math> to <math>k+1</math>, adding the value of the <math>k+1</math>th card into the set of value of cards. We keep doing this, until we pick cards <math>2n-k</math> to <math>2n-1</math>, at which point we know the exact number on the <math>2n</math>th card. Now, we go back to <math>1</math> through <math>k</math>, and repeat this process, until we reveal the <math>2n-1</math>th card(unless we win during the process). This process terminates only when there are less or equal to <math>k</math> cards that we don't know the exact numbers on or if we somehow win, clearly, as otherwise we're still revealing new information by picking cards from <math>1</math> through <math>k</math>. Note that we now know the exact values on <math>2n-k</math> of the cards. By the pigeon hole principle, since <math>k<n</math>, <math>2</math> of them are the same, and we pick those <math>2</math> cards and <math>k-2</math> other random cards and we win. <br />
<br />
{{MAA Notice}}<br />
<br />
==See also==<br />
{{USAMO newbox|year=2016|num-b=5|aftertext=|after=Last Problem}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_4&diff=782412016 USAMO Problems/Problem 42016-04-25T03:25:39Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>== Problem ==<br />
Find all functions <math>f:\mathbb{R}\rightarrow \mathbb{R}</math> such that for all real numbers <math>x</math> and <math>y</math>, <cmath>(f(x)+xy)\cdot f(x-3y)+(f(y)+xy)\cdot f(3x-y)=(f(x+y))^2.</cmath><br />
<br />
== Solution ==<br />
<br />
'''Step 1:''' Set <math>x = y = 0</math> to obtain <math>f(0) = 0.</math><br />
<br />
'''Step 2:''' Set <math>x = 0</math> to obtain <math>f(y)f(-y) = f(y)^2.</math><br />
<br />
<math>\indent</math> In particular, if <math>f(y) \ne 0</math> then <math>f(y) = f(-y).</math><br />
<br />
<math>\indent</math> In addition, replacing <math>y \to -t</math>, it follows that <math>f(t) = 0 \implies f(-t) = 0</math> for all <math>t \in \mathbb{R}.</math><br />
<br />
'''Step 3:''' Set <math>x = 3y</math> to obtain <math>\left[f(y) + 3y^2\right]f(8y) = f(4y)^2.</math><br />
<br />
<math>\indent</math> In particular, replacing <math>y \to t/8</math>, it follows that <math>f(t) = 0 \implies f(t/2) = 0</math> for all <math>t \in \mathbb{R}.</math><br />
<br />
'''Step 4:''' Set <math>y = -x</math> to obtain <math>f(4x)\left[f(x) + f(-x) - 2x^2\right] = 0.</math><br />
<br />
<math>\indent</math> In particular, if <math>f(x) \ne 0</math>, then <math>f(4x) \ne 0</math> by the observation from Step 3, because <math>f(4x) = 0 \implies f(2x) = 0 \implies f(x) = 0.</math> Hence, the above equation implies that <math>2x^2 = f(x) + f(-x) = 2f(x)</math>, where the last step follows from the first observation from Step 2.<br />
<br />
<math>\indent</math> Therefore, either <math>f(x) = 0</math> or <math>f(x) = x^2</math> for each <math>x.</math><br />
<br />
<math>\indent</math> Looking back on the equation from Step 3, it follows that <math>f(y) + 3y^2 \ne 0</math> for any nonzero <math>y.</math> Therefore, replacing <math>y \to t/4</math> in this equation, it follows that <math>f(t) = 0 \implies f(2t) = 0.</math><br />
<br />
'''Step 5:''' If <math>f(a) = f(b) = 0</math>, then <math>f(b - a) = 0.</math><br />
<br />
<math>\indent</math> This follows by choosing <math>x, y</math> such that <math>x - 3y = a</math> and <math>3x - y = b.</math> Then <math>x + y = \tfrac{b - a}{2}</math>, so plugging <math>x, y</math> into the given equation, we deduce that <math>f\left(\tfrac{b - a}{2}\right) = 0.</math> Therefore, by the third observation from Step 4, we obtain <math>f(b - a) = 0</math>, as desired.<br />
<br />
'''Step 6:''' If <math>f \not\equiv 0</math>, then <math>f(t) = 0 \implies t = 0.</math><br />
<br />
<math>\indent</math> Suppose by way of contradiction that there exists an nonzero <math>t</math> with <math>f(t) = 0.</math> Choose <math>x, y</math> such that <math>f(x) \ne 0</math> and <math>x + y = t.</math> The following three facts are crucial:<br />
<br />
<math>\indent</math> 1. <math>f(y) \ne 0.</math> This is because <math>(x + y) - y = x</math>, so by Step 5, <math>f(y) = 0 \implies f(x) = 0</math>, impossible.<br />
<br />
<math>\indent</math> 2. <math>f(x - 3y) \ne 0.</math> This is because <math>(x + y) - (x - 3y) = 4y</math>, so by Step 5 and the observation from Step 3, <math>f(x - 3y) = 0 \implies f(4y) = 0 \implies f(2y) = 0 \implies f(y) = 0</math>, impossible.<br />
<br />
<math>\indent</math> 3. <math>f(3x - y) \ne 0.</math> This is because by the second observation from Step 2, <math>f(3x - y) = 0 \implies f(y - 3x) = 0.</math> Then because <math>(x + y) - (y - 3x) = 4x</math>, Step 5 together with the observation from Step 3 yield <math>f(3x - y) = 0 \implies f(4x) = 0 \implies f(2x) = 0 \implies f(x) = 0</math>, impossible.<br />
<br />
<math>\indent</math> By the second observation from Step 4, these three facts imply that <math>f(y) = y^2</math> and <math>f(x - 3y) = \left(x - 3y\right)^2</math> and <math>f(3x - y) = \left(3x - y\right)^2.</math> By plugging into the given equation, it follows that<br />
<cmath>\begin{align*}<br />
\left(x^2 + xy\right)\left(x - 3y\right)^2 + \left(y^2 + xy\right)\left(3x - y\right)^2 = 0.<br />
\end{align*}</cmath> But the above expression miraculously factors into <math>\left(x + y\right)^4</math>! This is clearly a contradiction, since <math>t = x + y \ne 0</math> by assumption. This completes Step 6.<br />
<br />
'''Step 7:''' By Step 6 and the second observation from Step 4, the only possible solutions are <math>f \equiv 0</math> and <math>f(x) = x^2</math> for all <math>x \in \mathbb{R}.</math> It's easy to check that both of these work, so we're done.<br />
<br />
{{MAA Notice}}<br />
==Solution 2==<br />
Step 1: <math>x=y=0 \implies f(0)=0</math><br />
<br />
Step 2: <math>x=0 \implies f(y)f(-y)=f(y)^{2}</math>. Now, assume <math>y \not = 0</math>. Then, if <math>f(y)=0</math>, we substitute in <math>-y</math> to get <math>f(y)f(-y)=f(-y)^{2}</math>, or <math>f(y)=f(-y)=0</math>. Otherwise, we divide both sides by <math>f(y)</math> to get <math>f(y)=f(-y)</math>. If <math>y=0</math>, we obviously have <math>f(0)=f(0)</math>. Thus, the function is even.<br />
.<br />
Step 3: <math>y=-x \implies 2f(4x)(f(x)-x^{2})=0</math>. Thus, <math>\forall x</math>, we have <math>f(4x)=0</math> or <math>f(x)=x^{2}</math>.<br />
<br />
Step 4: We now assume <math>f(x) \not = 0</math>, <math>x\not = 0</math>. We have <math>f(\frac{x}{4})=\frac{x^{2}}{16}</math>. Now, setting <math>x=y=\frac{x}{4}</math>, we have <math>f(\frac{x}{2}=\frac{x^{2}}{4}</math> or <math>f(\frac{x}{2})=0</math>. The former implies that <math>f(x)=0</math> or <math>x^{2}</math>. The latter implies that <math>f(x)=0</math> or <math>f(x)=\frac{x^{2}}{2}</math>. Assume the latter. <math>y=-2x \implies -\frac{3y^{2}}{2}f(7y)-{2y^{2}}f(5y)=\frac{x^{2}}{2}</math>. Clearly, this implies that <math>f(x)</math> is negative for some <math>m</math>. Now, we have <math>f(\frac{m}{4})=\frac{m^{2}}{16} \implies f(\frac{m}{2})=0,\frac{m^{2}}{4} \implies f(m) \geq 0</math>, which is a contradiction. Thus, <math>\forall x</math><math>f(x)=0</math> or <math>f(x)=x^{2}</math>.<br />
<br />
Step 5: We now assume <math>f(x)=0</math>, <math>f(y)=y^{2}</math> for some <math>x,y \not = 0</math>. Let <math>m</math> be sufficiently large integer, let <math>z=|4^{m}x|</math> and take the absolute value of <math>y</math>(since the function is even). Choose <math>c</math> such that <math>3z-c=y</math>. Note that we have <math>\frac{c}{z}</math>~<math>3</math> and <math>\frac{y}{z}</math>~<math>0</math>. Note that <math>f(z)=0</math>. Now, <math>x=z, y=c \implies</math> LHS is positive, as the second term is positive and the first term is nonnegative and thus the right term is equal to <math>(z+c)^{4}</math>~<math>256z^{4}</math>. Now if <math>f(z-3c)=0</math>, the second term of the LHS/RHS clearly ~0 as <math>m \to \infty</math>. if <math>f(z-3c)=0</math>, then we have LHS/RHS ~ <math>0</math>, otherwise, we have LHS/RHS~<math>\frac{8^{2}\cdot 3z^{4}}{256z^{4}}</math>~<math>\frac{3}{4}</math>, a contradiction, as we're clearly not dividing by <math>0</math>, and we should have LHS/RHS=1.<br />
<br />
==See also==<br />
<br />
{{USAMO newbox|year=2016|num-b=3|num-a=5}}<br />
{{USAJMO newbox|year=2016|num-b=5|aftertext=|after=Last Problem}}</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_15&diff=776812016 AIME II Problems/Problem 152016-03-18T02:12:39Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>For <math>1 \leq i \leq 215</math> let <math>a_i = \dfrac{1}{2^{i}}</math> and <math>a_216 = \dfrac{1}{2^{215}}</math>. Let <math>x_1, x_2, ..., x_215</math> be positive real numbers such that <math>\sum_{i=1}^{215} x_i=1</math> and <math>\sum_{i \leq i < j \leq 216} x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}</math>. The maximum possible value of <math>x_2=\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
Replace <math>\sum x_ix_j</math> with <math>\frac12\left(\left(\sum x_i\right)^2-\sum x_i^2\right)</math> and the second equation becomes <math>\sum\frac{x_i^2}{1-a_i}=\frac{1}{215}</math>. Conveniently, <math>\sum 1-a_i=215</math> so we get <math>\left(\sum 1-a_i\right)\left(\sum\frac{x_i^2}{1-a_i}\right)=1=\left(\sum x_i\right)^2</math>. This is the equality case of Cauchy so <math>x_i=c(1-a_i)</math> for some constant <math>c</math>. Using <math>\sum x_i=1</math>, we find <math>c=\frac{1}{215}</math> and thus <math>x_2=\frac{3}{860}</math>. Thus, the desired answer is <math>860+3=\boxed{863}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_10&diff=776752016 AIME II Problems/Problem 102016-03-18T01:08:27Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>Triangle <math>ABC</math> is inscribed in circle <math>\omega</math>. Points <math>P</math> and <math>Q</math> are on side <math>\overline{AB}</math> with <math>AP<AQ</math>. Rays <math>CP</math> and <math>CQ</math> meet <math>\omega</math> again at <math>S</math> and <math>T</math> (other than <math>C</math>), respectively. If <math>AP=4,PQ=3,QB=6,BT=5,</math> and <math>AS=7</math>, then <math>ST=\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
<asy><br />
import cse5;<br />
pathpen = black; pointpen = black;<br />
pointfontsize = 9;<br />
size(8cm);<br />
<br />
pair A = origin, B = (13,0), P = (4,0), Q = (7,0),<br />
T = B + 5 dir(220), C = IP(circumcircle(A,B,T),Line(T,Q,-0.1,10)),<br />
S = IP(circumcircle(A,B,C),Line(C,P,-0.1,10));<br />
<br />
Drawing(A--B--C--cycle);<br />
D(circumcircle(A,B,C),rgb(0,0.6,1));<br />
DrawPathArray(C--S^^C--T,rgb(1,0.4,0.1));<br />
DrawPathArray(A--S^^B--T,rgb(0,0.4,0));<br />
D(S--T,rgb(1,0.2,0.4));<br />
<br />
D("A",A,dir(215));<br />
D("B",B,dir(330));<br />
D("P",P,dir(240));<br />
D("Q",Q,dir(240));<br />
D("T",T,dir(290));<br />
D("C",C,dir(120));<br />
D("S",S,dir(250));<br />
<br />
MP("4",(A+P)/2,dir(90));<br />
MP("3",(P+Q)/2,dir(90));<br />
MP("6",(Q+B)/2,dir(90));<br />
MP("5",(B+T)/2,dir(140));<br />
MP("7",(A+S)/2,dir(40));<br />
</asy><br />
Let <math>\angle ACP=\alpha</math>, <math>\angle PCQ=\beta</math>, and <math>\angle QCB=\gamma</math>. Note that since <math>\triangle ACQ\sim\triangle TBQ</math> we have <math>\tfrac{AC}{CQ}=\tfrac56</math>, so by the Ratio Lemma <cmath>\dfrac{AP}{PQ}=\dfrac{AC}{CQ}\cdot\dfrac{\sin\alpha}{\sin\beta}\quad\implies\quad \dfrac{\sin\alpha}{\sin\beta}=\dfrac{24}{15}.</cmath>Similarly, we can deduce <math>\tfrac{PC}{CB}=\tfrac47</math> and hence <math>\tfrac{\sin\beta}{\sin\gamma}=\tfrac{21}{24}</math>.<br />
<br />
Now Law of Sines on <math>\triangle ACS</math>, <math>\triangle SCT</math>, and <math>\triangle TCB</math> yields <cmath>\dfrac{AS}{\sin\alpha}=\dfrac{ST}{\sin\beta}=\dfrac{TB}{\sin\gamma}.</cmath>Hence <cmath>\dfrac{ST^2}{\sin^2\beta}=\dfrac{TB\cdot AS}{\sin\alpha\sin\gamma},</cmath>so <cmath>TS^2=TB\cdot AS\left(\dfrac{\sin\beta}{\sin\alpha}\dfrac{\sin\beta}{\sin\gamma}\right)=\dfrac{15\cdot 21}{24^2}\cdot 5\cdot 7=\dfrac{35^2}{8^2}.</cmath>Hence <math>ST=\tfrac{35}8</math> and the requested answer is <math>35+8=\boxed{43}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_10&diff=776742016 AIME II Problems/Problem 102016-03-18T01:06:53Z<p>Shaddoll: Solution</p>
<hr />
<div>Triangle <math>ABC</math> is inscribed in circle <math>\omega</math>. Points <math>P</math> and <math>Q</math> are on side <math>\overline{AB}</math> with <math>AP<AQ</math>. Rays <math>CP</math> and <math>CQ</math> meet <math>\omega</math> again at <math>S</math> and <math>T</math> (other than <math>C</math>), respectively. If <math>AP=4,PQ=3,QB=6,BT=5,</math> and <math>AS=7</math>, then <math>ST=\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
[asy]<br />
import cse5;<br />
pathpen = black; pointpen = black;<br />
pointfontsize = 9;<br />
size(8cm);<br />
<br />
pair A = origin, B = (13,0), P = (4,0), Q = (7,0),<br />
T = B + 5 dir(220), C = IP(circumcircle(A,B,T),Line(T,Q,-0.1,10)),<br />
S = IP(circumcircle(A,B,C),Line(C,P,-0.1,10));<br />
<br />
Drawing(A--B--C--cycle);<br />
D(circumcircle(A,B,C),rgb(0,0.6,1));<br />
DrawPathArray(C--S^^C--T,rgb(1,0.4,0.1));<br />
DrawPathArray(A--S^^B--T,rgb(0,0.4,0));<br />
D(S--T,rgb(1,0.2,0.4));<br />
<br />
D("A",A,dir(215));<br />
D("B",B,dir(330));<br />
D("P",P,dir(240));<br />
D("Q",Q,dir(240));<br />
D("T",T,dir(290));<br />
D("C",C,dir(120));<br />
D("S",S,dir(250));<br />
<br />
MP("4",(A+P)/2,dir(90));<br />
MP("3",(P+Q)/2,dir(90));<br />
MP("6",(Q+B)/2,dir(90));<br />
MP("5",(B+T)/2,dir(140));<br />
MP("7",(A+S)/2,dir(40));<br />
[/asy]<br />
Let <math>\angle ACP=\alpha</math>, <math>\angle PCQ=\beta</math>, and <math>\angle QCB=\gamma</math>. Note that since <math>\triangle ACQ\sim\triangle TBQ</math> we have <math>\tfrac{AC}{CQ}=\tfrac56</math>, so by the Ratio Lemma <cmath>\dfrac{AP}{PQ}=\dfrac{AC}{CQ}\cdot\dfrac{\sin\alpha}{\sin\beta}\quad\implies\quad \dfrac{\sin\alpha}{\sin\beta}=\dfrac{24}{15}.</cmath>Similarly, we can deduce <math>\tfrac{PC}{CB}=\tfrac47</math> and hence <math>\tfrac{\sin\beta}{\sin\gamma}=\tfrac{21}{24}</math>.<br />
<br />
Now Law of Sines on <math>\triangle ACS</math>, <math>\triangle SCT</math>, and <math>\triangle TCB</math> yields <cmath>\dfrac{AS}{\sin\alpha}=\dfrac{ST}{\sin\beta}=\dfrac{TB}{\sin\gamma}.</cmath>Hence <cmath>\dfrac{ST^2}{\sin^2\beta}=\dfrac{TB\cdot AS}{\sin\alpha\sin\gamma},</cmath>so <cmath>TS^2=TB\cdot AS\left(\dfrac{\sin\beta}{\sin\alpha}\dfrac{\sin\beta}{\sin\gamma}\right)=\dfrac{15\cdot 21}{24^2}\cdot 5\cdot 7=\dfrac{35^2}{8^2}.</cmath>Hence <math>ST=\tfrac{35}8</math> and the requested answer is <math>35+8=\boxed{43}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_15&diff=776732016 AIME II Problems/Problem 152016-03-18T01:04:08Z<p>Shaddoll: </p>
<hr />
<div>For <math>1 \leq i \leq 215</math> let <math>a_i = \dfrac{1}{2^{i}}</math> and <math>a_216 = \dfrac{1}{2^{215}}</math>. Let <math>x_1, x_2, ..., x_215</math> be positive real numbers such that <math>\sum_{i=1}^{215} x_i=1</math> and <math>\sum_{i \leq i < j \leq 216} x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}</math>. The maximum possible value of <math>x_2=\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
Replace <math>\sum x_ix_j</math> with <math>\frac12\left(\left(\sum x_i\right)^2-\sum x_i^2\right)</math> and the second equation becomes <math>\sum\frac{x_i^2}{1-a_i}=\frac{1}{215}</math>. Conveniently, <math>\sum 1-a_i=215</math> so we get <math>\left(\sum 1-a_i\right)\left(\sum\frac{x_i^2}{1-a_i}\right)=1=\left(\sum x_i\right)^2</math>. This is the equality case of Cauchy so <math>x_i=c(1-a_i)</math> for some constant <math>c</math>. Using <math>\sum x_i=1</math>, we find <math>c=\frac{1}{215}</math> and thus <math>x_2=\frac{3}{860}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_15&diff=776722016 AIME II Problems/Problem 152016-03-18T01:02:43Z<p>Shaddoll: Solution</p>
<hr />
<div>For <math>1 \leq i \leq 215</math> let <math>a_i = \dfrac{1}{2^{i}}</math> and <math>a_216 = \dfrac{1}{2^{215}}</math>. Let <math>x_1, x_2, ..., x_215</math> be positive real numbers such that <math>\sum_{i=1}^{215} x_i=1</math> and <math>\sum_{i \leq i < j \leq 216 x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}. The maximum possible value of </math>x_2=\dfrac{m}{n}<math>, where </math>m<math> and </math>n<math> are relatively prime positive integers. Find </math>m+n<math>.<br />
<br />
==Solution==<br />
Replace </math>\sum x_ix_j<math> with </math>\frac12\left(\left(\sum x_i\right)^2-\sum x_i^2\right)<math> and the second equation becomes </math>\sum\frac{x_i^2}{1-a_i}=\frac{1}{215}<math>. Conveniently, </math>\sum 1-a_i=215<math> so we get </math>\left(\sum 1-a_i\right)\left(\sum\frac{x_i^2}{1-a_i}\right)=1=\left(\sum x_i\right)^2<math>. This is the equality case of Cauchy so </math>x_i=c(1-a_i)<math> for some constant </math>c<math>. Using </math>\sum x_i=1<math>, we find </math>c=\frac{1}{215}<math> and thus </math>x_2=\frac{3}{860}$.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_13&diff=776712016 AIME II Problems/Problem 132016-03-18T00:59:05Z<p>Shaddoll: Solution</p>
<hr />
<div>Beatrix is going to place six rooks on a <math>6 \times 6</math> chessboard where both the rows and columns are labeled <math>1</math> to <math>6</math>; the rooks are placed so that no two rooks are in the same row or the same column. The <math>value</math> of a square is the sum of its row number and column number. The <math>score</math> of an arrangement of rooks is the least value of any occupied square.The average score over all valid configurations is <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
==Solution==<br />
We casework to find the number of ways to get each possible score. Note that the lowest possible score is <math>2</math> and the highest possible score is <math>7</math>. Let the bijective function <math>f(x)=\{1,2,3,4,5,6\} \to \{1,2,3,4,5,6\}</math> denote the row number of the rook for the corresponding column number. For a score of <math>2</math>, we must have <math>f(1)=1</math>, and we can arrange the rest of the function however we want, so there are <math>5!=120</math> ways. For a score of <math>3</math>, we must have either <math>f(1)=2</math> or <math>f(2)=1</math>, and we can arrange the rest of the rooks however we want, so by PIE the number of ways is <math>5!+5!-4!=216</math>. For a score of <math>4</math>, we must have <math>f(1)=3</math>, <math>f(2)=2</math>, or <math>f(3)=1</math>. If <math>f(1)=3</math>, we just don't want <math>f(2)=1</math>, if <math>f(2)=2</math>, we don't want <math>f(1)=1</math>, or if <math>f(3)=1</math>, we don't want <math>f(1)=2</math>, otherwise we can arrange the function however we like. If at least <math>2</math> of the values rooks have a value of <math>4</math>, we can arange the rest of the rooks however we like, so there are <math>3(5!-4!)-3(4!)+3!=222</math> by PIE. If the score is <math>5</math>, then we have either <math>f(4)=1</math>, <math>f(3)=2</math>, <math>f(2)=3</math>, or <math>f(1)=4</math>. If we have the first case, we don't want <math>f(2)=2</math>, <math>f(1)=2</math>, or <math>f(1)=3</math>, so by PIE the number of bad cases is <math>4!+4!-3!=42</math>. If we have the second case, then we don't want <math>f(2)=1</math>, <math>f(1)=1</math>, or <math>f(1)=3</math>, so similarly there are <math>42</math> bad cases. Therefore, there are a total of <math>54</math> good cases for each one. The number of ways to get <math>f(1)=1, f(1)=4</math> is <math>4!-3!</math> because we don't want <math>f(2)=2</math>, the number of ways to get <math>f(4)=1, f(2)=3</math> is <math>4!-3!</math> ways because we don't want <math>f(1)=2</math>, the number of ways to get <math>f(2)=3, f(3)=2</math> is <math>4!-3!</math> ways because we don't want <math>f(1)=1</math>, and the number of ways to get <math>f(1)=4, f(2)=3</math> is <math>4!-3!</math> ways because we don't want <math>f(3)=1</math>. The number of ways to get at least <math>3</math> cases satisfied is <math>6! \cdot 4</math> because we can arrange the remaining rooks however we like, and the number of ways to get all <math>4</math> cases satisfied is <math>2!=2</math> ways because we can arrange the remaining rooks however we like, so by PIE we have <math>54 \cdot 4-18 \cdot 6 + 6! \cdot 4-2!=130</math> ways to get a score of <math>5</math>. The only way to get a score of <math>7</math> is to have all the rooks run on the antidiagonal. Therefore, the number of ways to get a sum of <math>6</math> is <math>6!-120-216-222-130-1=31</math>. Thus, the expected sum is <math>\dfrac{120 \cdot 2 + 216 \cdot 3 + 222 \cdot 4 + 130 \cdot 5 + 31 \cdot 6 + 1 \cdot 7}{720}= \dfrac{2619}{720}=\dfrac{291}{80}</math>, so the desired answer is <math>291+80=\boxed{371}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_12&diff=776692016 AIME II Problems/Problem 122016-03-18T00:38:15Z<p>Shaddoll: Solution</p>
<hr />
<div>The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.<br />
Insert figure of a smaller circle, a bigger circle, and 6 sections dividing the region between the concentric circles.<br />
<br />
==Solution==<br />
Assume, WLOG, the left ring is color <math>1</math>. Now, let <math>f(a,b)</math> be the number of ways to satisfy the conditions where there are <math>a</math> sections ending on color <math>b</math>. We make a table on <math>f(a,b)</math>.<br />
<math>\begin{tabular}{c|c|c|c|c }&1 & 2 & 3& 4 \\ \hline<br />
1& 1 & 0 & 0 & 0\\<br />
2 & 0 & 1 & 1 & 1 \\<br />
3& 3 & 2 & 2 & 2 \\<br />
4 & 6 & 7 & 7 & 7 \\<br />
5 & 21 & 20 & 20 & 20\\<br />
6& 0& 61 & 61 & 61\\<br />
\end{tabular}</math><br />
Note that <math>f(6, 1)=0</math> because then <math>2</math> adjacent sections are both color <math>1</math>. We also have to multiply by <math>4</math> by symmetry for other colors in the left ring, so the desired answer is <math>(61+61+61) \cdot 4 = \boxed{732}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_11&diff=776682016 AIME II Problems/Problem 112016-03-18T00:29:56Z<p>Shaddoll: Solution</p>
<hr />
<div>For positive integers <math>N</math> and <math>k</math>, define <math>N</math> to be <math>k</math>-nice if there exists a positive integer <math>a</math> such that <math>a^{k}</math> has exactly <math>N</math> positive divisors. Find the number of positive integers less than <math>1000</math> that are neither <math>7</math>-nice nor <math>8</math>-nice.<br />
<br />
==Solution==<br />
We claim that an integer <math>N</math> is only <math>k</math>-nice if and only if <math>N \equiv 1 \pmod k</math>. By the number of divisors formula, the number of divisors of <math>\prod_{i=1}^n p_i^{a_i}</math> is <math>\prod_{i=1}^n (a_i+1)</math>. Since all the <math>a_i</math>s are divisible by <math>k</math> in a perfect <math>k</math> power, the only if part of the claim follows. To show that all numbers <math>N \equiv 1 \pmod k</math> are <math>k</math>-nice, write <math>N=bk+1</math>. Note that <math>2^{kb}</math> has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than <math>1000</math> that are either <math>1 \pmod 7</math> or <math>1\pmod 8</math> is <math>143+125-18=250</math>, so the desired answer is <math>999-250=\boxed{749}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_9&diff=776672016 AIME II Problems/Problem 92016-03-18T00:24:09Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>The sequences of positive integers <math>1,a_2, a_3,...</math> and <math>1,b_2, b_3,...</math> are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let <math>c_n=a_n+b_n</math>. There is an integer <math>k</math> such that <math>c_{k-1}=100</math> and <math>c_{k+1}=1000</math>. Find <math>c_k</math>.<br />
<br />
==Solution==<br />
Since all the terms of the sequences are integers, and 100 isn't very big, we should just try out the possibilities for <math>b_2</math>. When we get to <math>b_2=9</math> and <math>a_2=91</math>, we have <math>a_4=271</math> and <math>b_4=729</math>, which works, therefore, the answer is <math>b_3+a_3=81+181=\boxed{262}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_9&diff=776662016 AIME II Problems/Problem 92016-03-18T00:23:55Z<p>Shaddoll: Solution</p>
<hr />
<div>The sequences of positive integers <math>1,a_2, a_3,...</math> and <math>1,b_2, b_3,...</math> are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let <math>c_n=a_n+b_n</math>. There is an integer <math>k</math> such that <math>c_{k-1}=100</math> and <math>c_{k+1}=1000</math>. Find <math>c_k</math>.<br />
<br />
==Solution==<br />
Since all the terms of the sequences are integers, and 100 isn't very big, we should just try out the possibilities for <math>b_2</math>. When we get to <math>b_2=9</math> and <math>a_2=91</math>, we have <math>a_4=271</math> and <math>b_4=729</math>, which works, therefore, the answer is <math>b_3+a_3=81+181=\boxed{262}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_8&diff=776652016 AIME II Problems/Problem 82016-03-18T00:21:25Z<p>Shaddoll: Solution</p>
<hr />
<div>Find the number of sets <math>{a,b,c}</math> of three distinct positive integers with the property that the product of <math>a,b,</math> and <math>c</math> is equal to the product of <math>11,21,31,41,51,61</math>.<br />
<br />
==Solution==<br />
Note that the prime factorization of the product is <math>3^{2}\cdot 7 \cdot 11 \cdot 17 \cdot 31 \cdot 41 \cdot 61</math>. Ignoring overcounting, by stars and bars there are <math>6</math> ways to choose how to distribute the factors of <math>3</math>, and <math>3</math> ways to distribute the factors of the other primes, so we have <math>3^{6} \cdot 6</math> ways. However, some sets have <math>2</math> numbers that are the same, namely the ones in the form <math>1,1,x</math> and <math>3,3,x</math>, which are each counted <math>3</math> times, and each other set is counted <math>6</math> times, so the desired answer is <math>\dfrac{729 \cdot 6-6}{6} = \boxed{728}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_5&diff=776642016 AIME II Problems/Problem 52016-03-18T00:17:24Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>Triangle <math>ABC_0</math> has a right angle at <math>C_0</math>. Its side lengths are pariwise relatively prime positive integers, and its perimeter is <math>p</math>. Let <math>C_1</math> be the foot of the altitude to <math>\overline{AB}</math>, and for <math>n \geq 2</math>, let <math>C_n</math> be the foot of the altitude to <math>\overline{C_{n-2}B}</math> in <math>\triangle C_{n-2}C_{n-1}B</math>. The sum <math>\sum_{i=1}^\infty C_{n-2}C_{n-1} = 6p</math>. Find <math>p</math>.<br />
<br />
==Solution==<br />
Note that by counting the area in 2 ways, the first altitude is <math>\dfrac{ac}{b}</math>. By similar triangles, the common ratio is <math>\dfrac{a}{c}</math> for reach height, so by the geometric series formula, we have <math>6p=\dfrac{\dfrac{ac}{b}}{1-\dfrac{a}{c}}</math>. Testing triangles of the form <math>2p+1, 2p^{2}+2p, 2p^{2}+2p+1</math>, we have <math>13, 84, 85</math> satisfy this equation, so <math>p=13+84+85=\boxed{182}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_5&diff=776632016 AIME II Problems/Problem 52016-03-18T00:17:09Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>Triangle <math>ABC_0</math> has a right angle at <math>C_0</math>. Its side lengths are pariwise relatively prime positive integers, and its perimeter is <math>p</math>. Let <math>C_1</math> be the foot of the altitude to <math>\overline{AB}</math>, and for <math>n \geq 2</math>, let <math>C_n</math> be the foot of the altitude to <math>\overline{C_{n-2}B}</math> in <math>\triangle C_{n-2}C_{n-1}B</math>. The sum <math>\sum_{i=1}^\infty C_{n-2}C_{n-1} = 6p</math>. Find <math>p</math>.<br />
<br />
==Solution==<br />
Note that by counting the area in 2 ways, the first altitude is <math>\dfrac{ac}{b}</math>. By similar triangles, the common ratio is <math>\dfrac{a}{c}</math> for reach height, so by the geometric series formula, we have <math>6p=\dfrac{\dfrac{ac}{b}}{1-\dfrac{a}{c}}</math>. Testing triangles of the form <math>2p+1, 2p^{2}+2p, 2p^{2}+2p+1</math>, we have <math>13, 84, 85</math> satisfy this equation, so <math>p=13+84+85=\boxed{182}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_5&diff=776622016 AIME II Problems/Problem 52016-03-18T00:16:43Z<p>Shaddoll: Solution</p>
<hr />
<div>Triangle <math>ABC_0</math> has a right angle at <math>C_0</math>. Its side lengths are pariwise relatively prime positive integers, and its perimeter is <math>p</math>. Let <math>C_1</math> be the foot of the altitude to <math>\overline{AB}</math>, and for <math>n \geq 2</math>, let <math>C_n</math> be the foot of the altitude to <math>\overline{C_{n-2}B}</math> in <math>\triangle C_{n-2}C_{n-1}B</math>. The sum <math>\sum_{i=1}^\infty C_{n-2}C_{n-1} = 6p</math>. Find <math>p</math>.<br />
<br />
==Solution==<br />
Note that by counting the area in 2 ways, the first altitude is <math>\dfrac{ac}{b}</math>. By similar triangles, the common ratio is <math>\dfrac{a}{c}</math> for reach height, so by the geometric series formula, we have <math>6p=\dfrac{dfrac{ac}{b}}{1-\dfrac{a}{c}}</math>. Testing triangles of the form <math>2p+1, 2p^{2}+2p, 2p^{2}+2p+1</math>, we have <math>13, 84, 85</math> satisfy this equation, so <math>p=13+84+85=\boxed{182}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_14&diff=776612016 AIME II Problems/Problem 142016-03-18T00:14:26Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>Equilateral <math>\triangle ABC</math> has side length <math>600</math>. Points <math>P</math> and <math>Q</math> lie outside the plane of <math>\triangle ABC</math> and are on opposite sides of the plane. Furthermore, <math>PA=PB=PC</math>, and <math>QA=QB=QC</math>, and the planes of <math>\triangle PAB</math> and <math>\triangle QAB</math> form a <math>120^{\circ}</math> dihedral angle (the angle between the two planes). There is a point <math>O</math> whose distance from each of <math>A,B,C,P,</math> and <math>Q</math> is <math>d</math>. Find <math>d</math>.<br />
<br />
==Solution==<br />
The inradius of <math>\triangle ABC</math> is <math>100\sqrt 3</math> and the circumradius is <math>200 \sqrt 3</math>. Now, consider the line perpendicular to plane <math>ABC</math> through the circumcenter of <math>\triangle ABC</math>. Note that <math>P,Q,O</math> must lie on that line to be equidistant from each of the triangle's vertices. Also, note that since <math>P, Q, O</math> are collinear, and <math>OP=OQ</math>, we must have <math>O</math> is the midpoint of <math>PQ</math>. Now, Let <math>K</math> be the circumcenter of <math>\triangle ABC</math>, and <math>L</math> be the foot of the altitude from <math>A</math> to <math>BC</math>. We must have <math>\tan(\angle KLP+ \angle QLK)= \tan(120^{\circ})</math>. Setting <math>KP=x</math> and <math>KQ=y</math>, assuming WLOG <math>x>y</math>, we must have <math>(\tan(120^{\circ})=-\sqrt{3}=\dfrac{\dfrac{x+y}{100 \sqrt{3}}}{\dfrac{30000-xy}{30000}}</math>. Therefore, we must have <math>100(x+y)=xy-30000</math>. Also, we must have <math>(\dfrac{x+y}{2})^{2}=(\dfrac{x-y}{2})^{2}+120000</math> by the Pythagorean theorem, so we have <math>xy=120000</math>, so substituting into the other equation we have <math>90000=100(x+y)</math>, or <math>x+y=900</math>. Since we want <math>\dfrac{x+y}{2}</math>, the desired answer is <math>\boxed{450}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_14&diff=776602016 AIME II Problems/Problem 142016-03-18T00:10:08Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>Equilateral <math>\triangle ABC</math> has side length <math>600</math>. Points <math>P</math> and <math>Q</math> lie outside the plane of <math>\triangle ABC</math> and are on opposite sides of the plane. Furthermore, <math>PA=PB=PC</math>, and <math>QA=QB=QC</math>, and the planes of <math>\triangle PAB</math> and <math>\triangle QAB</math> form a <math>120^{\circ}</math> dihedral angle (the angle between the two planes). There is a point <math>O</math> whose distance from each of <math>A,B,C,P,</math> and <math>Q</math> is <math>d</math>. Find <math>d</math>.<br />
<br />
==Solution==<br />
The inradius of <math>\triangle ABC</math> is <math>100\sqrt 3</math> and the circumradius is <math>200 \sqrt 3</math>. Now, consider the line perpendicular to plane <math>ABC</math> through the circumcenter of <math>\triangle ABC</math>. Note that <math>P,Q,O</math> must lie on that line to be equidistant from each of the triangle's vertices. Also, note that since <math>P, Q, O</math> are collinear, and <math>OP=OQ</math>, we must have <math>O</math> is the midpoint of <math>PQ</math>. Now, Let <math>K</math> be the circumcenter of <math>\triangle ABC</math>, and <math>L</math> be the foot of the altitude from <math>A</math> to <math>BC</math>. We must have <math>\tan(\angle KLP+ \angle QLK)= \tan(120^{\circ})</math>. Setting <math>KP=x</math> and <math>KQ=y</math>, assuming WLOG <math>x>y</math>, we must have <math>(\tan(120^{\circ})=-\sqrt{3}=\dfrac{\dfrac{x+y}{100 \sqrt{3}}}{\dfrac{30000-xy}{30000}}</math>. Therefore, we must have <math>100(x+y)=xy-30000</math>. Also, we must have <math>(\dfrac{x+y}{2})^{2}=(\dfrac{x-y}{2})^{2}+120000</math> by the Pythagorean theorem, so we have <math>xy=120000</math>, so substituting into the other equation we have <math>90000=100(x+y)</math>, or <math>x+y=900</math>. Since we want <math>\dfrac{x+y}{2}</math>, the desired answer is <math>\boxed{450}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_14&diff=776592016 AIME II Problems/Problem 142016-03-18T00:08:54Z<p>Shaddoll: Solution</p>
<hr />
<div>Equilateral <math>\triangle ABC</math> has side length <math>600</math>. Points <math>P</math> and <math>Q</math> lie outside the plane of <math>\triangle ABC</math> and are on opposite sides of the plane. Furthermore, <math>PA=PB=PC</math>, and <math>QA=QB=QC</math>, and the planes of <math>\triangle PAB</math> and <math>\triangle QAB</math> form a <math>120^{\circ}</math> dihedral angle (the angle between the two planes). There is a point <math>O</math> whose distance from each of <math>A,B,C,P,</math> and <math>Q</math> is <math>d</math>. Find <math>d</math>.<br />
<br />
==Solution==<br />
The inradius of <math>\triangle ABC</math> is <math>100\sqrt 3</math> and the circumradius is <math>200 \sqrt 3</math>. Now, consider the line perpendicular to plane <math>ABC</math> through the circumcenter of <math>\triangle ABC</math>. Note that <math>P,Q,O</math> must lie on that line to be equidistant from each of the triangle's vertices. Also, note that since <math>P, Q, O</math> are collinear, and <math>OP=OQ</math>, we must have <math>O</math> is the midpoint of <math>PQ</math>. Now, Let <math>K</math> be the circumcenter of <math>\triangle ABC</math>, and <math>L</math> be the foot of the altitude from <math>A</math> to <math>BC</math>. We must have <math>\tan(\angle KLP+ \angle QLK)= \tan(120^{\circ})</math>. Setting <math>KP=x</math> and <math>KQ=y</math>, assuming WLOG <math>x>y</math>, we must have <math>(\tan(120^{\circ})=-\sqrt{3}=\dfrac{\dfrac{x+y}{100\sqrt{3}}}{\dfrac{30000-xy}{30000}</math>. Therefore, we must have <math>100(x+y)=xy-30000</math>. Also, we must have <math>(\dfrac{x+y}{2})^{2}=(\dfrac{x-y}{2})^{2}+120000</math> by the Pythagorean theorem, so we have <math>xy=120000</math>, so substituting into the other equation we have <math>90000=100(x+y)</math>, or <math>x+y=900</math>. Since we want <math>\dfrac{x+y}{2}</math>, the desired answer is <math>\boxed{450}</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_7&diff=776582016 AIME II Problems/Problem 72016-03-17T23:48:46Z<p>Shaddoll: Solution</p>
<hr />
<div>Squares <math>ABCD</math> and <math>EFGH</math> have a common center at <math>\overline{AB} || \overline{EF}</math>. The area of <math>ABCD</math> is 2016, and the area of <math>EFGH</math> is a smaller positive integer. Square <math>IJKL</math> is constructed so that each of its vertices lies on a side of <math>ABCD</math> and each vertex of <math>EFGH</math> lies on a side of <math>IJKL</math>. Find teh difference between the largest and smallest positive integer values for the area of <math>IJKL</math>.<br />
<br />
==Solution==<br />
Letting <math>AI=a</math> and <math>IB=b</math>, we have <math>IJ^{2}=a^{2}+b^{2} \geq 1008</math> by CS inequality. Also, since <math>EFGH||ABCD</math>, the angles that each square cuts another are equal, so all the triangles are formed by a vertex of a larger square and <math>2</math> adjacent vertices of a smaller square are similar. Therefore, the areas form a geometric progression, so since <math>2016=12^{2} \cdot 14</math>, we have the maximum area is <math>2016 \cdot \dfrac{11}{12} = 1848</math> and the minimum area is <math>1008</math>, so the desired answer is <math>1848-1008=\boxed{840}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_6&diff=776552016 AIME II Problems/Problem 62016-03-17T23:37:46Z<p>Shaddoll: Solution</p>
<hr />
<div>For polynomial <math>P(x)=1-\dfrac{1}{3}x+\dfrac{1}{6}x^{2}</math>, define<br />
<math>Q(x)=P(x)P(x^{3})P(x^{5})P(x^{7})P(x^{9})=\sum_{i=0}^{50} a_ix^{i}</math>.<br />
Then <math>\sum_{i=0}^{50} |a_i|=\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution==<br />
Note that all the odd coefficients have an odd number of odd degree terms multiplied together, and all the even coefficients have an even number of odd degree terms multiplied together. Since every odd degree term is negative, and every even degree term is positive, the sum is just equal to <math>Q(-1)=P(-1)^{5}=(\dfrac{3}{2})^{5}=\dfrac{243}{32}</math>, so the desired answer is <math>243+32=\boxed{275}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_4&diff=776542016 AIME II Problems/Problem 42016-03-17T23:33:23Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>An <math>a \times b \times c</math> rectangular box is built from <math>a \cdot b \cdot c</math> unit cubes. Each unit cube is colored red, green, or yellow. Each of the <math>a</math> layers of size <math>1 \times b \times c</math> parallel to the <math>(b \times c)</math> faces of the box contains exactly <math>9</math> red cubes, exactly <math>12</math> green cubes, and some yellow cubes. Each of the <math>b</math> layers of size <math>a \times 1 \times c</math> parallel to the <math>(a \times c)</math> faces of the box contains exactly <math>20</math> green cubes, exactly <math>25</math> yellow cubes, and some red cubes. Find the smallest possible volume of the box.<br />
<br />
==Solution==<br />
By counting the number of green cubes <math>2</math> different ways, we have <math>12a=20b</math>, or <math>a=\dfrac{5}{3} b</math>. Notice that there are only <math>3</math> possible colors for unit cubes, so for each of the <math>1 \times b \times c</math> layers, there are <math>bc-21</math> yellow cubes, and similarly there are <math>ac-45</math> red cubes in each of the <math>1 \times a \times b</math> layers. Therefore, we have <math>a(bc-21)=25b</math> and <math>b(ac-45)=9a</math>. We check a few small values of <math>a,b</math> and solve for <math>c</math>, checking <math>(a,b)=(5,3)</math> gives <math>c=12</math> with a volume of <math>180</math>, <math>(a,b)=(10,6)</math> gives <math>c=6</math> with a volume of <math>360</math>, and <math>(a,b)=(15,9)</math> gives <math>c=4</math>, with a volume of <math>540</math>. Any higher <math>(a,b)</math> will <math>ab>180</math>, so therefore, the minimum volume is <math>\boxed{180}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_4&diff=776532016 AIME II Problems/Problem 42016-03-17T23:32:20Z<p>Shaddoll: Solution</p>
<hr />
<div>An <math>a \times b \times c</math> rectangular box is built from <math>a \cdot b \cdot c</math> unit cubes. Each unit cube is colored red, green, or yellow. Each of the <math>a</math> layers of size <math>1 \times b \times c</math> parallel to the <math>(b \times c)</math> faces of the box contains exactly <math>9</math> red cubes, exactly <math>12</math> green cubes, and some yellow cubes. Each of the <math>b</math> layers of size <math>a \times 1 \times c</math> parallel to the <math>(a \times c)</math> faces of the box contains exactly <math>20</math> green cubes, exactly <math>25</math> yellow cubes, and some red cubes. Find the smallest possible volume of the box.<br />
<br />
==Solution==<br />
By counting the number of green cubes <math>2</math> different ways, we have <math>12a=20b</math>, or <math>a=\dfrac{5}{3} b</math>. Notice that there are only <math>3</math> possible colors for unit cubes, so for each of the <math>1 \ times b \times c</math> layers, there are <math>bc-21</math> yellow cubes, and similarly there are <math>ac-45</math> red cubes in each of the <math>1 \times a \times b</math> layers. Therefore, we have <math>a(bc-21)=25b</math> and <math>b(ac-45)=9a</math>. We check a few small values of <math>a,b</math> and solve for <math>c</math>, checking <math>(a,b)=(5,3)</math> gives <math>c=12</math> with a volume of <math>180</math>, <math>(a,b)=(10,6)</math> gives <math>c=6</math> with a volume of <math>360</math>, and <math>(a,b)=(15,9)</math> gives <math>c=4</math>, with a volume of <math>540</math>. Any higher <math>(a,b)</math> will <math>ab>180</math>, so therefore, the minimum volume is <math>\boxed{180}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_1&diff=776522016 AIME II Problems/Problem 12016-03-17T23:23:22Z<p>Shaddoll: </p>
<hr />
<div>Initially Alex, Betty, and Charlie had a total of <math>444</math> peanuts. Charlie had the most peanuts, and Alex had the least. The three numbers of peanuts that each person had formed a geometric progression. Alex eats <math>5</math> of his peanuts, Betty eats <math>9</math> of her peanuts, and Charlie eats <math>25</math> of his peanuts. Now the three numbers of peanuts each person has forms an arithmetic progression. Find the number of peanuts Alex had initially.<br />
<br />
==Solution==<br />
Let <math>r</math> be the common ratio, where <math>r>1</math>. We than have <math>ar-9-(a-5)=a(r-1)-4=ar^{2}-25-(ar-9)=ar(r-1)-16</math>. We now have, letting, subtracting the 2 equations, <math>ar^{2}+-2ar+a=12</math>, so we have <math>3ar=432, or ar=144</math>, which is how much Betty had. Now we have <math>144+\dfrac{144}{r}+144r=444</math>, or <math>144(r+\dfrac{1}{r})=300</math>, or <math>r+\dfrac{1}{r}=\dfrac{25}{16}</math>, which solving for <math>r</math> gives <math>r=\dfrac{4}{3}</math>, since <math>r>1</math>, so Alex had <math>\dfrac{3}{4} \cdot 144=\boxed{108}</math> peanuts.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_3&diff=776512016 AIME II Problems/Problem 32016-03-17T23:09:18Z<p>Shaddoll: /* Problem 3 */</p>
<hr />
<div>Let <math>x,y,</math> and <math>z</math> be real numbers satisfying the system<br />
<math>\log_2(xyz-3+\log_5 x)=5</math><br />
<math>\log_3(xyz-3+\log_5 y)=4</math><br />
<math>\log_4(xyz-3+\log_5 z)=4</math><br />
Find the value of <math>|\log_5 x|+|\log_5 y|+|\log_5 z|</math>.<br />
<br />
==Solution==<br />
First, we get rid of logs by taking powers: <math>xyz-3+\log_5 x=2^{5}=32</math>, <math>xyz-3+\log_5 y=3^{4}=81</math>, and <math>(xyz-3+\log_5 z)=4^{4}=256</math>. Adding all the equations up and using the <math>\log {xy}=\log {x}+\log{y}</math> property, we have <math>3xyz+\log_5{xyz} = 378</math>, so we have <math>xyz=125</math>. Solving for <math>x,y,z</math> by substituting <math>125</math> for <math>xyz</math> in each equation, we get <math>\log_5 x=-90, \log_5 y=-41, \log_5 z=134</math>, so adding all the absolute values we have <math>90+41+134=\boxed{265}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_3&diff=776502016 AIME II Problems/Problem 32016-03-17T23:07:30Z<p>Shaddoll: /* Problem 3 */</p>
<hr />
<div>==Problem 3==<br />
Let <math>x,y,</math> and <math>z</math> be real numbers satisfying the system<br />
<math>\log_2(xyz-3+\log_5 x)=5</math><br />
<math>\log_3(xyz-3+\log_5 y)=4</math><br />
<math>\log_4(xyz-3+\log_5 z)=4</math><br />
Find the value of <math>|\log_5 x|+|\log_5 y|+|\log_5 z|</math>.<br />
<br />
==Solution==<br />
First, we get rid of logs by taking powers: <math>xyz-3+\log_5 x=2^{5}=32</math>, <math>xyz-3+\log_5 y=3^{4}=81</math>, and <math>(xyz-3+\log_5 z)=4^{4}=256</math>. Adding all the equations up and using the <math>\log {xy}=\log {x}+\log{y}</math> property, we have <math>3xyz+\log_5{xyz} = 378</math>, so we have <math>xyz=125</math>. Solving for <math>x,y,z</math> by substituting <math>125</math> for <math>xyz</math> in each equation, we get <math>\log_5 x=-90, \log_5 y=-41, \log_5 z=134</math>, so adding all the absolute values we have <math>90+41+134=\boxed{265}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_3&diff=776492016 AIME II Problems/Problem 32016-03-17T23:07:15Z<p>Shaddoll: Solution/Problem 3 AIME II</p>
<hr />
<div>==Problem 3==<br />
Let <math>x,y,</math> and <math>z</math> be real numbers satisfying the system<br />
<math>\log_2(xyz-3+\log_5 x)=5</math><br />
<math>\log_3(xyz-3+\log_5 y)=4</math><br />
<math>\log_4(xyz-3+\log_5 z)=4</math><br />
Find the value of <math>|\log_5 x|+|\log_5 y|+|\log_5 z|</math>.<br />
<br />
==Solution<br />
First, we get rid of logs by taking powers: <math>xyz-3+\log_5 x=2^{5}=32</math>, <math>xyz-3+\log_5 y=3^{4}=81</math>, and <math>(xyz-3+\log_5 z)=4^{4}=256</math>. Adding all the equations up and using the <math>\log {xy}=\log {x}+\log{y}</math> property, we have <math>3xyz+\log_5{xyz} = 378</math>, so we have <math>xyz=125</math>. Solving for <math>x,y,z</math> by substituting <math>125</math> for <math>xyz</math> in each equation, we get <math>\log_5 x=-90, \log_5 y=-41, \log_5 z=134</math>, so adding all the absolute values we have <math>90+41+134=\boxed{265}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_2&diff=776482016 AIME II Problems/Problem 22016-03-17T23:00:02Z<p>Shaddoll: Solution</p>
<hr />
<div>There is a <math>40\%</math> chance of rain on Saturday and a <math>30\%</math> chance of rain on Sunday. However, it is twice as likely to rain on Sunday if it rains on Saturday than if it does not rain on Saturday. The probability that it rains at least one day this weekend is <math>\frac{a}{b}</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers. Find <math>a+b</math>.<br />
==Solution==<br />
Let <math>x</math> be the probability that it rains on Sunday given that it doesn't rain on Saturday. We then have <math>\dfrac{3}{5}x+\dfrac{2}{5}2x = \dfrac{3}{10} \implies \dfrac{7}{5}x=\dfrac{3}{10}</math> <math> \implies x=\dfrac{3}{14}</math>. Therefore, the probability that it doesn't rain on either day is <math>(1-\dfrac{3}{14})(\dfrac{3}{5})=\dfrac{33}{70}</math>. Therefore, the probability that rains on at least one of the days is <math>1-\dfrac{33}{70}=\dfrac{37}{70}</math>, so adding up the <math>2</math> numbers, we have <math>37+70=\boxed{107}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774992015 USAMO Problems/Problem 42016-03-11T00:09:09Z<p>Shaddoll: minor hole in solution</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math> and <math>g_i, h_i\geq 0 \forall i</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone at <math>(i, j)</math>, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math> and <math>r_i, c_i \geq 0 \forall i</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774982015 USAMO Problems/Problem 42016-03-11T00:08:32Z<p>Shaddoll: typo</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math> and <math>g_i, h_i>0 \forall i</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j \geq0</math> and place a stone at <math>(i, j)</math>, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math> and <math>r_i, c_i \geq 0 \forall i</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774972015 USAMO Problems/Problem 42016-03-11T00:08:08Z<p>Shaddoll: minor hole</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math> and <math>g_i, h_i>0 \forall i</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone at <math>(i, j)</math>, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math> and <math>r_i, c_i \geq 0 \forall i</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774932015 USAMO Problems/Problem 42016-03-10T04:35:44Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone at <math>(i, j)</math>, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math> and <math>r_i, c_i \geq 0 \forall i</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774922015 USAMO Problems/Problem 42016-03-10T04:34:32Z<p>Shaddoll: typo</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone at <math>(i, j)</math>, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774912015 USAMO Problems/Problem 42016-03-10T04:33:21Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone at (i, j)<math>, then we subtract </math>g_i<math> and </math>h_j<math> by </math>1<math> each, until </math>g_i<math> and </math>h_i<math> become </math>0<math> </math>\forall i<math>, which will happen when </math>m<math> stones are placed, because </math>\sum_{i=1}^n g_i<math> and </math>\sum_{i=1}^n h_i<math> are both initially </math>m<math> and decrease by </math>1<math> after each stone is placed. Note that in this process </math>r_i+g_i<math> and </math>c_i+h_i<math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences </math>r_i<math> and </math>c_i<math> such that </math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m<math>. By stars and bars, the number of ways is </math>\binom{n+m-1}{m}^{2}$.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774902015 USAMO Problems/Problem 42016-03-10T04:32:50Z<p>Shaddoll: typoed</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone there, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remains invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774892015 USAMO Problems/Problem 42016-03-10T04:32:03Z<p>Shaddoll: typoed</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone there, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each step. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remain invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774882015 USAMO Problems/Problem 42016-03-10T04:28:14Z<p>Shaddoll: minor wording change</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone there, then we subtract <math>r_i</math> and <math>c_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each step. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remain invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774872015 USAMO Problems/Problem 42016-03-10T04:27:36Z<p>Shaddoll: Leaving space between lemmas and proofs</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are equivalent <math>\forall i</math>.<br />
<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone there, then we subtract <math>r_i</math> and <math>c_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each step. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remain invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774862015 USAMO Problems/Problem 42016-03-10T04:26:50Z<p>Shaddoll: /* Problem */</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
==Solution==<br />
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math><br />
<br />
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are equivalent <math>\forall i</math>.<br />
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.<br />
<br />
Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> are equivalent.<br />
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.<br />
<br />
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.<br />
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone there, then we subtract <math>r_i</math> and <math>c_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each step. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remain invariant, thus, the final piling satisfies the conditions above.<br />
<br />
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.<br />
<br />
Solution by Shaddoll</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774842015 USAMO Problems/Problem 42016-03-10T01:58:22Z<p>Shaddoll: /* Solution */</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774832015 USAMO Problems/Problem 42016-03-10T01:58:14Z<p>Shaddoll: /* Problem 4 */</p>
<hr />
<div>===Problem===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
<br />
===Solution===<br />
According to the given, <math>f(x-a)+f(x+0.5a)=f(x-0.5a)+f(x)</math>, where <math>x</math> and <math>a</math> are rational. Likewise, <math>f(x-0.5a)+f(x+a)=f(x+0.5a)+f(x)</math>. Hence <math>f(x+a)-f(x)= f(x)-f(x-a)</math>, namely <math>2f(x)=f(x-a)+f(x+a)</math>. Let <math>f(0)=C</math>, then consider <math>F(x)=f(x)-C</math>, where <math>F(0)=0</math> and <math>2F(x)=F(x-a)+F(x+a)</math>. We have:<br />
<br />
<cmath>F(2x)=F(x)+[F(x)-F(0)]=2F(x)</cmath><br />
<cmath>F(3x)=F(2x)+[F(2x)-F(x)]=3F(x)</cmath><br />
By induction, <math>F(nx)=nF(x)</math> for all in.tegers <math>k</math>.<br />
Therefore, for nonzero integer <math>m</math>, <math>\frac{1}{m}F(mx)=F(x)</math>, namely <math>F\left(\frac{x}{m}\right)=\left(\frac{1}{m}\right)F(x)</math>.<br />
Hence <math>F\left(\frac{n}{m}\right)=\left(\frac{n}{m}\right)F(1)</math>. Letting <math>F(1)=k</math>, we obtain <math>F(x)=kx</math>, where <math>k</math> is the slope of the linear functions, and <math>f(x)=kx+C</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774822015 USAMO Problems/Problem 42016-03-10T01:57:38Z<p>Shaddoll: /* Problem 6 */</p>
<hr />
<div>===Problem 4===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
<br />
===Solution===<br />
According to the given, <math>f(x-a)+f(x+0.5a)=f(x-0.5a)+f(x)</math>, where <math>x</math> and <math>a</math> are rational. Likewise, <math>f(x-0.5a)+f(x+a)=f(x+0.5a)+f(x)</math>. Hence <math>f(x+a)-f(x)= f(x)-f(x-a)</math>, namely <math>2f(x)=f(x-a)+f(x+a)</math>. Let <math>f(0)=C</math>, then consider <math>F(x)=f(x)-C</math>, where <math>F(0)=0</math> and <math>2F(x)=F(x-a)+F(x+a)</math>. We have:<br />
<br />
<cmath>F(2x)=F(x)+[F(x)-F(0)]=2F(x)</cmath><br />
<cmath>F(3x)=F(2x)+[F(2x)-F(x)]=3F(x)</cmath><br />
By induction, <math>F(nx)=nF(x)</math> for all in.tegers <math>k</math>.<br />
Therefore, for nonzero integer <math>m</math>, <math>\frac{1}{m}F(mx)=F(x)</math>, namely <math>F\left(\frac{x}{m}\right)=\left(\frac{1}{m}\right)F(x)</math>.<br />
Hence <math>F\left(\frac{n}{m}\right)=\left(\frac{n}{m}\right)F(1)</math>. Letting <math>F(1)=k</math>, we obtain <math>F(x)=kx</math>, where <math>k</math> is the slope of the linear functions, and <math>f(x)=kx+C</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&diff=774812015 USAMO Problems/Problem 42016-03-10T01:57:25Z<p>Shaddoll: /* Problem */</p>
<hr />
<div>===Problem 6===<br />
Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.<br />
<br />
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.<br />
<br />
How many different non-equivalent ways can Steve pile the stones on the grid?<br />
<br />
===Solution===<br />
According to the given, <math>f(x-a)+f(x+0.5a)=f(x-0.5a)+f(x)</math>, where <math>x</math> and <math>a</math> are rational. Likewise, <math>f(x-0.5a)+f(x+a)=f(x+0.5a)+f(x)</math>. Hence <math>f(x+a)-f(x)= f(x)-f(x-a)</math>, namely <math>2f(x)=f(x-a)+f(x+a)</math>. Let <math>f(0)=C</math>, then consider <math>F(x)=f(x)-C</math>, where <math>F(0)=0</math> and <math>2F(x)=F(x-a)+F(x+a)</math>. We have:<br />
<br />
<cmath>F(2x)=F(x)+[F(x)-F(0)]=2F(x)</cmath><br />
<cmath>F(3x)=F(2x)+[F(2x)-F(x)]=3F(x)</cmath><br />
By induction, <math>F(nx)=nF(x)</math> for all in.tegers <math>k</math>.<br />
Therefore, for nonzero integer <math>m</math>, <math>\frac{1}{m}F(mx)=F(x)</math>, namely <math>F\left(\frac{x}{m}\right)=\left(\frac{1}{m}\right)F(x)</math>.<br />
Hence <math>F\left(\frac{n}{m}\right)=\left(\frac{n}{m}\right)F(1)</math>. Letting <math>F(1)=k</math>, we obtain <math>F(x)=kx</math>, where <math>k</math> is the slope of the linear functions, and <math>f(x)=kx+C</math>.</div>Shaddollhttps://artofproblemsolving.com/wiki/index.php?title=2014_USAJMO_Problems/Problem_2&diff=774802014 USAJMO Problems/Problem 22016-03-10T01:30:58Z<p>Shaddoll: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Let <math>\triangle{ABC}</math> be a non-equilateral, acute triangle with <math>\angle A=60^{\circ}</math>, and let <math>O</math> and <math>H</math> denote the circumcenter and orthocenter of <math>\triangle{ABC}</math>, respectively.<br />
<br />
(a) Prove that line <math>OH</math> intersects both segments <math>AB</math> and <math>AC</math>.<br />
<br />
(b) Line <math>OH</math> intersects segments <math>AB</math> and <math>AC</math> at <math>P</math> and <math>Q</math>, respectively. Denote by <math>s</math> and <math>t</math> the respective areas of triangle <math>APQ</math> and quadrilateral <math>BPQC</math>. Determine the range of possible values for <math>s/t</math>.<br />
<br />
==Solution==<br />
<asy><br />
import olympiad;<br />
unitsize(1inch);<br />
pair A,B,C,O,H,P,Q,i1,i2,i3,i4;<br />
<br />
//define dots<br />
A=3*dir(50);<br />
B=(0,0);<br />
C=right*2.76481496;<br />
<br />
O=circumcenter(A,B,C);<br />
H=orthocenter(A,B,C);<br />
<br />
i1=2*O-H;<br />
i2=2*i1-O;<br />
i3=2*H-O;<br />
i4=2*i3-H;<br />
//These points are for extending PQ. DO NOT DELETE!<br />
<br />
P=intersectionpoint(i2--i4,A--B);<br />
Q=intersectionpoint(i2--i4,A--C);<br />
<br />
//draw<br />
dot(P);<br />
dot(Q);<br />
draw(P--Q);<br />
dot(A);<br />
dot(B);<br />
dot(C);<br />
dot(O);<br />
dot(H);<br />
draw(A--B--C--cycle);<br />
<br />
//label<br />
label("$A$",A,N);<br />
label("$B$",B,SW);<br />
label("$C$",C,SE);<br />
label("$P$",P,NW);<br />
label("$Q$",Q,NE);<br />
label("$O$",O,N);<br />
label("$H$",H,N);<br />
//change O and H label positions if interfering with other lines to be added<br />
<br />
//further editing: ABCPQOH are the dots to be further used. i1,i2,i3,i4 are for drawing assistence and are not to be used<br />
</asy><br />
<br />
Lemma: <math>H</math> is the reflection of <math>O</math> over the angle bisector of <math>\angle BAC</math> (henceforth 'the' reflection)<br />
<br />
Proof: Let <math>H'</math> be the reflection of <math>O</math>, and let <math>B'</math> be the reflection of <math>B</math>. <br />
<br />
Then reflection takes <math>\angle ABH'</math> to <math>\angle AB'O</math>.<br />
<br />
<math>\Delta ABB'</math> is equilateral, and <math>O</math> lies on the perpendicular bisector of <math>\overline{AB}</math> <br />
<br />
It's well known that <math>O</math> lies strictly inside <math>\Delta ABC</math> (since it's acute), meaning that <math>\angle ABH' = \angle AB'O = 30^{\circ},</math> from which it follows that <math>\overline{BH'} \perp \overline{AC}</math> . Similarly, <math>\overline{CH'} \perp \overline{AB}</math>. Since <math>H'</math> lies on two altitudes, <math>H</math> is the orthocenter, as desired.<br />
<br />
So <math>\overline{OH}</math> is perpendicular to the angle bisector of <math>\angle OAH</math>, which is the same line as the angle bisector of <math>\angle BAC</math>, meaning that <math>\Delta APQ</math> is equilateral. <br />
<br />
Let its side length be <math>s</math>, and let <math>PH=t</math>, where <math>0 < t < s, t \neq s/2</math> because <math>O</math> lies strictly within <math>\angle BAC</math>, as must <math>H</math>, the reflection of <math>O</math>. Also, it's easy to show that if <math>O=H</math> in a general triangle, it's equilateral, and we know <math>\Delta ABC</math> is not equilateral. Hence H is not on the bisector of <math>\angle BAC \implies t \neq s/2</math>. Let <math>\overrightarrow{BH}</math> intersect <math>\overline{AC}</math> at <math>P_B</math>. <br />
<br />
Since <math>\Delta HP_BQ</math> and <math>BP_BA</math> are 30-60-90 triangles, <math>AB=2AP_B=2(s-QP_B)=2(s-HQ/2)=2s-HQ=2s-(s-t)=s+t</math><br />
<br />
Similarly, <math>AC=2s-t</math><br />
<br />
The ratio <math>\frac{[APQ]}{[ABC]-[APQ]}</math> is <math>\frac{AP \cdot AQ}{AB \cdot AC - AP \cdot AQ} = \frac{s^2}{(s+t)(2s-t)-s^2}</math><br />
The denominator equals <math>(1.5s)^2-(.5s-t)^2-s^2</math> where <math>.5s-t</math> can equal any value in <math>(-.5s, .5s)</math> except <math>0</math>. Therefore, the denominator can equal any value in <math>(s^2, 5s^2/4)</math>, and the ratio is any value in <math>\boxed{\left(\frac{4}{5},1\right)}.</math><br />
<br />
Note: It's easy to show that for any point <math>H</math> on <math>\overline{PQ}</math> except the midpoint, Points B and C can be validly defined to make an acute, non-equilateral triangle.<br />
<br />
==Solution 2==<br />
Let <math>J</math> be the farthest point on the circumcircle of <math>\triangle{ABC}</math> from line <math>BC</math>.<br />
Lemma: Line <math>AJ</math>||Line <math>OH</math><br />
Proof: Set <math>b=-\dfrac{1}{2}+i\dfrac{\sqrt{3}}{2}</math> and <math>c=-\dfrac{1}{2}-i\dfrac{\sqrt{3}}{2}</math>, and <math>a</math> on the unit circle. It is well known that <math>o=0</math> and <math>h=a+b+c</math>, so we have <math>h-o=a+b+c=a-1=a-j</math>, so <math>\dfrac{a-j}{h-o}</math> is real and thus the 2 lines are parallel.<br />
<br />
WLOG let <math>A</math> be in the first quadrant. Clearly by the above lemma <math>OH</math> must intersect line <math>BC</math> closer to <math>B</math> than to <math>C</math>. Intersect <math>AJ</math> and <math>BC</math> at <math>D</math> and <math>OH</math> and <math>BC</math> at <math>E</math>. We clearly have <math>0 < \dfrac{\overarc{JC}-\overarc{AB}}{2} = \dfrac{120-\overarc{AC}}{2} = \angle{ADB} = \angle{OEC} < 30 = \angle{OBC}</math>, <math>OH</math> must intersect <math>AB</math>. We also have, letting the intersection of line <math>OH</math> and line <math>AC</math> be <math>Q</math>, and letting intersection of <math>OH</math> and <math>AB</math> be <math>P</math>, <math>\angle{OQA} = \angle{JAB} = \dfrac{\overarc{JB}}{2} = 60</math>. Since <math>\angle{OCA}=\angle{BCA}-\angle{BCO} < 90-30 =\angle{OQA}</math>, and <math>\angle{OQC} = 120>\angle{OAC}</math>, <math>OH</math> also intersects <math>AC</math>. We have <math>\angle{OPA}=\angle{PAJ}=60</math>, so <math>\triangle{APQ}</math> is equilateral. Letting <math>AJ=2x</math>, and letting the foot of the perpendicular from <math>O</math> to <math>AJ</math> be <math>L</math>, we have <math>OL=\sqrt{1-x^{2}}</math>, and since <math>OL</math> is an altitude of <math>\triangle{APQ}</math>, we have <math>[APQ]=\dfrac{OL^{2}\sqrt{3}}{3} = \dfrac{\sqrt{3}(1-x^{2})}{3}</math>. Letting the foot of the perpendicular from <math>A</math> to <math>OJ</math> be <math>K</math>, we have <math>\triangle{JKA}\sim \triangle{JLO}</math> by AA with ratio <math>\dfrac{JA}{JO} = 2x</math>. Therefore, <math>JK = 2x(JL) = 2x^{2}</math>. Letting <math>D</math> be the foot of the altitude from <math>J</math> to <math>BC</math>, we have <math>KD=JD-JK=\dfrac{3}{2}-2x^{2}</math>, since <math>re(B)=re(C) \implies JD=re(j)-(-\dfrac{1}{2})=\dfrac{3}{2}</math>. Thus, since <math>BC=\sqrt{3}</math> we have <math>[ABC]=\dfrac{(\dfrac{3}{2}-2x^{2})(\sqrt{3})}{2} = \dfrac{(3-4x^{2})(\sqrt{3})}{2}</math>, so <math>[PQCB]=[ABC]-[APQ]=\dfrac{(5-8x^{2})(\sqrt{3})}{12}</math>, so <math>\dfrac{[APQ]}{[PQCB]} = \dfrac{4-4x^{2}}{5-8x^{2}} = \dfrac{1}{2}+\dfrac{3}{10-16x^{2}}</math>. We have <math>x=\sin(\dfrac{JOA}{2})</math>, with <math>0<120-2\angle{ACB}=\angle{JOA}<60</math>, so <math>x</math> can be anything in the interval <math>(0, \dfrac{1}{2})</math>. Therefore, the desired range is <math>(\dfrac{4}{5}, 1)</math>.<br />
<br />
Solution by Shaddoll<br />
<br />
==See Also==<br />
<br />
{{USAJMO box|year=2014|num-b=1|num-a=3}}</div>Shaddoll