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.
, so that the number 
is a prime.
board, a nonnegative real number is written in such a way that the sum of the numbers in each row is equal to 
, and the sum of the numbers in each column is equal to . Define 
to be the largest value in row 
, and let 
. Similarly, define 
to be the largest value in column , and let 
.
?
we consider a 
rectangular frame, consisting of the 
boundary squares of a rectangle.
for which Renate has a winning strategy.
cats consisting of five different breeds. He records the number of cats of each breed and after multiplying these five numbers he obtains the number 
. How many cats of each breed does he have?
, 
is a perfect square.
, let 
be all positive integers smaller than that are coprime to . Find all 
such that 
for all 
is the largest positive integer that divides both 
and 
. Integers and are coprime if 
.
be an integer. In a configuration of an 
board, each of the 
cells contains an arrow, either pointing up, down, left, or right. Given a starting configuration, Turbo the snail starts in one of the cells of the board and travels from cell to cell. In each move, Turbo moves one square unit in the direction indicated by the arrow in her cell (possibly leaving the board). After each move, the arrows in all of the cells rotate 
counterclockwise. We call a cell good if, starting from that cell, Turbo visits each cell of the board exactly once, without leaving the board, and returns to her initial cell at the end. Determine, in terms of , the maximum number of good cells over all possible starting configurations.
classes and 
student. We know that in this school every two students have attended exactly in one common class. Also due to smallness of school each class has less than students. If 
is not a perfect square, prove that there exist a student that has attended in at least 
classes.
, prove that there exists a positive integer 
, such that for any integer 
, can be expressed by a sum of positive integers 
's as![\[n=a_1+a_2+\dots+a_m,\]](http://latex.artofproblemsolving.com/6/c/2/6c2a979a5ff6c40bf2d7152c8c32088fc36f848b.png)
where 
, 
, 
, 
and 
.
where is an odd integer. Let 
be a function defined on 
taking values in 
such that
for all 
for all 
; b) 
identical-looking coins in a circle. It is known that exactly two of them are fake. Real coins weigh the same, fake ones too, but they are lighter than the real ones. How can you determine in three weighings on a cup scale without weights whether there are fake coins lying nearby or not??
and 
.![\[P=\frac{1}{5-2a}+\frac{1}{5-2b}+\frac{1}{5-2c}.\]](http://latex.artofproblemsolving.com/c/3/7/c3708768a84c2bbb1e4fae502a9bb1e92cb13d02.png)
and 
Prove that
by 
,
for every positive integer 
leave distinct remainders when divided by 
.
we have these
is odd, => 
is odd for every natural 
leave 
remainder when divided by 
divisible by 
leave 
remainder when divided by 
is not equal to 
for 
divisible by 
=> contradiction
.
is sufficient to determine 
modulo 
.
for convenience (note the recursion still works from 
to 
,
and furthermore that 
.
.
.
.
so we have 
.
.
utilizing the fact that 
so 
as they are both odd. Thus it follows by induction on 
is the same across all values of ![\[f(3^{M+1}) - f(2 \cdot 3^M) \equiv f(2 \cdot 3^M) - f(3^M) \equiv f(3^M) \pmod{3^{M+2}}\]](http://latex.artofproblemsolving.com/4/b/6/4b64215bdbe4a55a4789067cb38fb458f74452b6.png)
,
.
our induction is complete.
form a complete residue system modulo 
.
.
that 
.
.
,
modulo 
.
so we are done.
is the only thing you need to see and from then on its just details.
to be such that 
and 
.
such that 
and 
.
such that 
and 
.
we have 
(i.e. 
.
.
and we have 
where 
therefore the problem statement holds for 
.
therefore 
from proposition (2). Therefore it is clear that 
.
and we have 
.
.
is distinct mod 
when 
.
.
.
and 
lining up the terms. When you do this out the notation makes a lot more sense, trust me.)
we can separate 
into three groups all of whose elements correspond to 
.
.
.
takes on all of the odd integers from 
.
![\[v_3(2^{\phi(3^{k+1})}-1)=v_3(4^{3^k}-1)=k+1\]](http://latex.artofproblemsolving.com/6/3/f/63f63ce8eea416b7bb66f25ea6692928c8cd0c10.png)
via lifting the exponent. Therefore 
henceforth 
but 
.
where 
.
we arrive at ![\[f_{k+1}(x_1+(n+1)\cdot 3^k)-f_{k+1}(x_1+n3^k)=z3^k\]](http://latex.artofproblemsolving.com/9/b/1/9b1deedbfa133a6134e278f6170f8ac65d4b59ba.png)
from which we can derive ![\[f_{k+1}\left(x+a\cdot 3^k\right)-f_{k+1}\left(x+b\cdot 3^k\right)\equiv (a-b)3^k\pmod{3^{k+1}}\]](http://latex.artofproblemsolving.com/3/e/a/3ea9894e673e2faa36d6a8b03788c0c911a25ac1.png)
and 
therefore the first part of our list of necessary conditions is taken care of. Now, notice that substituting 
into the second equation we arrive at the second condition.
and we are done.
this claim is not true.
but 
.
give distinct residues modulo 
for all 
.
is periodic with minimum period 
if and only if 
.
.
.
.
.
Conversely, if 
is periodic and minimum period is an integer 
such that 
.
by induction hypothesis 
.
for some 
.
.
give each residue modulo 
times. Since 
exactly 
Since 
for all 
but not 
.
if and only if 
that any 
cycles every 
,
Hence ![\[ f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1} \]](http://latex.artofproblemsolving.com/a/f/0/af0415948cba300ada165bc5e2e5a2af580b1e85.png)
noting that 
does not depend on 
hence 
,
differ mod 
leave distinct remainders when divided by 
.
,
,
being true means that these three terms leave distinct remainders when divided by 
(I hope I don't need to explain this). In this manner, 
,
,
,
,
,
.
leave distinct remainders when divided by 
,
(I am doing two base cases just to be safe). At this point, we notice that the remainders give some really nice pattern, so we are intrigued about the difference between two terms whose abscissas differ by a power of 
is true. That is, 
leave distinct remainders when divided by 
.
be the statement: 
leave distinct remainders when divided by 
for all positive integers 
,
is true. That is, 
leave distinct remainders when divided by 
.
modulo 
.
take on the value that is the remainder when 
.
and 
be positive integers and 
be an odd positive integer. If 
is not divisible by 
.
has no two elements that are the same. Namely, they cover all the odd positive integers less than 
.
.
.
for all positive integers 
.
,
.
holds true. Notice that 
,
by the induction hypothesis. Also note that because 
is divisible by 
,
,
,
,
for all positive integers 
,
.
.
.
,
verifying that the set 
,
is replaced by 
.
.
not being divisible by 
,
,
must leave different remainders when divided by 
must leave distinct remainders when divided by 
.
,
leave distinct remainders modulo 
.
.
is a complete residue class modulo 
.
.
.
then 
,
.
is a complete residue system modulo 
,
.
.
.
.
.
But 
,
.
are all distinct modulo 
where 
.
is distinct from all previous values. Then using periodicity again, we are done.
(WLOG 
)
.
.
.
so 
.
forms a complete residue set modulo 
,
for all 
.
.
,
.
for some integer 
modulo 
so therefore 
.
so therefore we must have that 
as desired.
if and only if 
.
which due to order reasons is clearly congruent to 
modulo 
leave distinct remainders mod 
are all distinct mod 
are all distinct mod 
.![\[\{f(1),\ldots,f(3^n)\} \equiv \{1,3,5,\ldots,2\cdot 3^n-1\}\pmod{2\cdot 3^n}.\]](http://latex.artofproblemsolving.com/5/b/8/5b80d1ef1cb133c6214e29d91a325dfc84286b46.png)
Thus,![\[f(3^n+1)\equiv f(1)+2^1+2^3+\cdots+2^{2\cdot 3^n-1}\pmod{3^{n+1}}\]](http://latex.artofproblemsolving.com/0/2/7/0273b0aa38bbad9780e59180d3cfb5bf22fcfb3f.png)
by Euler's theorem. We compute![\[D:=2^1+2^3+\cdots+2^{2\cdot 3^n-1}=2\frac{4^{3^n}-1}{3}.\]](http://latex.artofproblemsolving.com/a/a/3/aa37d090e9369d0b2f1c9a017d92e500dceb0538.png)
By LTE, we have 
,
.
are all distinct mod 
,
.
.![\[\{f(1),\ldots,f(3^{n+1})\}\equiv\{f(1),f(1)+3^n,f(1)+2\cdot 3^n\}\cup\cdots\cup\{f(3^n),f(3^n)+3^n,f(3^n)+2\cdot 3^n\}\pmod{3^{n+1}}.\]](http://latex.artofproblemsolving.com/c/b/c/cbccdcf90cfc39e4554e4cda3acdd636c4509d9e.png)
It's clear then that this covers all residue classes mod 
![\[f(n)-f(n-1)=2^{f(n-1)}\]](http://latex.artofproblemsolving.com/9/c/c/9cc45ec947d8c18735cacc5312c704e5a32c9431.png)
.......... and so on till:![\[f(2)-f(1)= 2^{f(1)}\]](http://latex.artofproblemsolving.com/4/c/5/4c5585802a673e03d58eaaa8d784af5ba395a227.png)
.![\[f(n)=\sum_{i=1}^{n-1}2^{f(i)}+1.\]](http://latex.artofproblemsolving.com/0/7/d/07d0239b12f2927510e55fcb28dddc70d64207ea.png)
Clearly f(n) is odd for all n.![\[f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}\]](http://latex.artofproblemsolving.com/8/f/8/8f8ba3307e35b2a741687fa4db352e9795041ce6.png)
must be divisible by ![\[\Rightarrow f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}\equiv 2(m-t)(mod 3^{2013})\]](http://latex.artofproblemsolving.com/1/e/6/1e6841b5e21d71ec6e2e762191ca752d1f493797.png)
But this is not True since 3 does not divide 2 and m-t<2013 and this is a contradiction.So, we have proved the required result and we are done.
and 
,
modulo 
is trivial since 
.
,
By LTE,
so we have that 
modulo 
because 
is even and has 
equal to 
.
modulo 
leave distinct remainders when divided by 
by induction on 
is easy to verify. Now, assume that the statement holds for an arbitrary 
.
By the inductive hypothesis, we know that 
are distinct modulo 
modulo 
by Euler, our above sum is equivalent to
But from LTE, we have 
,
.
for some fixed 
.
leave different residues mod 
.
by Euler's theorem (1). We have 
for some constant c either 1 or 2; by the same reasoning 
for the same c; in particular, no matter the choice, it's obvious they're all distinct since 
,
sufficiently separates the residues in each group (one spans from ![$[0,3^k-1]$](http://latex.artofproblemsolving.com/7/a/6/7a632186121642a104e90780295c8daf92145786.png)
,![$[3^k,3^k2-1]$](http://latex.artofproblemsolving.com/1/d/a/1da2c565ceb351588c3e179052789165b504b285.png)
,![$[3^k2,3^{k+1}-1]$](http://latex.artofproblemsolving.com/b/c/7/bc713e3debfdbc2556bce7c7d8d7ace3f1bf6e32.png)
)
have distinct residues 
.
.
in some uniform order. It suffices to show that no corresponding terms from different blocks are equivalent 
,
.
The exponents are 
,
.
.
,
and 
as desired.
.
,![\[v_3 \left(2 \cdot \frac{4^{3^k}-1}{3} \right) = k\]](http://latex.artofproblemsolving.com/6/e/b/6eb099d2af8067067688f9b7d20774e1d253e827.png)
have different residues mod 
.
trivial. Then write ![\[ f(a+3^i)-f(a) = \sum_{n=a}^{a+3^i-1} f(n+1)-f(n) = \sum_{n=a}^{a+3^i-1} 2^{f(n)}. \]](http://latex.artofproblemsolving.com/1/3/8/1386818ff89079991ee4020f84cec8772b7a50cd.png)
By inductive hypothesis, all of the 
leave distinct residues modulo 
,
,![\[ f(a+3^i)-f(a) \equiv \sum_{k=1}^{3^k} 2^{2k-1} = 2 \cdot \frac{4^i-1}{3}. \]](http://latex.artofproblemsolving.com/9/4/2/94218adbbecf14844275404dcdb8148c92d1b390.png)
Now taking 
,
have distinct residues modulo 
,
in ternary so that ![\[ \Delta = \sum_{i} b_i \cdot 3^{a_i} \]](http://latex.artofproblemsolving.com/7/2/f/72fe8a0d8c7deb66eae553b1b3fc4a41c1ace6fe.png)
for distinct 
of numbers in 
.![\[ \nu_3(f(a+\Delta)-f(a)) = \nu_3(\Delta) \]](http://latex.artofproblemsolving.com/6/4/7/64723a688caeb1788fd3481dc12e7d1e54148a54.png)
by basic 
has period 
is easy to verify. We then show the hypothesis holds for 
for all positive integers ![\[f(n+3^k)-f(n) = 2^{f(n)} + 2^{f(n+1)} + \ldots + 2^{f(n+3^k-1)}.\]](http://latex.artofproblemsolving.com/a/c/8/ac8430563b67a00f9929c5f266fe0d2501e34749.png)
![\[2^1 + 2^3 + \ldots + 2^{2 \cdot 3^k-1} \equiv \frac{2 \left(4^{3^k}-1\right)}{3} \pmod{3^{k+1}}.\]](http://latex.artofproblemsolving.com/c/4/e/c4eabde47d53fc40de1b234d61564d9ebf3ab1f7.png)
is equivalent twice this expression, so their 
'![\[v_3\left(\frac{2 \left(4^{3^k}-1\right)}{3}\right) = v_3(4-1) + v_3(3^k) - 1 = k. \quad {\color{blue} \Box}\]](http://latex.artofproblemsolving.com/3/2/0/320c0f72b7101fdf687ea31aa7b917d6097c3f39.png)
leave distinct residues modulo 
distinct remainders when divided by 
and that the sequence 
,
and 
leave distinct remainders modulo 
Then it suffices to show that,
Note that 
.
Thus we have,
Now from sum of geometric series we have,
Now it suffices to show 
,
as desired.
,
all have different residue
.![\[f(n + 3^k) - f(n) = \sum_{i=0}^{i = 3^k - 1} 2^{f(n) + i}\]](http://latex.artofproblemsolving.com/5/f/4/5f495f2f62dbdecdfbc352b9d2a23ff52930f017.png)
Since 
,![\[\sum_{i=0}^{3^k-1} 2^{2i+1}\]](http://latex.artofproblemsolving.com/3/e/6/3e690a13014c5400c7515842ac6e5bf1839a20fc.png)
which is equivalent to![\[2 \cdot \frac{4^{3^k} - 1}{3}\]](http://latex.artofproblemsolving.com/9/3/c/93ce002a3abde1a683567ba56abb9cb6af3b26fa.png)
By LTE, 
leave distinct remainders when divided by 
case is easy to verify. Now assume the claim for 
.
is 
.
,
then the result follows.
is divided by 
for positive integers 
is some constant 
,
are some permutation of 
by the Chinese Remainder Theorem. Then by Lemma 1, we have
then clearly the remainder when 
is divided by 
.
are divided by 
will always be made all distinct.
leaving distinct residues in 
have distinct remainders 
.
have distinct residues modulo 3. Induction hypothesis: Assume it holds for n=k.
.
.
then 
,
.
is a complete residue system mod 
.
.
.
.
.
,
Hence 
Clearly, this shows that 
where 
.
.
is distinct from all previous values and using the periodicity, we are ready.
are distinct mod 
.
mod 
case.
.
be a positive integer. Then 
.
.
)![\[\nu_3(2^r - 1) = \nu_3(4^{r/2} - 1) = \nu_3(r/2) + \nu_3(4 - 1) = \nu_3(r) + 1.\]](http://latex.artofproblemsolving.com/8/8/3/883fc9b41f5cf44e3a9ba7e9e14ffdc2d559cee3.png)
Since 
,
.
,
as claimed. 
mod 
.![\[f(n + 3^k + 1) = f(n + 3^k) + 2^{f(n + 3^k)} = \dots = f(n + 1) + \sum_{i = 1}^{3^k} 2^{f(n + i)}\]](http://latex.artofproblemsolving.com/9/7/5/975f631f1fcbc6d13320182bb047bcc42bb09855.png)
![\[ \equiv f(n + 1) + \sum_{i = 1}^{3^k} 2^{2i - 1} = f(n + 1) + \frac23\left(4^{3^k} - 1\right).\]](http://latex.artofproblemsolving.com/b/8/d/b8d4eb9db4854a9775c04f5c85432d59a0ee44c0.png)
But since ![\[\nu_3\left(\frac23\left(4^{3^k} - 1\right)\right) = \nu_3\left(4^{3^k} - 1\right) - 1 = k\]](http://latex.artofproblemsolving.com/1/1/3/1139343b41d5a7898a1ede5ed9cf94ecc30c6bce.png)
by LTE again, we obtain 
.
,
are in some order congruent to ![\[f(n + i), f(n + i) + 3^k, f(n + i) + 2 \cdot 3^k\]](http://latex.artofproblemsolving.com/b/d/0/bd035ccdb48f913ccc82a31499e829880298ab7c.png)
mod 
,
.![\[a_1, a_2, \dots, a_{3^k}, a_1 , \dots \pmod {2 \cdot 3^k}\]](http://latex.artofproblemsolving.com/b/e/c/bec77966fd62fc661572464630c43286b6cc119a.png)
Now, by Euler's theorem, we actually have that![\[f(n) \equiv f(n - 1) + 2^{a_{n-1}} \pmod {3^{k + 1}}\]](http://latex.artofproblemsolving.com/2/0/a/20ab4deca83bac05250a96dd71a6a885bb905cec.png)
Therefore,![\[f(n + 3^k) - f(n) \equiv 2^{a_1} + 2^{a_2} + \cdots + 2^{a_{3^k}} \pmod {3^{k + 1}}\]](http://latex.artofproblemsolving.com/e/2/e/e2e9b709e5738e9bb81d3664f5954a3b7641c461.png)
Since the order of ![\[v_3(2^{2m} - 1) = 1 + v_3(m) \geq 3^{k + 1} \implies 3^k \mid m\]](http://latex.artofproblemsolving.com/9/1/8/918f9eff9f916fc8074afb0c6a62d3cd5f83668d.png)
Therefore, 
are odd,![\[2^{a_1} + 2^{a_2} + \cdots + 2^{a_{3^k}}\]](http://latex.artofproblemsolving.com/a/b/1/ab12d08c6c54eb2b438413cf9ed34a3992e26856.png)
covers every residue that is 
,![\[f(n + 3^k) - f(n) \equiv 2 + 5 + \cdots + 3^{k + 1} - 1 \equiv \frac{3^{k+1} + 1}{2} \cdot 3^k \pmod {3^{k + 1}}\]](http://latex.artofproblemsolving.com/e/9/2/e9223eae758ebfd587eabfa87eff6859df2870da.png)
Thus, the smallest 
is 
We proceed with induction. The base case, 
is trivial as 
and the sequence will always shift down by one.
We show it for 
By the inductive hypothesis, for nonnegative integers 
is a complete residue system modulo 
Apply this for 
so due to periodicity it suffices to show that 
are distinct modulo 
But, since powers of 
iterations mod 
by Euler's Theorem, it follows that by the inductive hypothesis, 
as 
is some permutation of the odd residues under mod 
But 
by LTE. Therefore 
are indeed distinct modulo 
so our induction is complete. Now the result follows. QED
leave distinct remainders when divided by 
and we shall show it for 
is odd for all positive integers 
.
)
for all 
.
we wish to show it holds for 
.
As a corollary it follows that,![\[f(r+1)+f(r+2)+\dots + f(3^n+r) \equiv f(r)+f(r+1)+\dots + f(3^n+r-1) \pmod{3^n}\]](http://latex.artofproblemsolving.com/0/0/0/00001c6c4562ebf6f40bfcf18700806760329699.png)
which implies 
by the Chinese Remainder Theorem it also follows that 
.
As 
are distinct 
and the inductive hypothesis (of the claim) for 
holds, and also by the Lifting the Exponent Lemma it follows that 
.![\[\frac{4^{3^m}-1}{3} \equiv 3^{m} \pmod{3^{m+1}}\]](http://latex.artofproblemsolving.com/f/5/6/f5620a25cf046fd2a2fb7a9763073778c33b5a62.png)
are quite easy to check. Now say the claim holds for 
so we wish to show it for 
.![\[\frac{4^{3^m}-1}{3} = (3l+1)3^m\]](http://latex.artofproblemsolving.com/f/9/d/f9d3a0f863a33d22a2069defc93149cd934b6c8d.png)
for some positive integer 
.
which completes the induction and we are done.
we have 
.
since 
are distinct 
by our first claim, and Euler's Generalization of Fermat's Little Theorem.
and by the above claim, 
are distinct 
for all 
are distinct