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.
be an acute triangle with 
, midpoint 
of side 
, altitude 
(
), and orthocenter 
. A circle passes through points 
and 
, is tangent to line 
, and intersects the circumcircle of triangle at a second point 
. The circumcircle of triangle 
intersects line 
at a second point 
. Prove that the lines 
and 
are perpendicular.
satisfy,
Where {
} is a permutation of . Prove that 
and 
Prove that
Let and 
Prove that
has a unique solution in integers with 
and 
.
as 
fir 
. Prove that 
for all 
.
be triangle with circumcenter 
and orthocenter 
. 
intersect again at 
respectively. Lines through parallel to 
intersects 
at 
respectively. Point 
such that 
is a parallelogram. Prove that lines 
and 
are concurrent at a point on 
.
is a cyclic quadrilateral inscribed in a circle of radius one unit. If 
, prove that is a square.
are positive real numbers.Prove that
be a function taking in positive integers and outputting nonnegative integers, defined as follows:
is the number of positive integers 
with 
such that the equation 
has an integer solution 
.
such that
and 
(Adit Aggarwal, India.)
be positive reals such that 
. Prove that
be an isosceles trapezoid with 
. The inscribed circle 
of triangle 
meets 
at 
. Let 
be a point on the (internal) angle bisector of 
such that 
. Let the circumscribed circle of triangle 
meet line at 
and 
. Prove that the triangle 
is isosceles.
such that, for all positive integers 
and ,
, 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 reals such that 
Prove that
,
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.