AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
such that
for all real numbers 
such that 
.
such that for all 
,![\[f(x+yf(x))+y = xy + f(x+y).\]](http://latex.artofproblemsolving.com/c/f/3/cf3d20a041c27244e90876119b4568b7a3e13c03.png)
be an integer, let 
be a set of 
elements, and let 
, be distinct subsets of of size at least 
such that ![\[ A_i \cap A_j \not= \emptyset, A_i \cap A_k \not= \emptyset, A_j \cap A_k \not= \emptyset, \;\textrm{imply}\ \;A_i \cap A_j \cap A_k \not= \emptyset \ .\]](http://latex.artofproblemsolving.com/c/1/1/c113f5cdce00dfec6714c382a8e1bc74f188f025.png)
Show that 
.
such that 
or 
, there exist integers![\[
1 \leq a_1 < a_2 < \cdots < a_{(p-1)/2} < p
\]](http://latex.artofproblemsolving.com/6/8/e/68e3d73edec43b2cc480832adf23bbbb5f4c7bee.png)
such that![\[
\prod_{\substack{1 \leq i < j \leq (p-1)/2}} (a_i + a_j)^2 \equiv 1 \pmod{p}.
\]](http://latex.artofproblemsolving.com/2/9/e/29edf6ab8cee2a526e7753a140c5a291e987856a.png)
denote the maximum number of 
-tetrominoes that can be placed on an 
board such that each -tetromino covers at least one cell that is not covered by any other -tetromino.
such that![\[
f(N) \leq cN^2
\]](http://latex.artofproblemsolving.com/7/4/8/748109c3d63203f9a67a167434e10a909f38e83f.png)
for all positive integers 
.
be a graph colored using 
colors. We say that a vertex is forced if it has neighbors in all the other 
colors.
-regular graph , there exists a coloring using 
colors such that at least 
of the colors have a forced vertex of that color.
vertices of the same color may be adjacent.
, 
, 
, ... be an infinite sequence of real numbers satisfying the equation 
for all 
, where and are two different positive reals., , , ... be bounded?
be an isosceles triangle with 
. Let 
be a point on 
. Let 
be a point inside the triangle such that 
and![\[
CL \cdot BD = BL \cdot CD.
\]](http://latex.artofproblemsolving.com/1/6/7/16771838c95f86e92f79b8d049e46ab473e6287d.png)
Prove that the circumcenter of triangle 
lies on line 
.
triangle with 
. We take 
, 
point on AC, AB respectively such that 
, 
. 
, 
lines intersect at point 
. If 
, find 
of functions by 
for 
. Prove that each 
is a polynomial with integer coefficients.
be a convex pentagon such that![\[ \angle BAC = \angle CAD = \angle DAE\qquad \text{and}\qquad \angle ABC = \angle ACD = \angle ADE.
\]](http://latex.artofproblemsolving.com/d/3/d/d3d9a82f4318190298a8f008d417a364e03f1fca.png)
The diagonals 
and 
meet at 
. Prove that the line 
bisects the side 
.
, 
, and 
are fixed on a line in this order. Let 
be a circle passing through and whose center does not lie on the line 
. Denote by the intersection of the tangents to at and . Suppose meets the segment 
at 
. Prove that the intersection of the bisector of 
and the line does not depend on the choice of .
be positive real numbers such that 
. Prove that
.
questions, each with 
answer choices. A participant who answers all questions correctly will receive a gift. To ensure that at least one member of my family answers all questions correctly, how many family members need to take the quiz?
, each of our twin children also begins to have twins every year. If this pattern continues, how many years will it take for my family to grow large enough to have the required number of members to guarantee winning the quiz gift?
be positive integers with product 
where 
is an odd positive integer. Prove that 
then 
for all 
and 
. Let 
then it suffices to prove 
then 
, otherwise WLOG 
then 
so 
\for all 
, a contradiction to 
.
so 
or 
. Thus, 
This follows 
or 
. Thus, the only possible prime divisor of 
is 
.
. Indeed, if 
then 
and 
. Since and 
so 
.
. Since is odd so there exists 
. Hence 
.
then there exists 
. Hence, .
. We follow 
, as desired.
. So, we can replace the 
as 
for all 
. Let 
. Also, 
.
.
.
or 
or it suffices to show 
.
such that 
.
such that 
, then 
. So, for every 
, 
. So, 
for all 
. But we had 
, so there is no such 
such that . 
.
, 
.
. If we take the product over all , we get
As 
, 
. Now as ,we get is even. But we were given that is odd which gives us a contradiction.
such that . So, 
or 
.
, we are done, so we need to consider the case in which 
that implies 
for 
.
such that is even, then is also even. So, 
, which would make all other 
also to be even which contradicts the fact that . So, we get all 
are odd. So, 
., 
. So, 
. we get 
. and as is odd, 
. So, 
.
where 
for all to be odd.
such that 
and 
, it suffices to prove that 
.
such that 
and 
.
such that 
, contradiction!
and this shows that is odd!)
as 
, and set 
Clearly 
.
, so 
To prove the given inequality, we need to show 
; we claim that 
is relatively prime of each of the 's. To see this, note that if there a and a prime 
so that and 
, then 
, and since 
, we have 
, implying that divides each of the 's. This contradicts .
, we have 
Multiplying these congruences for , and noting that is odd we have 
But since is relatively prime to 
, this implies 
, as required. 
, and write 
for positive integers 
with 
. Then ![\[\gcd(a_1^n + P, \ldots, a_n^n + P) = d^n \gcd(b_1^n + Q, \ldots, b_n^n + Q)\]](http://latex.artofproblemsolving.com/c/b/0/cb00e3a967bc6aa05aa5e7aab2aa40d2f0643e49.png)
where 
. Hence it suffices to show ![\[D := \gcd(b_1^n + Q, \ldots, b_n^n + Q) \le 2.\]](http://latex.artofproblemsolving.com/e/7/0/e70d3916a978c7e53ab7b16175312a38e53c10b3.png)
To do this, write ![\[b_1^n \equiv b_2^n \equiv \ldots \equiv b_n^n \equiv -Q \pmod{D}.\]](http://latex.artofproblemsolving.com/0/d/e/0de9d0b6dfdc6972f1eadbb98eee6756fbf57699.png)
Suppose some prime divides both 
and . Then ![\[b_1^n \equiv b_2^n \equiv \ldots \equiv b_n^n \equiv -Q \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/c/c/3/cc3d43ebd649404e153174b9846377733e5634b3.png)
so 
, contradicting . Thus 
. But ![\[Q^n = b_1^nb_2^n\ldots b_n^n \equiv (-Q)^n \pmod{D}\]](http://latex.artofproblemsolving.com/1/6/f/16f169a1fdbd1aa042925d4055675c2837808dd8.png)
so 
(since is odd). This is enough to force 
, i.e. 
, as desired.
, we can divide out by 
from both sides since every term in the LHS is of degree . So assume 
, then we want to show![\[ d:=\gcd(a_1^n + P, a_2^n+P, \ldots, a_n^n + P) \le 2. \]](http://latex.artofproblemsolving.com/0/b/5/0b512fb674d0c1a07b1489fc9a5568254a91a502.png)
We have 
by Euclid, so![\[ -a_1a_2\cdots a_n \equiv a_1^n \equiv a_2^n \equiv \cdots \equiv a_n^n \pmod{d}. \]](http://latex.artofproblemsolving.com/a/7/7/a77615ce8f6856cf2222d62a98f45b75a9a24c7f.png)
Multiplying together each of the above relations containing 
, we get![\[ (-a_1a_2\cdots a_n)^n \equiv a_1^na_2^n\cdots a_n^n \pmod{d} \implies 2(a_1a_2\cdots a_n)^n \equiv 0 \pmod{d} \]](http://latex.artofproblemsolving.com/d/6/b/d6b71e436a582f171e2ed13fec2dc67c3a2055fc.png)
since is odd. existed s.t. 
and 
. Then there must exist some 
such that 
, otherwise 
. We know 
, so 
. But 
, so 
, so 
, which is a contradiction since we assumed 
. There was nothing special about , so 
for all 
. In particular, 
. So we can divide by 
on both sides to get 
, so 
.
be positive integers with product where is an odd positive integer. Prove that 
.Hence 
for some .Hence 
where 
.Thus we have to show ![\[d^n\cdot \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)=\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\leq
\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\leq 2\gcd(a_1,\dots, a_n)^n=2d^n\cdot \gcd(b_1,\dots, b_n)^n\]](http://latex.artofproblemsolving.com/f/2/2/f228a1d7dc7534af17b6bfcaf20a2bf0e5c477b8.png)
![\[\implies \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)\leq 2\gcd(b_1,\dots, b_n)^n =2\]](http://latex.artofproblemsolving.com/8/e/4/8e46dfcf669c47ff5ef18956d561f63e865743e6.png)
.Since 
Now let 
be a prime.Then ![\[-Q\equiv b_1^n\equiv b_2^n\cdots \equiv b_n^n\pmod p\]](http://latex.artofproblemsolving.com/d/d/2/dd2ca477535b3d6ac79055428e866911335330c2.png)
![\[(b_1^n)(b_2^n)\cdots (b_n^n)\equiv (-Q)^n\pmod p \implies Q^n\equiv -Q^n\pmod p\implies 2Q^n\equiv 0\pmod p\]](http://latex.artofproblemsolving.com/7/e/f/7ef5e9d25f555b366a180405568e21de5313c3a0.png)
.Now if 
.Then 
a contradiction!Thus .Then if 
.Clearly all are odd.Clearly not all 
otherwise 
.Similarly not all 
.Thus there are 
such that 
and 
.But then 
again a contradiction.Hence 
as desired
Then let for each . We want to show that 
dividing each of 
Then, we must have 
Multiplying over all gives 
for any 
If there exists with 
, then 
for all , contradiction. Thus, , and we conclude. 
; then we wish to show that if 
divides all of the 
, then 
. Write down all the equations of the form 
. Note that cannot share a prime factor with any of the , since then that prime would divide all the . Now multiplying together all these equations gives 
and we're done.
; from here, FTSOC assume that there exists some odd prime dividing all of 
. Then, we see that if one is a multiple of , then is a multiple of which would force every other 
to be a multiple of and violate the condition. Hence, we have 
. Though, multiplying every equation gives us that 
modulo which upon dividing both sides by 
(allowed as it is not a multiple of ) gives that 
which obviously is impossible.
be the 
and write 
.
. Let P' denote the product 
. What is left to prove is that 
. Clearly 
is relatively prime to each 
since otherwise a commmon divisor would divide the remaining 
.
and if we multiply them we get 
(since n is odd). Hence divides 
but since and P are relatively prime this implies that 
and hence 
doesn't change anything, hence WLOG let 
, so the inequality becomes:
whenever .
divide the gcd. Suppose FTSOC that a prime does divide the gcd. Clearly cannot divide all of 
. Now suppose divides some of these numbers, so 
. But there exists an with , which means 
: contradiction. Hence divides none of . Then it is necessary to have 
for all . Since is odd, multiplying these congruences yields 
. But since 
, this gives 
, which is impossible since 
. Hence proved. does not divide the gcd. Suppose FTSOC that 
for all . As with before, since not all of can be even, none of them can be even. Further, observe that since is odd, 
. are congruent to 
, then their product is as well and thus 
, contradiction. Similarly not all of the are congruent to 
. But then picking such that 
and 
implies that 
, so they cannot both equal zero: contradiction.. 
and 
because 
So we have that 
,
Showing that 
for any prime 
we have that 
so 
and 
(
for any 
We have * because 
.
is odd so 
and 
so 
for any 
is even, so we achieve a contradiction thus 
in this final case, so we are done.
.
,
now divides both terms.
.
for each 
.
where we let 
.
.
for some 
.
,
but since 
for all 
However, since 
for all 
,
,
,
.
First, we prove that 
does not divide the LHS. Note that at least one of the 
while another is 
,
,
is odd
.
.
so 
.
,
.
as the largest integer 
.
and there exists 
,
for 
.
where 
and 
.
.
so cancelling 
on both sides, we obtain 
Since the inequality still holds equivalently when 
,
Consider a prime 
for some 
.
for all primes that divide one of 
to be true, we must have 
This implies that 
or 
We note that 
,
,
,
,
for some 
as 
.
.
.
for 
and 
such that 
(meaning one of them is 
)
and 
at the same time, which is impossible.
,
,
,
,
(since 
,
or 
,
and 
the problem becomes prove that 
.
.
for all 
then by taking the product over all 
or 
,
or 
so we are finished
,
.
so we want to prove 
Now suppose we have a power of a prime 
such that 
,
and since they are coprime we must have 
.
and 
,
which means
If 
is relatively prime to 
.
we get 
.
is 
is not relatively prime to 
then since we know this holds for every pair of 
,
.
,
so 
and no higher powers of 2 is achievable.
then there exists 
such that 
which means every integer in the sequence must be the same modulo 
.
,
,
and no higher powers of 
.
.
,
because 
,
.
,
for all 
,
,
,
but this means that 
.
for all 
for all 
,
,
.
,
.
.
is a power of 2.
have a common odd prime factor 
.
Taking the cyclic product, 
But now, for any 
So 
have the common factor 
.
.
,
,
.
.
,
.
.
,
,
,
for some integer 
.
till 
,
.
,
.
and therefore 
![\[\epsilon=gcd(a_1,a_2,\dots,a_n)\]](http://latex.artofproblemsolving.com/0/0/0/0005227e91e1e502bef8ec9c1f89a4ae47141131.png)
which leads us to a simplification through letting 
as: ![\[gcd(a_1^n+P,a_2^n+P,\dots,a_n^n+P)=gcd\left(\epsilon^n b_1^n+\epsilon^n \prod_{i=1}^{n} b_i, \epsilon^n b_2^n+\epsilon^n \prod_{i=1}^{n} b_i, \dots, \epsilon^n b_n^n+\epsilon^n \prod_{i=1}^{n} b_i\right)\]](http://latex.artofproblemsolving.com/a/2/8/a288f764784e0abd3009fe18c3828da8bbbb0f64.png)
![\[=\epsilon^n gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right)\]](http://latex.artofproblemsolving.com/8/d/0/8d0ce9d00973659eab08fd6309dd12bcdcbc2f73.png)
by basic simplification of greatest common divisor function. Now basically our original statement is equivalent to proving that for 
we have that,![\[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right) \le 2 \ \ \ \ \ \ \ (1)\]](http://latex.artofproblemsolving.com/e/e/b/eeb0b03a5c841c67356ee078bb632ddc46471bfb.png)
considering some prime 
such that 
holding for each 
for any 
immediately consider all the other 
type statements which would give us 
by Euclid's Lemma again, and finally 
.![\[b_1^n \equiv b_2^n \equiv \dots \equiv b_n^n \equiv -\prod_{j=1}^{n}b_j \ (mod \ p)\]](http://latex.artofproblemsolving.com/9/c/1/9c126d97405c5708d1690678126a8de521af5720.png)
and if we take product of all the individual statements, ![\[\left(\prod_{i=1}^{n}b_i\right)^n \equiv \left(-\prod_{i=1}^{n}b_i\right)^n \ (mod \ p) \implies 2\left(\prod_{i=1}^{n}b_i\right) \equiv 0 \ (mod \ p)\]](http://latex.artofproblemsolving.com/7/1/c/71c2309ac46ee4ba3cd50c63d1c0414763d1bf38.png)
due to the fact that ![\[p \mid 2\left(\prod_{i=1}^{n}b_i\right) \implies p \mid \left(\prod_{i=1}^{n}b_i\right)\]](http://latex.artofproblemsolving.com/2/d/1/2d1d64768230e4a963b68ea3009077a1ff8bf95c.png)
but by consecutive Euclid's Lemma application we must have that ![\[4 \mid \left(b_j^n+\prod_{i=1}^{n} b_i\right) \ \forall j\]](http://latex.artofproblemsolving.com/0/0/2/002cda18e492047be63183a83e04026880787b28.png)
now if any 
for some ![\[4 \mid b_j^n+\prod_{i=1}^{n}b_i\]](http://latex.artofproblemsolving.com/2/4/6/2465e77536bcf141d24e3421ace98ef3f52ed4b0.png)
such that 
gives us 
and again contradicts the ![\[\prod_{i=1}^{n}b_i \equiv 1 \ (mod \ 4)\]](http://latex.artofproblemsolving.com/e/4/8/e48c004ba2c1f7efe4280153397b69fcfcc8fe7d.png)
then we have 
for each 
since 
for any ![\[1 \equiv \prod_{i=1}^{n}b_i \equiv (-1)^n \equiv (-1) \ (mod \ 4)\]](http://latex.artofproblemsolving.com/8/a/0/8a079a0c9b454f69f320115d6c182a45ee713190.png)
contradicting our assumption.![\[\prod_{i=1}^{n}b_i \equiv (-1) \ (mod \ 4)\]](http://latex.artofproblemsolving.com/3/9/c/39cc7f2d040b7869c9344ccb0eb4767de57e936a.png)
in which case 
for each 
when we combine the following facts:
Thus we have that, ![\[(-1) \equiv \prod_{i=1}^{n}b_i \equiv 1^n \equiv 1 \ (mod \ 4)\]](http://latex.artofproblemsolving.com/b/e/2/be23b0659fec952a5c5cf3eb9995c7000d89c81c.png)
which contradicts our assumption again. Hence we have covered all possible cases and deduced that first, ![\[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right)=2^a\]](http://latex.artofproblemsolving.com/c/e/f/cefa417227eaefe41115dd6240c8a9f3ba74be12.png)
for some 
and thus ![\[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right) \mid 2\]](http://latex.artofproblemsolving.com/c/4/0/c40eb3c38ebc4d58ce4b989403089725e8328c74.png)
which in combination with 
gives us our required 
and thus we are done. 
until their GCD is 
.
for all ![\[-P^n = (-P)^n \equiv a_1^n a_2^n \dots a_n^n = P^n \pmod{k}.\]](http://latex.artofproblemsolving.com/4/f/1/4f1b33e7486aa3d7e8cd6895427c2dd06f0d47cd.png)
If 
which is a contradiction. Therefore we can divide both sides by 
,
,
and 
so that it suffices to prove 
as then 
To this end, suppose that an odd prime 
for all 
,![\[Q^n \equiv x_1^n \dotsm x_n^n \equiv \underbrace{(-Q) \dotsm (-Q)}_{n \text{ times}} \equiv -Q^n \pmod{p}.\]](http://latex.artofproblemsolving.com/0/1/2/01219478ed7f0bfec250663390beb15847557603.png)
This implies that 
for some 
.
case, thankfully it's pretty trivial
.
,
.
we have![\[\gcd(a_1^n + P, \dots, a_n^n + P) = d^n \gcd(b_1^n + Q, \dots, b_n^n + Q)\]](http://latex.artofproblemsolving.com/c/2/9/c29edf7e1aeb7800ee393a200d0e5d5c8fa59a8e.png)
and![\[2d^n = 2\gcd(a_1,\dots, a_n)^n\]](http://latex.artofproblemsolving.com/7/6/c/76cfef37322df722c60a620bfeba5bf7d79814b4.png)
Then note,![\[\gcd(a_1^n + P, \dots, a_n^n + P) \le 2\gcd(a_1,\dots, a_n)^n \iff \gcd(b_1^n + Q, \dots, b_n^n + Q) \le 2\]](http://latex.artofproblemsolving.com/b/f/6/bf690762ba5029bbdf45110c3d46d0021d056cd0.png)
.
then note that all 
.
.
,![\[4\mid b_1^n + Q = b_1 \left(b_1^{n-1}+\frac{Q}{b_1}\right)\]](http://latex.artofproblemsolving.com/d/2/d/d2d12d0cc92856e9a9c9acda03dd07c32fa14484.png)
Since 
.
.![\[4 \mid b_i^n + Q = b_i \left(b_i^{n-1}+\frac{Q}{b_i}\right)\]](http://latex.artofproblemsolving.com/3/b/a/3bae7d515c09523616b94e5ea1f341694acb7fb4.png)
Since 
.
in this product, which is a clear contradiction. Similarly, we have a contradiction when 
which implies that 
.
note,![\[p\mid b_i^n + Q = b_i(b_i^{n-1}+\frac{Q}{b_i})\]](http://latex.artofproblemsolving.com/5/3/2/532d782433d6ceb2006c47ba41cfb9dfa61d66af.png)
If 
.
which is a clear contradiction. Thus, 
or in other words, 
for all ![\[Q^{n-1} \equiv (-1)^n \frac{Q^n}{Q} = -Q^{n-1} \pmod{p}\]](http://latex.artofproblemsolving.com/7/b/a/7ba3db2f6862f62b9bfcf4b7d2651c1d7abec386.png)
since 
which finishes the proof.
,
,
,
,
.
It suffices to prove that 
.
.
then 
for every 
,
.
.
This forces 
,
which would imply that 
,
,
.
.
Indeed, note that 
.
.
.
such that 
.
(by definition), we have 
,
.
If there doesn’t exist such a prime, then the 
.
since both sides are homogeneous with order 
.
for 
.
and hence 
.
and hence 
for all 
Now, assume that there exists some prime 
Thus, we have that 
However, this implies that 
and so 
which means that 
However, we clearly can't have that 
or else this implies that 
Hence, 
which is a contradiction.
Assume that 
we will prove that 
we see that 
which implies that 