Wednesday, 22 May 2013

A number theory problem from online games Part 2

Using the same notation as last time we want to show that for $r \in (0,1),r=\frac{p}{q}\in \mathbb{Q}$, $f:A\rightarrow \mathbb{R},f(a)=r-\frac{[ra]}{a}$ (where A is natrual number larger than 1) maximized at the second crossings. Why?

Definition. Let $a_n=\left$\frac{nq}{p} \right$$ be the largest integer that $[ra_n]\leq n$.

The above claim is equivalent to claiming that $f(a_2)$ is the global maximum of f.

Theorem. $f(a_n)=\frac{pa_n-(n-1)q}{a_nq}$.

Proof. $f(a_n)=r-\frac{[ra_n]}{a_n}=\frac{p}{q}-\frac{[\frac{pa_n}{q}]}{a_n}=\frac{p}{q}-\frac{n-1}{a_n}$, the result follows.

Theorem. $f(a_i)\geq f(a_j)$ iff $\frac{a_i}{i-1}\geq \frac{a_j}{j-1}$.

Proof. Straightforward by direct expansion.

Theorem.  $f(a_n)$ maximized at $n=2$.

Proof. This is equivalent to $(k-1)a_2-a_k\geq 0$.

$(k-1)a_2-a_k=(k-1)\left$\frac{2q}{p} \right$ - \left$\frac{kq}{p}\right$\geq 0$ which can be shown using modular arithmetic. (It isn't hard to check: there are only finite case to check.)

How about the case $a_n \leq a \leq a_{n+1}$?

Note that $f(a)=\frac{\left\{ra\right\}}{a}$ and let $f(a_k) = \alpha$. Consider the case $f(a_k)-f(a_k-1)=\frac{\alpha}{a_k}-\frac{\alpha-r}{a_k-1}=\frac{ra_k-\alpha}{a_k(a_k-1)}$ which is larger than zero for large enough a_k. Now we can summarize our approach to find our optimal solution:

Check the following value of a: if they are a better solution replace the current one.
1) The $a_2$ (usually the best answer)
2) Find smallest $a_k \geq r^{-1}$. For each $a_i$ find $a_i-n$ so that $f(a_i-n)$ is maximized in the range $a_{i-1}+1\leq a \leq a_i$.

Complexity? Something like $O(min(\frac{q}{p},q))$. The problem is how often the answer falls on $a_2$ and how should we make the algorithm more efficient? I would leave that part open.