AoPS Academy
![\[ x^n + 1 = y^{n+1}, \]](http://latex.artofproblemsolving.com/4/a/8/4a80f616d2a091187cdd1c57a5b6e1f09cdc9396.png)
where 
is a positive integer not smaller then 2, has no positive integer solutions in 
and 
for which and 
are relatively prime.
. How many complex numbers 
are there such that 
and 
is an integer.
be reals such that 
. Prove that
Let be reals such that 
. Prove that
,
,
, 
, 
is not greater than 
.
red balls and 
white balls. Audi took two balls at once from inside the bag. The chance of taking two balls of the same color is ...
unit. The area of the hexagon is ...
and are the roots of the cubic equation 
. The value of 
is ...
so that 
and 
is ...
, 
, 
, 
has an average of 
and a median of 
. The largest number of such data is ...
are integers greater than 
which are four consecutive quarters of an arithmetic row with 
. If 
and 
are squares of two consecutive natural numbers, then the smallest value of 
is ...
, with 
, 
and 
. The points 
and 
lies on the line segment 
. with 
and 
. The measure of the angle 
is ...
meet 
for each natural number . The value of 
is ....
provided that the difference of any two numbers at least 
is ...
which satisfies 
are as many as ... with 
and 
. Point lies on the side so that 
. Suppose 
is a point on the side extension 
so that 
is perpendicular to . The point lies on the ray such that 
and 
. The large angle 
is ...
consists of integers with the following properties: For every three different members of there are two of them whose sum is a member of . The largest value of is ....
with 
positive reals is ....
with 
is ....
square units. Two plots are said to be neighbors if they both have one side in common. Initially, there are a total of 
coins on the chessboard where each coin is only loaded exactly on one square and each square can contain coins or blanks. At each turn. You must select exactly one plot that holds the minimum number of coins in the number of neighbors of the plot and then you must give exactly one coin to each neighbor of the selected plot. The game ends if you are no longer able to select squares with the intended conditions. The smallest number of so that the game never ends for any initial square selection is ....
such that 
divides 
.
, points , , and are the midpoints of sides , 
, and , respectively. Prove that the area of the triangle with side lengths 
, 
, and 
has area ![$\tfrac{3}{4}[ABC]$](http://latex.artofproblemsolving.com/9/8/a/98a118cb3595f9ea91f8b38b7293cc211f81295a.png)
.
be a permutation of 
such that there are exactly ordered pairs of integers 
satisfying 
and 
. How many possible exist?
, let 
denote the number of its positive divisors (including 1 and itself). Determine all positive integers 
for which there exists a positive integer such that 
.
, let denote the number of its positive divisors (including 1 and itself). Determine all positive integers for which there exists a positive integer such that .
- divisors of 
from the greatest one to the least one we get:
- divisors of 
are smaller than so they actually divisors of . From here we get:
only when 
are smaller than so they actually divisors of .
and 
- divisors of from the greatest one to the least one we get: - divisors of are smaller than so they actually divisors of . From here we get: only when or there is any rule in such situation s=can you explain it. Really I can not still why you have used as sequence.
are positive divisors of . Then can't we say that 
please try to understand it might be very easy.
as a postitive divisors of n, right ?
, now it is yes?
, then t(n) is multiplicative (if 
, then 
).
is odd, if 
integer, then 
and is odd.
, then 
.
is multiplicative (
) subset of odd numbers.
, then 
, because 
, were 
.
.
then 
, because 
.
. I think all odd numbers belongs to S.
be the set of all integers representable in the form 
. I claim that is the set of all positive odd integers. First, it is clear that 
, as 
.
, then is expressible in the form 
. Since the numerator of this fraction is odd, must be odd. greater than 1 can be expressed as a product of (not necessarily distinct) numbers of the form 
, then 
, where 
is the 
th prime, which implies that . (It also follows that 
implies that 
.)
follows from 
. be any odd integer larger than 3, and suppose that all odd integers less than 
lie in . Let be congruent to 
modulo 
, for some positive integer 
; then 
for some nonnegative integer . If 
, then 
, so 
, which lies in since 
and 
by our inductive hypothesis.
, we shall define the sequences 
, and 
, and 
and 
It is clear that 
are all positive integers when 
, 
, 
, 
when 
. 
when .
for 
and 
are of the form 
. Hence, the product 
. But by our inductive hypothesis, 
as well, so 
, which completes our proof.
, for some positive integer . It's well known fact that the number of positive divisors of 
is equal to 
. So we have to prove that for each odd positive integer 
there exist such finite sequence 
that 
is equal to . Let be the set containing all such numbers . Easy to note that each element of 
is an odd integer. and both belong to , than their product 
also belong to . Take 
and 
such that 
and 
. It means that ![\[xy=\frac{(2a_{1}+1)...(2a_{m}+1)(2b_{1}+1)...(2b_{k}+1)}{(a_{1}+1)...(a_{m}+1)(b_{1}+1)...(b_{k}+1)}\]](http://latex.artofproblemsolving.com/b/0/a/b0ae5bb626c9a04f1b954be70f6b691a3501b2c7.png)
. It follows that is in , as desired.
in , is also in . (1), than it will follow that each odd number is contained in , which we need to prove. Apply strong induction and prove the following conjecture: If 
are all in , where 
-s are first primes, starting from , than also 
belongs to , where is minimal prime number, greater than 
.
imply 
and hence, is in . Assume now for 
. Than, from (1), each number, whose factorization into primes contains only numbers from 
, is contained in . Consider now 
. Obviously, 
is a positive integer and 
. So, factorization of 
into primes is of the form 
, where each 
is a nonnegative integer. By assumption, is in . It means that 
is in , but 
, completing the proof of our conjecture. So, each odd prime is contained in and by (1), each odd positive integer is contained in , except for . (Easy to prove).
. Obviously, is a positive integer and . So, factorization of into primes is of the form , where each is a nonnegative integer. By assumption, is in . It means that is in , but , completing the proof of our conjecture. So, each odd prime is contained in and by (1), each odd positive integer is contained in , except for . (Easy to prove).
, can't 
be even?
.
. Since the numerator is odd, a good integer cannot be an even integer.
is obvious. can be expressed as 
. are good.
.
. Since 
is odd and less than , it's good.
.
, where is odd. Let 
, and let 
for all integers 
.
. Since is odd, is good, so 
is also good.
is correct. However, I don't understand your case of 
, what is ? And what does 
mean? It normally means 
, but it appears it means 
in how you are using it. Can you clarify on these two problems? Then maybe I can understand your proof 
., where is odd. Let 
, and let for all integers .. Since is odd, is good, so is also good. means 
with times taken the function 
for 
meaning,
and his proof is correct.
. Assume the result is valid for all 
Let 
and 
where is odd .
.Now consider the sequence
.
.Let ![$[y]$](http://latex.artofproblemsolving.com/b/d/e/bde015c27a93628bf6263095b942c5348d9570f2.png)
be the representation of in the above form .Hence would be represented in the form ![$A. [y]$](http://latex.artofproblemsolving.com/c/d/c/cdc75372a4ab7a7adc88bd43e77360c2a5e7c348.png)
.Hence the induction is complete
, let denote the number of its positive divisors (including 1 and itself). Determine all positive integers for which there exists a positive integer such that . can be written as 
for 
and 
integers (for 
anyway). Clearly, any such number must be odd, as the numerator is odd. Note that is expressible, simply by 
and 
.
be the smallest odd number that is not expressible. Suppose 
where is odd and 
. Consider 
and plug 
to obtain an expression for , since 
is odd, hence expressible, by assumption, yielding a contradiction! So all odd numbers are expressible. 
. 
easily follows on taking 
, so from now on assume 
. First let 
where the 
's are positive integers, and 's are primes. Then the problem condition translates to 
Since numerator is odd, so for to be an integer, the denominator must also be odd (and also must be an odd integer, so we can effectively ignore even from now on). This means that 
, or equivalently that all 's are even. Letting 
, we get 
Call all integers , which can be written in the fashion above, as expressible numbers. Also, for any expressible number , we let 
denote its notation in the above form (note that we have 
only). We proceed by strong induction to show that all odd are expressible. For 
, take 
and 
. Now, suppose the result is true for all odd numbers less than . We will show that it is true for as well. If 
, then write 
. Thus, we have 
where 
is expressible by induction hypothesis. So from now on let 
. Suppose there exists some 
with 
(we'll later prove why such an 
must exist). Write 
. Then we have 
This gives 
Since 
, so we get that 
where 
is expressible by induction hypothesis. Thus, all odd are expressible if such an exists. exists. Suppose not. Then 
for any 
(
simply gives ). This easily converts to the form that 
for any 
. But this means that 
, contradicting the fact that is odd. Thus, such an exists for all odd . Hence, done. seperately, and showing why exists), and I haven't changed anything coz this is how I discovered the solution. To be completely honest, I had a thinking that maybe just dividing into cases modulo 
will work. However, it soon became clear that this wasn't the case, as each case was getting divided into a sub-case. Luckily for us, the whole thing generalized easily (Or maybe the problem was designed in such a way only 
).
, so is achievable. Let 
. Let 
be the prime factorization of . Then 
and 
. In order for 
to be an integer, it is necessary that 
is odd, since 
is odd. So is always odd. is multiplicative, is also multiplicative. Also, note that 
, in other words, the primes used in the base of the prime factorization of the input "don't matter". So if 
, and 
is the sequence of primes, then 
for any positive integer 
. It follows that if all odd primes are in the range of , then all odd positive integers are in the range of , since we can write every odd positive integer as a product of odd primes., and take the least prime that is not in the range of . Note that 
, so 
. If 
then let 
, so 
for any prime 
. Since 
is odd due to and 
, there exists an such that 
, due to minimality of . So 
. Since the primes in the prime factorization of "don't matter", as established earlier, we can make 
, so 
, and thus must be in the range of , contradiction.
, then take 
, so 
. Note that 
is odd since . Then taking 
, we have 
, for some prime . Note that 
is smaller than , so we have some such that 
. So then 
, and we can make 
, so 
. Then 
so is achievable. Therefore all odd primes are in the range of , and we are done.
which works when 
. Now, if 
with odd, then we have 
By induction, since can be represented, we are done.
for distinct primes 
and positive integers 
Then, we have ![\[\frac{\tau\left(n^2\right)}{\tau(n)}=\frac{(2e_1+1)(2e_2+1)\dots(2e_k+1)}{(e_1+1)(e_2+1)\dots(e_k+1)}.\]](http://latex.artofproblemsolving.com/5/8/7/587deb4f5c3310d12011b36a1fa03172c678f397.png)
Since the numerator is odd, the denominator must also be odd, so all 
are even, and is odd. It just remains to solve the following equivalent problem: for which odd positive integers is it possible to find elements that multiply to , not necessarily distinct, from the set 
where is a positive integer. Call rational number good if it satsifies that. Note that is good by taking no elements at all. An empty product is equal to . is good by taking 
and 
. and are good rationals, not necessarily distinct, then 
is good. Take all the elements from the construction for and then the ones from the one for , and then take the product of them all. is a good positive integer, then 
is good. In this case, take the elements from the construction for and add on the element described by 
, for the statement for all odd , is good. If 
then 
is an odd positive integer, which must be good. Thus, 
is good.
for odd. Since is odd, must be good, so it suffices to show that 
is good. Indeed, let 
then 
is odd, so 
Thus, ![\[\frac{2c-1}{c}\cdot \frac{4c-3}{2c-1}\cdot \dots \cdot \frac{2^a(c)-(2^a-1)}{2^{a-1}(c)-(2^{a-1}-1)}=\frac{2^ac-(2^a-1)}{c}=\frac{m}{b}\]](http://latex.artofproblemsolving.com/e/2/2/e226a47ac8cbf4484b7604ee72f0f0699d55ea03.png)
is good as desired.
must be odd, we have is odd, so 
is also odd. It remains to show that all odd numbers work.
, is odd, so must be a perfect square. Write ![\[n = p_1^{2a_1} p_2 ^{2a_2} \cdots p_l ^{2a_l} \]](http://latex.artofproblemsolving.com/a/d/a/ada800f176063de64bb03ae6007b4e7d19b5ace3.png)
for some positive integer 
, distinct primes 
, and positive integers 
.![\[m = \frac{(4a_1 + 1)(4a_2 + 1)\cdots (4a_l + 1)}{(2a_1 + 1)(2a_2 + 1)\cdots (2a_l + 1)} \]](http://latex.artofproblemsolving.com/1/a/a/1aa7b968e8c017d68038c99cd93f732f2d71b669.png)
Note that if we can find 
such that the expression is equal to , then is a valid number in the problem.
work by having no at all, and 
, respectively.. Suppose that all odd positive integers less than were expressible. We show that is also expressible.
and 
.
for all positive integers , then we have ![\[f^y(c\cdot (2^a - 1)) = k\cdot 2^{a+1 - y} \cdot (2^a - 1) + 2^{2a - y} - 2^{a+1 - y} + 1 \]](http://latex.artofproblemsolving.com/1/6/a/16ab08f4caf0df5a456d7bf570d5b9477c3afd23.png)
for all positive integers 
.
is obvious), we see that if works, then 
as desired. So the induction is complete.
for any positive integer 
. Using the fact that 
for 
, we get that the number ![\[\frac{d}{f(d)} \cdot \frac{f(d)}{f^2(d)} \cdots \frac{f^{a-1}(d)}{f^a(d)} = \frac{d}{f^a(d)} = \frac{k\cdot 2^{a+1} \cdot (2^a - 1) + (2^a - 1)^2}{(2^a - 1)(2k + 1)} \]](http://latex.artofproblemsolving.com/4/e/d/4ed19fe5b4ccaab8b1b0f8d64535f2f82cfe387c.png)
is expressible. Since 
is expressible, we can multiply by and get that ![\[\frac{k\cdot 2^{a+1} \cdot (2^a - 1) + (2^a - 1)^2}{2^a - 1} = c\]](http://latex.artofproblemsolving.com/0/a/a/0aa190a7d47e8b1cef837da9d43d7d321a0e4c9f.png)
is also expressible, which completes the induction.
(where are exponents in the factorization of n). From here, it's obvious evens don't work, all exponents are even, and we prove all odds work by proving you can find elements from the set 
(repeating allowed) that multiply to m; call these numbers obtainable. We proceed by induction, manually computing base cases n=1,3; observe that if m is obtainable then 2m-1 is obtainable by also using 
(1), and if a and b are obtainable then ab is obtainable by combining sets (2); assume henceforth the inductive hypotheses for 
. In this way, the next minimal number 
is obtainable by using (1) and inductive hypothesis. Furthermore, if 
is 3 mod 4, by inductive hypothesis j is obtainable, so by (2) it suffices to prove 
is obtainable. But this is evident, as 
is indeed obtained.
for arbitrary d (i hope i didn't get this wrong, someone pls check), and from there it was easy.
. Clearly works by taking , so suppose .
for positive integers 
. Call rational numbers which can be written like this good. Obviously products of good numbers are also good. Observe that each fraction always have nonpositive 
, hence must be odd. We now show that every odd prime is good, which will finish the problem. To do this, we induct on .
, so 
. Then we consider the identity
hence 
is good. On the other hand, by the definition of , 
is odd and strictly less than , hence by inductive hypothesis it is good as well. Thus is good: done. 
primes by using , but for 
primes this doesn't work. When I tried 
, I found that we could "start" from 
, but again this doesn't work for 
. But for this case "starting" from 
sometimes works. At this point we figure out the solution.
is odd so can never be even. We claim that all odd numbers are possible.
. Then let prime factorization of be
where 
. Then 
. Of course all numbers in are of form
where 
, note that any number of form is also in by choosing appropriate prime factors. So we only have to consider rationals of these forms. by choosing (or choosing 
). Now if 
and 
,then 
. Now note that 
we have 
. This can be proved by induction on 
. For 
consider the sequence 
. Now if for 
, if we have 
, then note that by choosing the sequence
we get 
. Hence their product 
. This completes the induction step. As we have 
. Letting
we get 
for all 
.
where 
. For , it is already established that . Now let's suppose for the sake of induction that the given relation holds for all 
where 
. Then note that 
for some positive where is an odd number. Note that 
hence 
. Now as establised earlier that 
. We get
. This finishes the induction step. satisfy the given equation for some 
.
be real numbers.Prove that
Write only the answers to the questions given.
to be more exact:
in years 2002-08 time was 90' for part A and 120' for part B
,
then by induction we prove that every odd m can be represented as 
is false 
?
,
,
,
such that ![\[\frac{2e_1 + 1}{e_1 + 1} \cdot \frac{2e_2 + 1}{e_2 + 1} \cdots \frac{2e_k + 1}{e_k + 1} = m.\]](http://latex.artofproblemsolving.com/a/4/c/a4cf80078ca38e95920acf734c5c5a46f96bdfd0.png)
,
for some odd 
for 
,![\[\frac{2(2^ra - a - 1) + 1}{2^ra - a - 1 + 1} \cdot \frac{4(2^ra - a - 1) + 1}{2(2^ra - a - 1)} \cdots \frac{2^r(2^ra - a - 1) + 1}{2^{r - 1}(2^ra - a - 1) + 1} = \frac{2^ra - 1}{a}.\]](http://latex.artofproblemsolving.com/e/8/6/e868105c86df1f950f2287c3ab865f9be929b887.png)
Finally, multiply by a construction for 
,
![\[\frac{2(2^ra - a - 1) + 1}{2^ra - a - 1 + 1} \cdot \frac{4(2^ra - a - 1) + 1}{2(2^ra - a - 1)+1} \cdots \frac{2^r(2^ra - a - 1) + 1}{2^{r - 1}(2^ra - a - 1) + 1} = \frac{2^ra - 1}{a}.\]](http://latex.artofproblemsolving.com/3/2/a/32aecc64c33a73a75dd00eba63674435aba643dd.png)
then 
Notice the numerator is always odd, so 
letting 
Then 
so 
is also of the desired form.