AoPS Academy
be a triangle with circumcircle 
, 
-angle bisector 
, and -median 
. Suppose that meets 
at 
and meets again at 
. A line 
parallel to meets , at 
, 
respectively, so that is between and . The circle with diameter 
meets again at 
. varies, show that 
is constant.
. Let and 
be the feet of the altitudes from to 
and from 
to 
respectively.
and 
as the reflections of across lines 
and , respectively. Let 
be the circumcircle of 
. Denote by 
the second intersection of line 
with , and by 
the intersection of ray 
with .
is the circumcenter of , prove that , , and are collinear if and only if quadrilateral 
can be inscribed within a circle.
grid consisting of 2025 unit squares. Within each unit square is a car, facing either up, down, left, or right. If the square in front of a car in the direction it is facing is empty, it can choose to move forward. Each car wishes to exit the grid.
cars from the grid in such a way that it becomes possible for all the remaining cars to eventually exit the grid. that guarantees that Kritesh's job is possible?
The last line only since I like these variables better, heh. Let 
[which is called the Liouville Function] then we can see that 
is multiplicative, as 
. But by Dirichlet Convolution ![\[ \sum_{d \mid n} \lambda(d) = \lambda \ast \textbf{1} \]](http://latex.artofproblemsolving.com/8/3/f/83f7786937968849d11e513011352975cbddf8ea.png)
we can see that 
is also multiplicative. So it suffices to look at prime powers 
. It's now easy to conclude that ![\[ \sum_{d \mid n} \lambda(d)= \begin{cases} 1 \text{, if } n \text{ is a perfect square}
\\ 0 \text{, else.} \end{cases}\]](http://latex.artofproblemsolving.com/6/9/a/69ac3eb71aac8e945da61a5fc46e0917a77ea671.png)
So it suffices to count the number of perfect squares smaller than 
and well 
, hence the answer is 
.
is multiplicative. We have that![\[\displaystyle\sum_{n=1}^{1989}{(-1)^{\Omega(n)}\lfloor\frac{1989}{n}\rfloor} = \displaystyle\sum_{n=1}^{1989}{\displaystyle\sum_{n\mid m, m\leq 1989}{(-1)^{\Omega(n)}}}\]](http://latex.artofproblemsolving.com/1/d/0/1d08d012ecc2a91a2274fd6d81ff99dda96e42e3.png)
We can switch the order of the summation to make it![\[\displaystyle\sum_{m=1}^{1989}{\displaystyle\sum_{n\mid m}{(-1)^{\Omega(n)}}} = \displaystyle\sum_{m=1}^{1989}{\textbf{1}*(-1)^{\Omega(n)}}\]](http://latex.artofproblemsolving.com/6/0/3/603147c02250d726a594c2f7acb538c0d9704ef6.png)
Because is multiplicative, 
must also be multiplicative. For a prime power 
, note 
is 
if is even, and 
if is odd. Thus, we have that is if 
is a square and otherwise.![\[\displaystyle\sum_{m=1}^{1989}{\textbf{1}*(-1)^{\Omega(n)}} = \lfloor\sqrt{1989}\rfloor = \boxed{44}\]](http://latex.artofproblemsolving.com/4/b/7/4b7ce3a04966a30cd2da183013ebe57c19dd4110.png)
Now let 
where 
are distinct primes and 
are positive integers. Since is mutiplicative, we have
If at least one of the is odd, the sum is . On the other hand, if all are even, the sum is . Then the final sum counts the number of perfect squares between and inclusive, which is .
.![\[
\sum_{n=1}^{1989} (-1)^{\Omega(n)}\left\lfloor \frac{1989}{n} \right\rfloor = \sum_{n=1}^{1989} \sum_{m \mid n} (-1)^{\Omega(m)}.
\]](http://latex.artofproblemsolving.com/6/f/1/6f1df800004014b1683a01bb1b237f3268575286.png)
We will now show that![\[
\sum_{m \mid n} (-1)^{\Omega(m)} = 1
\]](http://latex.artofproblemsolving.com/9/2/2/9224382e59164762af692df149ec6d0c16cd8151.png)
if 
is a square and 
if is not a square. Notice that if is not a square, it has an even number of divisors, so we can partition the divisors of into groups 
. Notice that each group has sum because one of them has one more prime divisor than the other. If is a square, then we can do the same thing but with 
for some 
. Then 
, so the sum is 
. So summing from 
to 
is just the number of squares less than , which is .
Now see that the inner function is basically 
and both are multiplicative functions and hence their Dirichlet convulation is also a multiplicative function; and now we can check easily that ![\[\sum_{n \mid m} (-1)^{\Omega(n)}= \begin{cases} 1 \text{ if $m$ perfect square} \\ 0 \text{ otherise} \end{cases}\]](http://latex.artofproblemsolving.com/a/1/9/a19cebd6063504d98b3e0c8c93084b113117d03f.png)
This basically gives us that the answer is 
.
and 
. Prove that
Where 
denote the number of prime factors of ![\[ \sum_{n=1}^{1989} (-1)^{\Omega(n)}\left\lfloor \frac{1989}{n} \right \rfloor. \]](http://latex.artofproblemsolving.com/2/0/4/2043dca9f2ff2adfd3c8d49fa4dd278871968db0.png)
It is often useful to rewrite the floor function in order to swap the order of summation, so let us do exactly that here:
Now, we will prove the following lemma that we obtained from checking small cases:![\[
\sum_{m \mid n} (-1)^{\Omega(m)} = 1 \iff n\text{ is a perfect square;}
\]](http://latex.artofproblemsolving.com/e/b/0/eb0f4b6a7767af51d40578ac00534ae8032681de.png)
![\[
\sum_{m \mid n} (-1)^{\Omega(m)} = 0 \text{ otherwise.}
\]](http://latex.artofproblemsolving.com/4/9/1/4915b23e26fb5c5e1ccf55e5614bca5eb64d8579.png)
Proof: 
- then we can easily see that it is multiplicative. Therefore, it suffices to check the function for prime powers 
if 
is even and 
if it is odd. Next, observe that since![\[ \sum_{d \mid n} f(d) = f \ast \textbf{1},\]](http://latex.artofproblemsolving.com/e/7/6/e7654598a9425ac392bee97751577393a5b1d2e0.png)
the function 
is also multiplicative. However, if a prime number 
has its 
odd, then we would have a zero - otherwise, we have a 
e
so the lemma is proven.
From here, since 
,
.