AoPS Academy
let 
denote the intersection of diagonals 
and 
, and let 
denote the intersection of diagonals 
and 
. Prove that if 
and 
, then 
bisects angle 
.
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 . )
x table such that the unit squares are colored arbitrary in black and white, such that exactly three of the squares placed in the corners of the table are white, and the other one is black. Prove that there exists a 
x square which contains an odd number of unit squares white colored.
as the largest integer 
such that 
. Find all integers that are not powers of 
such that the sequence 
is unbounded.
that are not powers of .
inspection that all 
's are at most if 
. Thus that work satisfy . that is not a power of works. It suffices to show that the order of modulo 
is 
. Realize that ![\[ \nu_2(3^{2^k}-1) = \nu_2(2^k)+\nu_2(3^2-1^2)-1=k+2, \]](http://latex.artofproblemsolving.com/9/b/5/9b5c1009f21bc67c180f822314175ec6cf55b28b.png)
so the order is as desired.
is always 1 or 3 mod 8, so otherwise 
will never be divisible by 8. has order mod for 
. By 
LTE, we have 
which clearly implies this result. numbers that are 1 or 3 mod 8, all of these are part of this cycle. Therefore, for each that is 1 mod 8, for arbitrarily large 
there exists with 
, hence done.
or 
. First note that, when is even, is most clearly odd and thus, the required sequence is most obviously bounded. Further, when 
,![\[3^n-5 \equiv 3^n+3 \in \{4,6\} \pmod{8}\]](http://latex.artofproblemsolving.com/e/1/3/e1385ce79892b44094644f5afd346ebf7f12a2d1.png)
when 
, we also have![\[3^n-7 \equiv 3^n+1 \in \{2,4\} \pmod{8}\]](http://latex.artofproblemsolving.com/4/4/0/44079c19e17acb698ed0cb160e22923bf37b567b.png)
So, any term in this sequence is not greater than for these cases implying that they are clearly bounded. Thus, all other possibilities besides the claimed ones are impossible.
. One can check quite easily that there exists 
such that 
in these cases. Then, assume there exists a positive integer 
(we verified that this is divisible by ) such that 
for all 
. Let 
be the positive integer such that 
. Then,
Now, we note that for all even 
,
Now, one can consider 
which is clearly even since we confirmed that . By LTE, this gives![\[\nu_2(3^m-1)=\nu_2(3-1)+\nu_2(3+1)+\nu_2(m) - 1 = 1+2-(k-2)-1=k\]](http://latex.artofproblemsolving.com/5/0/6/50647e2ac93bdb11aa8b29c0540b0b0bb2be7d3c.png)
Thus,![\[3^{m+r} - n \equiv n\left(3^m-1\right) + 2^k \equiv n\cdot 2^k + 2^k \equiv 0 \pmod{2^{k+1}}\]](http://latex.artofproblemsolving.com/4/a/0/4a035e698b9390552e33325c6b7660e9671518d1.png)
But this is a most clear contradiction to our assumption that is the maximum element of this sequence. Thus, there indeed exists no such maximum and the sequence is unbounded as desired.
even fail. Then 
or 
modulo have bounded less than or equal to by looking at modulo for 
.
modulo .
for even and,
for odd. Then clearly we require 
and hence is the order of modulo . 
as a quasi generator. only covers residues congruent to 
or modulo over modulo .
are modulo , so 
only covers residues congruent to modulo .
in fact only covers residues congruent to modulo . To see this induct. Note that the base case of 
for 
is trivial. Now from our inductive step assume for some the residue of modulo say , is congruent to modulo . Then clearly,
Now taking modulo we have 
, completing the induction. covers distinct residues mod . However as there are exactly residues that are or modulo , we must in fact have cycle over all residues congruent to or modulo , modulo for 
. Now we can finish. or modulo it suffices to show that 
can grow arbitrarily large for 
or 
. However note that for any we have for some ,
from our lemma concerning as a generator. Thus we are done.
gives only residues 
if a number satisfies the condition it must be of that form. We are going to prove those in fact satisfies, this is, it always exists a 
and 
such that 
for every of this form, it suffices to prove that 
to state that every 
is a power of 
(because those sets would have the same number of elements) , but this is true as
that satisfy 
. This is necessary as 
only has the terms and , so otherwise, the sequence is strictly bounded under . that is or modulo works, we will show that it is true up to . Since is unbounded, this will be sufficient to show the condition holds for any positive integer. modulo be 
. We have![\[3^e-1 \equiv 0 \pmod{2^k} \iff \nu_2(3^e-1) \ge k.\]](http://latex.artofproblemsolving.com/1/0/9/10969f2dfe5b42297f5f9ace7100a6d3d3afa1b7.png)
![\[\nu_2(3^k-1) = \nu_2(3-1)+\nu_2(3+1)+\nu_2(k)-1 = \nu_2(k)+2 \implies e = 2^{k-2}.\]](http://latex.artofproblemsolving.com/f/9/1/f9136512c8c6ad396ad8f186ca5a4fb2adc91cb5.png)
numbers that are or modulo , these must fill out each of the numbers in the cycle, which proves the sequence is unbounded. 
. First notice that each must be a residue of 
for all sufficiently large ; otherwise, its 
is indeed bounded.
for all 
, so we have 
distinct residues modulo 
. Consequently, our claim follows by induction by considering the "transfer" of residues between modulo and 
. 
that are or mod . have bounded sequences. mod , we get that the only possible modulos are mod and mod . Therefore, if is anything but or mod , then 
can be at most (becuase can't be a multiple of ) for any non-negative integer , making the sequence bounded. Therefore, in order for the sequence to be unbounded, we need to be either or mod . is or mod , then the sequence is unbounded. and such that 
for some positive integer , then 
. This can be proved by letting 
and 
for odd positive integers 
and 
and noting that in the sum![\[m+n=(a+b)2^x,\]](http://latex.artofproblemsolving.com/9/9/b/99b3d49de11aeedfd9afc6af02c0a835cb16323a.png)
must be even, making . We will use this fact to prove that is unbounded for all that are or mod . be an integer such that 
and 
. Since is or mod , such an must exist. Now note that by the case of LTE, for a positive integer , we have![\[\nu_2(3^{c+m}-3^m)=\nu_2(3^m(3^c-1))=\nu_2(3^c-1),\]](http://latex.artofproblemsolving.com/7/6/c/76c86a63d70cffddce39dbff67e580c200084aba.png)
![\[=\nu_2(2)+\nu_2(4)+\nu_2(c)-1=\nu_2(c)+2.\]](http://latex.artofproblemsolving.com/3/4/6/3468b8c7ecfa2da5f0043953ab87f507cbb48e95.png)
Therefore, for any integer such that , and for any positive integer such that 
(this must exist, we know that 
), we have that![\[\nu_2(3^{c+m}-3^m)=\nu_2(3^m-n)=x\iff \nu_2(3^{c+m}-n)>x,\]](http://latex.artofproblemsolving.com/b/4/a/b4af8ae82265feb7bab79edd1e83528e88ac90d7.png)
by (2a). This gives that the sequence is unbounded (by induction on the exponent of ) if we can find that there exists an integer such that 
. However, since is or mod , and we know that there exist infinite numbers of powers of that are or mod , such an must exist. Therefore, if is or mod , the sequence is indeed unbounded, finishing the problem.
works then 
for some . It follows that can only be or modulo . which is or modulo works. Indeed, suppose that 
for some 
. Let 
.
is even then 
. is odd then 
It it well known that 
. Thus, 
is divisible by but not by 
. So 
is an even integer. It follows from 
that 
.
such that 
. So by induction it follows that 
is unbounded, as required.
Clearly, even values don't work. We consider 
Clearly, 
can only achieve the values 
Thus, if 
, we have that 
Thus, we have that 
Observe that each number term that is either 
in 
can be written as because of the order. Thus, we are done by LTE.
. We start off with a claim, which re-derives LTE in the case .
, we have![\[ \nu_2\left( 3^{2^{r-2}}-1 \right) = r. \]](http://latex.artofproblemsolving.com/0/5/d/05d9cdb0a252f33b04aba18b0ababda33767f910.png)
Proof. Write![\[ 3^{2^{r-2}}-1 = (3-1) \prod_{i=0}^{r-3} \frac{3^{2^{i+1}}-1}{3^{2^i}-1}
= 2 \prod_{i=0}^{r-3} \left( 3^{2^i}+1 \right). \]](http://latex.artofproblemsolving.com/3/c/a/3ca7e45c1e1f87964cbfad2ec77d480ce9105f62.png)
For 
, we have 
, and for 
, we have 
; thus the claim follows. 
mod 
is exactly 
, for . Further, 
for any integer . But there are exactly integers mod that are or mod , so traverses exactly these integers.
all work. And 
fail by mod , hence done.
.
,
.
.
covers all values 
.
are distinct mod 
but 
since 
.
,
where 
because they're 
.
.
.