AoPS Academy
be an acute traingle with 
. Point 
is a foot of altitude through vertex 
. Point 
is a circumcenter of . Prove that areas of quadrilaterals 
and 
are equal.
. 
amount of people stand on coordinates 
where 
. Every person got a water cup and two people are considered to be neighbour if the distance between them is 
. At the first minute, the person standing on coordinates 
got litres of water, and the other 
people's water cup is empty. Every minute, two neighbouring people are chosen that does not have the same amount of water in their water cups, and they equalize the amount of water in their water cups. will not have more than 
litres of water.
such that ![$1+[\sqrt{2n}]~$](http://latex.artofproblemsolving.com/e/6/a/e6aa1bf5d761758196027add39f2e3cd77db1c1c.png)
divides 
.
, ![$[x]$](http://latex.artofproblemsolving.com/b/c/e/bceb7b14e55d33a8bca29b7863ad3cdae95afce4.png)
denotes the largest integer not exceeding . )
be a set of integers (not necessarily positive) such that
with 
; and 
are elements of (possibly equal), then 
also belongs to . is the set of all integers.
and 
. We claim that 
. Assume to the contrary that this is false. Then we can find some prime 
such that 
, 
, and 
. Since 
, 
if and only if 
; since 
, divides neither 
nor 
. From 
, 
or 
. Since 
, 
. Similarly,
, which contradicts 
.
. We note that for any 
in , 
must be in , so 
must be in . It follows that for all 
and 
in , 
. Hence, for all positive integers 
, 
, and , 
. As , the Frobenius coin problem tells us that all sufficiently large positive integers lie in . In other words, for some positive integer 
, all integers larger than or equal to lie in . We may suppose without loss of generality that 
.
be any integer less than . Since 
(from ) and 
, 
and 
lie in , whence 
must lie in as well. Thus, 
, as desired.
![\[m=\gcd \{c^2-d^2:c,d\in S\} \]](http://latex.artofproblemsolving.com/3/f/b/3fbce8ee4e18eebc9b01e6be85a3eb8e19b86b41.png)
is infinite, as it later turns out to be, 
is not well defined. may be a supernatural number. (http://en.wikipedia.org/wiki/Supernatural_numbers) must be assumed to be finite.
would not be well-defined. The 
of an infinite set of integers is perfectly well-defined; it is the largest integer that divides every element of the set. In your case, if you let 
be any nonzero element of 
, you must have 
, so is certainly finite.
shifty if 
(meaning is invariant under shifting by 
).
, then for any 
, ![\[ v^2 - (u^2-x) = (v^2-u^2) + x \in S. \]](http://latex.artofproblemsolving.com/a/9/e/a9e93b29aa7b21432bbbc8fae63985c5dfaa71e8.png)
Since we can easily check that 
and 
we conclude exists a shifty integer. is shifty. Assume for contradiction not. Then for GCD reasons the set of shifty integers must be 
for some 
.![\[ S \subseteq \left\{ x : x^2 \equiv m \pmod d \right\} \]](http://latex.artofproblemsolving.com/d/3/2/d3282c4f5705c412cccbd29920c5e33ee8597fa4.png)
for some fixed , since otherwise if we take any 
with distinct squares modulo , then 
is shifty, which is impossible. as in (a). In that case we need to have ![\[ a^2 \equiv b^2 \equiv (a^2-a)^2 \equiv (b^2-b)^2 \pmod d. \]](http://latex.artofproblemsolving.com/9/f/c/9fc75dcfea5ecef20cdbf57dde00ef8bef2e1e62.png)
Passing to a prime 
, we have the following:
or equivalently 
, either 
or 
.
or 
.
, or 
, we find either 
or 
(even if 
).
or 
, say.
+ z is in S. Thus, we wish to show that we can create all residues 
where a, b are elements given in condition 1., , 
, 
are all distinct mod 
. Then, we show that 
. Since for any elements x, y, z that are in S, we know that + z, let 
and 
and we can span through all the residues.
. Then![\[ x\in S\implies m^2-x \in S \implies n^2-(m^2-x)=x + (n^2-m^2) \in S. \]](http://latex.artofproblemsolving.com/b/0/4/b04e1bb59226a5dba1cdf3ae2292fc30482c289f.png)
Therefore, it suffices to show that we can get any residue mod . From now on, we work fully in mod .
, we can get 
, which is equivalent to just 
mod . Therefore, if 
, then we can also get plus the difference of two elements of 
in . Now, it suffices to show that we cannot have![\[ a^2 \equiv b^2 \equiv (a^2-a)^2 \equiv (b^2-b)^2 \pmod{p} \qquad (\clubsuit)\]](http://latex.artofproblemsolving.com/4/1/a/41ae96752a87bca6af8138db5957740bf62b093d.png)
for a prime , because if this were the case, then any new element we add can only be a multiple of greater; hence we will not get all possible residues. Otherwise, we will get a difference which is relatively prime to , and then we can add this difference over and over to to generate all possible residues.
holds. All equivalences are in mod . Then 
, so 
or 
. Similarly 
or 
. But 
, so 
. Therefore, either 
or 
. But neither of these are possible by condition (a)! Contradiction. This completes the proof.
is easy enough, however 
won't be used 
Let 
. Then, for every 
,![\[ s+ (y^2-x^2) \in S; \quad s+(x^2-y^2) = s- (y^2-x^2) \in S \]](http://latex.artofproblemsolving.com/b/b/a/bbafbe2f9c23c0f717e957dd7e015b18e76ddc20.png)
This will imply the fact that![\[ S = S+(y^2-x^2) \ \forall x,y \in S \]](http://latex.artofproblemsolving.com/9/6/8/968ffa4137fe242c86c62c49b05419fd0e02d935.png)
The Main Point of the Problem (and what makes this a 25+ MOHS.), then 
. We'll apply this again with instead of : as , so![\[ y^2- (x^2-s) \in S \]](http://latex.artofproblemsolving.com/a/8/b/a8bbda86b33badfd04f37e853948e9b5fd4431b9.png)
validating the Claim. 
Let . Then,![\[ s+1 \in S\]](http://latex.artofproblemsolving.com/1/6/a/16ab6866c1e255199bea3cef185ba163da616ac3.png)
(such a simple Claim, is it not?)
This is multiple (tedious) applications of 
(the tedious-ness of this does in fact contribute on why this is my favorite NT problem among my recent sessions. See 
for further exposition.)
in the problem statement, 
and 
are elements of .
![\[ \{b^2-a^2, (a^2-b)^2-b^2, (b^2-a)^2-a^2\} \in \{s_2^2-s_1^2 \mid \ \text{for} \ s_1,s_2 \in S\} \]](http://latex.artofproblemsolving.com/b/9/e/b9e6b1e965817de3cad9e7dcd1107fc6d6928f1b.png)
and we can infer from that![\[ S = S+z \cdot (b^2-a^2); \ S = S+z \cdot (a^2)(a^2-2b); \ S = S+z \cdot (b^2)(b^2-2a) \]](http://latex.artofproblemsolving.com/c/f/8/cf85b428244915b8e7a54a1d397d11dc8c46dcf5.png)
for every 
.
implies 
by 
/
/
.![\[ \gcd(b^2-a^2,a^2(a^2-2b)) = \gcd(b+a,a^2-2b) = g_1 \]](http://latex.artofproblemsolving.com/3/8/6/386f18e093f7eb560c5e1ef7e1f93e6da511518f.png)
applying the above statement with 
and 
yields![\[ S = S+g_1 \]](http://latex.artofproblemsolving.com/d/a/a/daa318c0a75b48889ac963d5063dfc2c0c8858a9.png)
and similarly with 
, we get![\[ S = S+g_1=S+g_2 \]](http://latex.artofproblemsolving.com/f/0/6/f06e9bea91b7aae94dfd6871f18fb91eadda34dd.png)
and 
are prime targets to apply the Lemma in Thirdly (I purposefully avoided another as a placeholder variable for the transitional 
, instead I picked 
from 
.)
, our job is done. To prove that, suppose 
for prime. Then,![\[ p \mid a+b, p \mid a^2-2b \Rightarrow p \mid a^2+2a, b^2-2b. \]](http://latex.artofproblemsolving.com/1/2/e/12e359f57d633fdd7fbeab27fd688ca9870fe6a9.png)
This may not seem like much, but that's the usefulness of having more than one 
s! Doing the same for the other expression,![\[ p \mid a^2-2a, b^2+2b. \]](http://latex.artofproblemsolving.com/4/1/8/41805f92e02a240082740b336cc56e83e2ad49ec.png)
Substracting yields 
--- which means either 
and even or 
which is impossible as . explicitly to prove the computation in Thirdly. 
with 
. have 
we are done. Otherwise are both 
, so taking implies the desired. with , note 
, 
. Thus 
for all integers by this argument. Such observations imply that consists of a set of residues modulo some integer 
. Let 
and be minimal. For any , we claim 
. This is because we must have 
by the minimality of . We claim 
, which suffices. Otherwise, let 
be prime. Let be the given relatively prime elements of . Then 
implies that at least one of 
and 
holds. Since and are relatively prime, we cannot have 
. Note that all elements of are 
modulo . Then we have is one of and 
modulo . The second case is clearly bad, so 
. Similarly 
, which contradicts the given, so we are done.
.
, then from 
we get 
. Then by induction we have 
for 
(*)
,
and 
. Suppose that 
then there exists such that 
![\[ \Leftrightarrow \left\{ \begin{array}{l}
p \mid {a^2} - {b^2}\\
p \mid {({a^2} - a)^2} - {a^2}\\
p \mid{({b^2} - b)^2} - {b^2}
\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}
\left[ \begin{array}{l}
p \mid a - b\\
p \mid a + b
\end{array} \right.\\
\left[ \begin{array}{l}
p \mid {a^2} - 2a\\
p \mid {a^2}
\end{array} \right.\\
\left[ \begin{array}{l}
p \mid {b^2} - 2b\\
p \mid {b^2}
\end{array} \right.
\end{array} \right.\]](http://latex.artofproblemsolving.com/8/7/5/875cdea74967a17dcc59ad319ab2389fa37a4888.png)
But all the cases can happen will lead to a contradiction that 
.
, then there exists 
such that 
by Bezout Lemma
, we lead to 
. We will show the claim by induction
are in 
then 
and from induction, 
is not a perfect square, let it be 
for 
(Since 
)
, means 
and 
from induction, then 
and done!!!
, all residues modulo are in .
are the only residues in with 
. Then for any 
we must have 
. Summing 
is same for each . As 
, so 
. Thus 
and 
(if 
). Now 
. If 
, then 
, forcing 
, contradicting . Thus 
and 
. Then 
. But then for any , either 
or 
, contradiction. 
and 
. By Cauchy-Davenport there 
has cardinality at least 
. But also there is subset of . This forces . We can finish as before. 
, all residues modulo are in . are only residues modulo with 
. Pick a prime dividing 
. As before all are congruent modulo . Thus each 
are congruent modulo . This basically means for any 
, 
is same modulo for any choice of . But by previous claim, we know the residues 
are in (modulo ), forcing 
mod , contradiction. 
. Let 
. We Claim that
This follows by fixing and using induction on 
(by using (b) two times for 
or 
). By our Claim, can be anything modulo , hence 
. 
is dropped):
shifty if (meaning is invariant under shifting by )., then for any , Since we can easily check that and we conclude exists a shifty integer. is shifty then 
is as well (by swapping 
), here is another solution. It's not as efficient but the idea is basically a carbon copy of the technique used in the ELMO problem and I think it's pretty neat: covers all residues modulo 
for any prime and 
. Surprisingly, most of the work is to prove this for 
. Let , and let 
be the set of residues modulo of , so we want to prove that 
. Suppose otherwise, and fix 
, so 
for all 
. As 
varies these are all distinct, hence
Summing both sides, this means that
as 
. Hence it follows that is constant, so 
.
, then we have 
, so 
. But then either divides 
or 
for all , violating the first condition.
, then we have 
. But then 
, so 
, which is a contradiction.. Now, to extend to , the same "sum argument" applied to the set of residues 
, which we will define as 
, implies that
for all 
. But there exists 
such that 
but 
by the case, so if 
then 
, hence we cannot have 
. It follows that 
., forms a complete residue set 
. Then and are shifty, so it follows that covers all of 
, as desired. 
then for any 
we have 
and thus 
Now, if we let 
then for any 
we have 
for any integer . Therefore, if we find 
such that 
then we are done by Bezout's. Suppose
Then the second plus the first is 
. Since 
we have 
Similarly, 
so 
If then odd which violates the second one. Now, so we can switch any with to get from the second one 
and 
, impossible. Therefore we are done.
is odd, and since 
is also in the set and 
. Other elements in the set are clearly 
and 
Then note that 
Similarly 
so 
.
.
similarly 
. Now since 
, by bezout's all integers are then in .
then it follows that 
. contains every residue 
for prime power 
.
, it follows for all . FTSOC suppose not. It must follow that 
for any 
, so can only take on residue . appears. However, it then follows that 
, so either 
or 
.
or , then this contradicts relatively prime . If all residues are 
, then this contradicts relatively prime 
.
is nonzero 
. reaches every residue 
. Shifting by 
repeatedly gives the result.
are elements of , then 
. Indeed, this follows as 
be two elements of that satisfy (a).
.
as 
by the conditions in (a). Furthermore, 
Assume for the sake of contradiction that 
is the common GCD; then it follows 
and 
, so 
. On the other hand, all three terms cannot be even, so this implies . 
that sum to and 
. It follows that if , then 
and 
are both in , which is enough.
such that, for all 
, 
. Notice that showing 
would finish.
. Then we have 
, so 
.
, we find 
.
, they must equal 1, so . Otherwise, we claim either 
or 
equals 1. Note the first expression equals![\[\gcd(a^2-b^2,a^2-2b) = \gcd((a+b)(a-b), b(b-2)) = \gcd((a+b)(a-b),b-2),\]](http://latex.artofproblemsolving.com/1/1/7/1178021b6bdc0659ca5d5ebaf939a96eda8f0627.png)
, the expression equals 
. Similarily, the second expression equals 
, so if neither expression equals 1, 
, contradiction. is also in , Bezout's on the determined coprime pair tells us . 
be called translater if 
I claim there exists a translater:
we have that 
and thus, 
and thus, 
is a translater. for some 
We have that the set 
Hence, 
Let 
We now have the following:
or 
However, in either cases, this is a contradiction.
which only satisfies for the set 
satisfying
Prove
operations will yield a positive operation: making it similar to a Euclidean Algorithm step of 
instead of 
--- which doesn't seem like a groundbreaking observation but simplifies the matter of interpreting the values of![\[ S_{k-\text{modified}} = \{k^2- s \mid \ \text{for} \ s \in S \} \]](http://latex.artofproblemsolving.com/c/9/0/c90e23e71d1bf688c54f75643c8998c48526cef2.png)
(explained more in Motivation, as usual. Find the 
hidden for the hint.)
For those wondering 
,
'
call 
nice if
.
Playing with 
,
(this will be further referred as 
as I'm lazy.) However, why 
should be equal to 
,
,
--- and then I saw that 
yields all elements of 
.
and 
.
It should come as no surprise that I had a more pleasant experience on handling ![\[ a^2-b, a^2-a, b^2-a, b^2-b \]](http://latex.artofproblemsolving.com/3/b/d/3bd36fed1131f4ef566c7e3515d803acbadbcdcb.png)
elementarily formed numbers, since there's a guarantee that when we operate on 
be formed. After forming that number, it's also in our best interests to come up with close numbers to it; and theoretically proceed from a basis of four numbers to prove ![\[ 18,20,42,44 \in S, \ \text{with the addition of} \ 7^2-20 = 29 \in S \]](http://latex.artofproblemsolving.com/2/b/b/2bbabeeac4e4cba0775894fc7e340ac2a7e3bd39.png)
are far apart from each other. With ![\[ 4,6,20,22 \in S\]](http://latex.artofproblemsolving.com/8/b/c/8bcf4450947b109979b013e069872afc5b6c9d94.png)
with 
.
.
,
:![\[ 4^2- 5 = 11 \in S, \ 3^2-11 = -2 \in S\]](http://latex.artofproblemsolving.com/5/0/9/5095533d43de2b66a2b4852d30af52c8c130b7e8.png)
and doing that enabled me to go further down to ![\[ (-2)^2-5 = -1 \in S, \ (-1)^2-(-1) = 2 \in S, \ 2^2-3 = 1 \in S. \]](http://latex.artofproblemsolving.com/7/e/2/7e2eab1cfe0ba58a53f6a80d696321f90b2744bf.png)
and then we get the legendary duo of 
--- and this opened my mind to the possibility of 
the outcome of the procedure![\[ x,y \in S \Rightarrow x^2-y \in S\]](http://latex.artofproblemsolving.com/2/9/b/29b732540648a32951172250f4c379c7fae3586e.png)
by bounding the values of either 
viable Solution.)
.
,
except when 
--- so the pair 
is not a nice pair; and try to prove that 
!
,
Hint 2: reflection to 
and 
.
will solve the problem.
While the 
strat works for small 
in an effective way, ![\[ x^2-y \in S. \]](http://latex.artofproblemsolving.com/e/5/5/e55eab040caf942dc4f67a14a3295cf77265d9b4.png)
.![\[ x^2-(x^2-1) = 1 \in S_{x,x^2-1} \]](http://latex.artofproblemsolving.com/b/b/d/bbde6e0104ff8ba5056b5abf3235b27005781fe3.png)
and we immediately win --- with the condition that 
(or, in more simple terms, 
.
with each other, and applying the same method of![\[ (x-2)^2-(x^2-3) = -4x+7 \in S\]](http://latex.artofproblemsolving.com/0/2/b/02b1d268a187a82c90674891337db78a1b0fa8cd.png)
yielded bleak prospects for explicitly size-bounding a resulting 
!![\[ \text{there does not exist} \ p \ \text{prime so that} \ a \equiv 2 \pmod p \ \text{and} \ b \equiv 2 \pmod p.\]](http://latex.artofproblemsolving.com/e/9/0/e90ad9de11edc0edfe18dfc2d54cfc79a96ad4c2.png)
Since the terms 
and the term 
seems so different from each other, I tried forming the sets![\[ S^{\text{[2]}} = \{s^2 \mid s \in S\}, \quad S^{\text{[1]}} = S \]](http://latex.artofproblemsolving.com/9/b/0/9b0852567fe2e34340d69a7dfa0eb59f383efc12.png)
to differentiate them explicitly. This helped me see the error in my ways: I've been trying so hard to take ![$x,y \in S^{[2]}$](http://latex.artofproblemsolving.com/f/0/6/f066c93bfded998165831bf63191c80296507df1.png)
such as 
on 
instead of taking, say,![\[ (x,y) = (5,7^2-5) \Rightarrow 5^2-(7^2-5) \in S \]](http://latex.artofproblemsolving.com/5/f/0/5f027fc78f2cb745860ece85a9b5b7c805819451.png)
this also helped me realize that 
doesn't help as it returns 
,
(not really) the node 
in the number line twice with respect to the point 
.![\[\begin{tabular}{p{12cm}}
Our goal isn't necessarily to create $1 \in S$, but to make some shift equal to 1!
\end{tabular} \\ \]](http://latex.artofproblemsolving.com/6/4/e/64e4647998c068ff1d510aa6c986691b56b3fc45.png)
this mirrored the Euclidean Algorithm more than anything else, but there's the elusive challenge of applying ![\[ s_1,s_2 \in S \Rightarrow S = S+s_2^2-s_1^2; \]](http://latex.artofproblemsolving.com/3/b/3/3b3d2aacfc88f71cb44b45d33d313e627ab9cd2d.png)
what if we could make some 
appear in the substraction of squares? To be exact, this is just a matter of factorization, but isn't that all Hensel's Lemma on 
do?
After doing some computation work on the ![\[ \gcd(b^2-a^2, (a^2-b)^2-b^2) = \text{not exactly 1} \]](http://latex.artofproblemsolving.com/b/6/d/b6d31cc96e166cdbe8d0a5efb194ef58c7623f86.png)
due to the existence of some pesky 
not canceling out with 
.![\[ p \mid a+b, p \mid a^2+2a, \ \text{and} \ p \mid b^2-2b. \]](http://latex.artofproblemsolving.com/f/b/7/fb7ddf787022b7741b61aa1dae9509e35c643804.png)
As 
is out of the question, this brought a suspicion: what if![\[ a \equiv -2 \ \text{mod} \ p, \ \text{and} \ b \equiv 2 \ \text{mod} \ p? \]](http://latex.artofproblemsolving.com/4/6/c/46cb7ea28a53fcf071e41f43ec3ac537b27bceb8.png)
For example, I tried analyzing 
where 
are divisible by 
.
,![\[ S_{5,16} = S_{a,a^2-b} \subseteq S_{5,9} \]](http://latex.artofproblemsolving.com/c/f/0/cf05dccf8a211a6f76667fe9ef2a4729aa84c59a.png)
and that finishes the problem, since 
is a nice pair.
is a bit scary, but they can be factored as well, right? Also, there are four elementary formed terms of the original set 
that can be compared with 
both complement each other towards a happy ending.![\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]](http://latex.artofproblemsolving.com/8/4/2/842413e566043c96b7a8f2300401b08af9d8ba48.png)
Final Comments: This might seem like a long thread; but in total, I don't think this to be a scary problem.![\[ (a^2-a)^2-(b^2-b) \in S \]](http://latex.artofproblemsolving.com/8/7/4/87411bc75ab81e4a413d802d5ff67afde74fb2e1.png)
reflection among the negatives might carve a quick way into the Solution.
be positive integers. Then there exists integers 
such that![\[\sum_{i=1}^{m} a_ix_i = \gcd(a_1, a_2, ..., a_m)\]](http://latex.artofproblemsolving.com/9/8/f/98fe94ca90cc40bdb6cfcae0a9ca29764e97a29c.png)
Also, 
is the least positive integer satisfying this property.
.
,
.
for all integers 
and 
.
.
.
and 
.
such that 
,
,
.
was irrelevant. But then I realized if all numbers of 
and noticing that we are just through.
elements? I just applied it 
is in 
,
,
.
,
,![$(a^2-b^2) + [(a^2-b^2) + x] = 2(a^2-b^2)+x \in S$](http://latex.artofproblemsolving.com/3/a/a/3aa1873e430baa39aca938296577d66e491d7b2e.png)
,![$(a^2-b^2) + [(a^2-b^2)+ x] = 3(a^2-b^2) + x \in S$](http://latex.artofproblemsolving.com/8/c/0/8c0264fdfa2939f7dc5b0104939d641851de0b54.png)
,
for all 
.
,
,
,
.
,
,
and any 
,
does the trick. Thus, we have that 
for all integers 
be elements of 
is in 
is in 
and 
.
,![$$x + k\gcd(a^2-b^2, c^2-d^2) = x + k[(a^2-b^2)r + (c^2-d^2)s] = [x + (a^2-b^2)(rk)] + (c^2-d^2)(sk) \in S,$$](http://latex.artofproblemsolving.com/d/6/f/d6f3137925fded664605d1affd5a0e2359a643b5.png)
as desired. 
,
.
,
.
Note that 
,
,
.
Similarly, note that 
Note that 
,
Thus, 
Thus, by the second claim, we have that for any integer 
and 
Now, note that 
since if a prime 
,
and 
,
Now, note that for any integer 
so since 
,![\begin{align*}
S &\ni x + \gcd(b-2, b^2-a^2)(sk) \\
&= a + \gcd(a-2, b^2-a^2)(rk) + \gcd(b-2, b^2-a^2)(sk) \\
&= a + k[r\gcd(a-2, b^2-a^2) + s\gcd(b-2, b^2-a^2)] \\
&= a+k,
\end{align*}](http://latex.artofproblemsolving.com/4/3/4/434e2697f6b4d0648f795886d899c2ded3e5e0f9.png)
so 
for any integer 
,
,