POTWs 1 Solutions

Here are the solutions to POTWs 1. Along with the solutions, we also give some comments and difficulty ratings $\beta$ in $[1,5]$ , where POSN Camp level is 1-2, TMO level is 1-3, October Camp is around 2-4, and IMO is around 3-5.

E1 [Classical] ( $\beta = 1.4$ )
Starting from the origin $(0,0)$ . In each turn, you can either move up, down, or right (by one unit) but you cannot visit the same point twice and the points you visit must have coordinate $(x,y)$ such that $0 \leqslant x \leqslant m , 0 \leqslant y \leqslant n$ . How many paths are there to reach the point $(m,n)$ ?

Solution. Since we can’t move the point to the left, for each $a=0,1,2,\ldots,m-1$ , once our point leave the vertical line $x=a$ , it can’t be on that line again. Note that the point we’ll arrive on the next vertical line $x=a+1$ has the same $y$ -coordinate with the departure point from $x=a$ . Also, since we can’t visit the same point twice, the path starting from the arrival point to the departure point (which may actually be the same as the arrival) for each line $x=a$ is uniquely determined. So, it suffices to determine the departure points for each line $x=a$ . For each of the $m$ lines, there are $n+1$ choices. Hence, the answer is equal to $(n+1)^m$ . $\blacksquare$

Comment. The key point in solving this is to notice that the number of paths we need to count is equal to the number of some things which are easier to count. In this case, it turns out that the departure points for each vertical line $x=a$ uniquely determine the path, hence we can just count the ways to choose the departure points.

M1 [Kvant Magazine] ( $\beta = 2.4$ )
Prove that for all positive integers $n>1,$

$\displaystyle \left\lfloor\sqrt{n}\right\rfloor + \left\lfloor\sqrt[3]{n}\right\rfloor + \cdots + \left\lfloor\sqrt[n]{n} \right\rfloor = \left\lfloor \log_{2}{n} \right\rfloor + \left\lfloor \log_{3}{n}\right\rfloor + \cdots + \left\lfloor\log_{n}{n}\right\rfloor.$

Solution. We’ll count the number of pairs of positive integers $(x,y)$ satisfying $x^y\leqslant n$ and $x\geqslant 2$ in two ways. First is by case-work on $x$ . For each fixed $x=2,3,\ldots,n$ , the condition on $y$ is $y\leqslant \log_x n$ , so there are exactly $\left\lfloor \log_x n\right\rfloor$ values of $y$ satisfying the condition. So the number of pairs $(x,y)$ is exactly

$\displaystyle \left\lfloor \log_{2}{n} \right\rfloor + \left\lfloor \log_{3}{n}\right\rfloor + \cdots + \left\lfloor\log_{n}{n}\right\rfloor.$

We can also count by case-work on the value of $y$ . (Note that $y$ can’t be greater than $n$ since $2^{n+1}>n\geqslant x^y\geqslant 2^y$ .) For a fixed $y$ , the condition on $x$ is $2\leqslant x\leqslant \sqrt[y]{n}$ , so there are exactly $\lfloor \sqrt[y]{n} \rfloor -1$ such $x$ . So, the number of pairs $(x,y)$ is exactly

$\displaystyle (n-1)+(\lfloor \sqrt[2]{n} \rfloor -1)+(\lfloor \sqrt[3]{n} \rfloor -1)+\cdots +(\lfloor \sqrt[n]{n} \rfloor -1)=\lfloor \sqrt[2]{n} \rfloor +\lfloor \sqrt[3]{n} \rfloor +\cdots+ \left\lfloor\sqrt[n]{n} \right\rfloor,$

which completes our proof. $\blacksquare$

Comment. This problem is one of the classic examples of double counting – it’s literally just counting some set of points by rows and columns. If the reader is interested, ELMO 2015 Problem 2 is a similar problem.

H1 [China MO 1993] ( $\beta = 4.2$ )
Let $f$ be a function from the positive real numbers to the positive real numbers such that $f(xy)\leqslant f(x)f(y)$ for any positive real numbers $x$ and $y$ . Prove that for any positive real number $x$ and all positive integers $n$ ,

$\displaystyle f(x^n)\leqslant f(x)f(x^2)^{\frac{1}{2}}\cdots f(x^n)^{\frac{1}{n}}.$

Solution. Let $F_n(x)=f(x)f(x^2)^{\frac{1}{2}}\cdots f(x^n)^{\frac{1}{n}}$ for every positive real $x$ . We’ll prove by induction on $n$ that $F_n(x)\geqslant f(x^n)$ for every positive real $x$ . The base case $n=1$ is obvious. For the inductive step, it suffices to note that if $F_n(x)\geqslant f(x^n)$ for all $n=1,2,\ldots, m$ then

$\begin{aligned} F_{m+1}(x)^{m+1} & = F_m(x)^{m+1}f(x^{m+1}) \\ & = F_m(x)^mf(x^{m+1})F_m(x) \\ & = F_{m-1}(x)^mf(x^m)f(x^{m+1})F_m(x)\\ & = \cdots \\ & = f(x)f(x^2)\cdots f(x^{m+1})F_m(x)F_{m-1}(x) \cdots F_1(x) \\ & \geqslant f(x)f(x^2) \cdots f(x^{m+1})f(x^m)f(x^{m-1})\cdots f(x) \\ & = (f(x)f(x^m))(f(x^2)f(x^{m-1}))\cdots (f(x^m)f(x))f(x^{m+1})\\ & \geqslant f(x^{m+1})^{m+1}. \quad \blacksquare \end{aligned}$

Comment. This problem employs mathematical induction in an ingenious way.

The InfinityDots Project

because math is for everyone

POTWs 1 Solutions

Leave a comment Cancel reply

Share this:

Related

Leave a comment Cancel reply