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.
times as many students as Lara’s high school. The two high schools have a total of
students. How many students does Portia’s high school have?
where 
and 
are positive integers that do not exceed 
?
denote the set of positive integers
such that for all 
it holds that 
be a positive integer. There are circles drawn on a chalkboard such that any two circles intersect at 
distinct points and no circles pass through the same point. Turbo the snail slides along the circles in the following manner, leaving snail goo behind. Initially he moves on one of the circles in clockwise direction. He keeps sliding along until he reaches an intersection with another circle. Then, he continues his journey on this new circle and also changes the direction he is moving in. We define a snail orbit to be the covering of the whole surface of a circle with turbo's goo, and specifically only a single layer of it. Prove that for every odd there exists at least one configuration of circles with a single snail orbit, and find all such that there is exactly one of the aforementioned configuration type.
such that for any two infinite sequences of positive integers 
and 
, such that 
for all 
, there always exists a real number 
such that 
for all 
.
and 
be positive integers. Prove that there exists a positive integer 
such that for every odd integer 
, the digits in the base-
representation of 
are all greater than .
and be positive integers with 
. There are cupcakes of different flavors arranged around a circle and people who like cupcakes. Each person assigns a nonnegative real number score to each cupcake, depending on how much they like the cupcake. Suppose that for each person 
, it is possible to partition the circle of cupcakes into groups of consecutive cupcakes so that the sum of 's scores of the cupcakes in each group is at least 
. Prove that it is possible to distribute the cupcakes to the people so that each person receives cupcakes of total score at least with respect to .
and be positive integers. Prove that there exists a positive integer such that for every odd integer , the digits in the base- representation of are all greater than .
is 
. Begin by letting 
be the digit at the 
th position from the right (0-indexed) of in base ; i.e., 
is the units digit. Obviously, 
for all 
, since 
. We WTS 
for each 
, and observe the following:![\[ a_i=\left\lfloor\frac{n^k}{(2n)^i}\right\rfloor\text{ mod }2n=\left\lfloor\frac{n^{k-i}}{2^i}\right\rfloor\text{ mod }2n=\left\lfloor\frac{n^{k-i}\text{ mod }2^{i+1}n}{2^i}\right\rfloor. \]](http://latex.artofproblemsolving.com/8/e/e/8eee4210547c4be6b66528e10094e1967e0025a2.png)
Note that the numerator is a positive multiple of , since 1) 
and 2) is odd) 
. Thus,![\[ a_i=\left\lfloor\frac{n^{k-i}\text{ mod }2^{i+1}n}{2^i}\right\rfloor>d \quad\iff\quad n^{k-i}\text{ mod }2^{i+1}n\ge n\ge2^i(d+1), \]](http://latex.artofproblemsolving.com/b/0/0/b0054af59102b038afc55f886fb6ed3b81faed15.png)
which is true since 
and 
. 
works. be an odd integer and let be the number of digits of when written in base . Clearly we have 
. For 
, let integer 
be such that 
. Let 
for 
and let 
. Note that 
is an integer because 
. Also, is the 
th digit (counting from the right) of when written in base , because 
and![\[
\sum_{i=0}^{m-1}s_i(2n)^i=r_1+\sum_{i=1}^{m-1}(r_{i+1}-r_i)=r_m=n^k.
\]](http://latex.artofproblemsolving.com/e/9/7/e9711b83d9f885bbdf641d3bb411d6fdfc660ce4.png)
It suffices to prove that 
for all .
since is odd. Hence 
for all . Fix 
. Since 
it follows that![\[
s_i\equiv\frac{r_{i+1}-r_i}{(2n)^i}+\frac{n^k-r_{i+1}}{(2n)^i}\equiv\frac{n^k-r_i}{(2n)^i}\pmod{2n}.
\]](http://latex.artofproblemsolving.com/f/a/a/faa14e97eae8b8d2e1dce4541a6dae93b78e27a9.png)
Then 
so 
since 
is positive. Thus 
, as desired. 
, but annoyingly I said that 
, which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
, but annoyingly I said that , which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
in my solution
, but annoyingly I said that , which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
is . Begin by letting be the digit at the th position from the right (0-indexed) of in base ; i.e., is the units digit. Obviously, for all , since . We WTS for each , and observe the following:Note that the numerator is a positive multiple of , since 1) and 2) is odd) . Thus,which is true since and . for each would still show that exists even tho the sol was already sufficient assuming that anyway? (for this one, in other words, do the graders actually care about an unnecessary/slightly off sentence I wrote after a solution that would've probably gotten a 7?)
. Define 
and 
to be the remainder when 
is divided by 
. Notice that 
and 
is odd for 
. Then, we claim that ![\[n^k = \sum_{i=1}^k \left(\frac{r_i n - r_{i-1}}{2^{i-1}}\right) \cdot (2n)^{i-1}.\]](http://latex.artofproblemsolving.com/f/0/c/f0c355fcbb56f4618d249ed1bd891de5f69b4064.png)
Indeed, notice that this sum equals 
since it telescopes. Now notice by definition of 
, each coefficient of 
is an integer. Also, since 
, each coefficient is between 
and 
. Thus, the above sum is simply a base- representation of .
, we have ![\[\frac{r_i n - r_{i-1}}{2^{i-1}} > \frac{r_i n}{2^{i-1}} - 1 \geq \frac{n}{2^{i-1}} - 1.\]](http://latex.artofproblemsolving.com/9/b/9/9b958a38b460bfbbe7a02ecf54b9f0d909adb9e6.png)
Clearly, as becomes arbitrarily large, the lower bound of each digit becomes arbitrarily large as well.
We start with the following:
we have 
The base case 
is because 
Now for the inductive step, we have
Plugging this into the inductive hypothesis completes the induction.
in the above claim gives 
Every term to the left of the rightmost term is an integer, so the rightmost term is also an integer. However, since 
for all 
it must be 
This gives us 
We have 
since 
for all 
Thus the boxed equation gives the unique base representation of 
is an odd integer, for all 
The base case 
is trivial as is odd. For the inductive step, we have 
for some odd integer 
so 
This is 
The last term is even for 
and the first term is odd since and 
are odd. This completes the induction.
we have 
so assume 
Then we have
since any odd positive integer is at least 
Therefore, the th digit from the left in the base representation of is at least 
Taking 
finishes.
be the number of digits in when expressed in base 
Note that
Note that 
but 
so for sufficiently large we have that 
Thus, we can just assume that going forward.
be the unique sequence of integers between and 
inclusive such that
Then, let 
be defined as
Note that 
This is obviously true for 
and for 
we have
so
for some integer 
However, we have that 
is odd, 
is even, and 
is nonnegative (would i get pts off for saying positive in contest?), so we have 
(might've accidentally said greater than here) and is an digit base number, we have that 
Then, we have for 
that
so
For sufficiently large we have
If 
we have for sufficiently large 
so the desired result is true for sufficiently large 
Thus, such an exists, and we are done.
works
has exactly digits.
Also note that 
from the bound This finishes.
where the last equality is since that sum is obviously an integer and the other sum is obviously less than 1.
Now, we can finish.
where the first inequality follows from being odd, and the second follows from 
From the first claim, we have:
representation of has at most digits. had at least 
digits. Then the least value of would be 
( s) 
, which would imply 
which is absurd since is positive.th digit of from the right in base is greater than 
.
. Since we are working in base , the th digit from the right will be equal to 
, where 
is the unique positive integer 
for which 
. 
is defined analogously. Since 
, we have 
so by Chinese Remainder Theorem (note that CRT is applicable since is odd so 
), 
for some 
(
is impossible since then would be even). We are given by definition that 
so: 
as desired.
is sufficient \newline
be the nth digit from the right. Since we have 
and , it follows that 
, so letting 
, we get that 
, as desired.
: We have that 
by telescoping. \newline 
since 
and 
. \newline 
since 
and 
. Therefore, our formula produces the right value as desired. Since there is a unique way to write in base , it remains to prove that each term of this formula is an integer. Since and 
, we have that 
. 
by definition, so 
and 
is an integer, as desired.
, and look at the rightmost 
digits of ; that is, the remainder upon division by 
. We compute it exactly:
be an odd integer, and 
integers. Then ![\[ n^k \bmod{(2n)^i} = c(k,\ell) \cdot n^i \]](http://latex.artofproblemsolving.com/a/b/2/ab2eba15757c8fc8ed876ce5527ab35f356de12b.png)
for some odd integer 
.
being the residue class of 
(which makes sense because was odd). 
th digit from the right to be greater than , it would be enough that ![\[ c(k,\ell) \cdot n^\ell \ge (d+1) \cdot (2n)^{\ell-1}. \]](http://latex.artofproblemsolving.com/b/3/6/b36a942d44a2ab6006740d410cce8b267d13164c.png)
But this inequality holds whenever 
., we find that for all odd ![\[ n \ge (d+1) \cdot 2^{k-1} \]](http://latex.artofproblemsolving.com/a/3/4/a34f34277b69603eca78a4f01801657d0e230f2c.png)
we have that
has digits in base-; and
, the \textsuperscript{th} digit from the right is at least 
is odd per se; we only need that 
.
. by 
shifts it digits right, leaving us with 
It suffices to show that the first digits after the decimal point are all greater than .
, consider a digit in its base representation. When we halve , the digit is replaced by either 
or 
. as 
, and carrying out the column multiplication. In particular, note that since 
, 
is also at most . for iterations, each of the first digits after the decimal point, while initially , will become in one of the iterations. For each digit, after 
, there are at most 
iterations remaining. Any digit is at least (the floor of) half of its previous value in one iteration, as established in the claim, so after all the iterations, the value of the digit is at least![\[\left \lfloor \frac{n}{2^{k-1}} \right \rfloor \geq \left \lfloor \frac{N}{2^{k-1}} \right \rfloor > d.\]](http://latex.artofproblemsolving.com/e/d/c/edc7830a8c8d9d1c344f561a08a39aa44dceadfe.png)
, but annoyingly I said that , which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
as mod 
(not exactly, but i proved that for my definition of that this is true) and i accidentally said that is positive instead of nonnegative. This does not impact the other steps in my solution.
and it is clear that is odd and is even, so I concluded that since is "positive" (nonnegative), that 
Unfortunately, I may have said greater than instead of greater than or equal to. However, this also does not impact my claim since I had intended to do 
is in fact positive, and my solution kind of made it clear why by doing 
It should be obvious from this... right?
, so 
. Then, the base representation of is in the form 
. Assume FTSOC that 
. Then, 
Taking both sides mod 
, we have 
. However, 
This means, 
Thus, we must have 
. Then, 
. Taking both sides mod gives a contradiction as desired.
is at least 
. We do this by induction on . by . The amount that carries over 
while the amount that stays is or . Note that 
Therefore, the digits after multiplying 
with are less than and at least 
as desired.
suffices.
(for all ). When 
, 
so for all 
there exists sufficiently large such that for all the digits of are greater than . in base are,![\[n^k_{2n} = \overline{a_1a_2\dots a_r}\]](http://latex.artofproblemsolving.com/2/2/a/22a02328957cf19b06acfcefc37ba7c13b37879e.png)
Then,![\[2n^{k+1}_{2n} = \overline{a_1a_2\dots a_r0}\]](http://latex.artofproblemsolving.com/6/7/d/67dc36da18501e5787798236b9ec16341ea92335.png)
are greater than 
then all digits of 
(excluding possibly the last digit) are at least . by . If a digit is even, its halve will be written which must be greater than . If a digit is odd, its halve is written and a carry over of 1 is taken to the next place. Then, the halve of 
will be written in the next place where 
is the number in this place which is clearly at least if 
. This process continues until the division is complete and it follows that all digits (except possibly the last if the final digit of is odd) will be at least .
, if we pick sufficiently large such that all digits of 
are greater than 
and 
, then all the digits of 
will be greater than (the final digit must be since is odd (as is odd)). Thus, the induction is complete and the result follows.
(for all ). When , so for all there exists sufficiently large such that for all the digits of are greater than . in base are,Then, are greater than then all digits of (excluding possibly the last digit) are at least . by . If a digit is even, its halve will be written which must be greater than . If a digit is odd, its halve is written and a carry over of 1 is taken to the next place. Then, the halve of will be written in the next place where is the number in this place which is clearly at least if . This process continues until the division is complete and it follows that all digits (except possibly the last if the final digit of is odd) will be at least ., if we pick sufficiently large such that all digits of are greater than and , then all the digits of will be greater than (the final digit must be since is odd (as is odd)). Thus, the induction is complete and the result follows.
and first digit is ) are of the form
where 
, 
, and 
. (
change on the choice of )
wins.
and 
as the first 
digits of base . Notice that the 
th digit of base is simply 
.
, which has a minimum value of 
as is odd.
.
, 
, and for our hypothesis to be true, 
. Since the left hand side is integer, it is minimized when it is equal to . After some minimal computation, we find this to be true.
have base- representation of![\[n^k=d_{k-1}(2n)^{k-1}+d_{k-2}(2n)^{k-2}+\ldots+d_1(2n)+d_0\]](http://latex.artofproblemsolving.com/1/5/7/157a1a1f2fa26cf40e766a5260561333287d0743.png)
where 
for all . We'll show that there exists a positive integer such that for all 
, 
for all . In short, we are adding possible leading zeroes to the base- representation.
. Let 
, read the reduction of 
denote the integer in 
such that 
. Then the digit 
of will largely decided by 
. Since 
, 
. Since is odd, the reduction is not zero, so it is at least 
.![\[n^{i+1}\le d_i(2n)^i+d_{i-1}(2n)^{i-1}+\dots+d_1(2n)+d_0<(d_i+1)(2n)^i=(d_i+1)2^in^i\]](http://latex.artofproblemsolving.com/b/1/4/b1441e60379275ac19c29315421e3451cbb854e6.png)
which rearranges to 
. We are done.
, but in my induction, I said that every digit is one of four forms, and this would mean 
implies that 
is of the form 
, which it obviously isn't, since 
doesn't have an inverse mod 
. However, is much larger than 
, so this doesn't ruin the 
thing, or anything else really, but I'm not sure if this will get 0-2 or 5/6 now.
works. Suppose the 
t
,
.![\[\frac{d+1}{2n}>\left\{\frac{n^k}{(2n)^r}\right\}=\left\{\frac{n^{k-r}}{2^r}\right\}\ge\frac1{2^r}\ge\frac1{2^k},\]](http://latex.artofproblemsolving.com/b/2/b/b2bccf78e0587e7079c171ad41b5bcc0ea415e56.png)
failing at 
does this still work or not
,![\[
n^k = \frac{f_{k-1}}{2^{k-1}} (2n)^{k-1} + \dots + \frac{f_1}{2} \cdot (2n) + f_0
\]](http://latex.artofproblemsolving.com/4/9/b/49b0a5749adf798fa3df4da0b3544fa7b330535f.png)
where 
are nonconstant linear integer polynomials such that 
with 
for large 
happend to be ![\[ \frac{d+1}{2n}> \left\{ \frac{n^k}{(2n)^r} \right\}=\left\{\frac{n^{k-r}}{2^r} \right\}>\frac{1}{2^r} \ge \frac{1}{2^k} \]](http://latex.artofproblemsolving.com/5/5/7/5572eb11d74cf3ce8cf4bc066983a26bf0b8ce2f.png)
Which happens only when 
and thus we are done 
.
(if it exists) to be the minimum positive integer such that for every odd integer 
,
,
,
exists for any positive integer 
.
,
for 
,
exists for all