## 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.

## Sunday, 19 May 2013

### A number theory problem from online games Part 1

The situation comes from online game in a very natrual style.

Unlike modern banking system, the statistics (like money) in online games are usually integer, but that makes some problem (to the producer sometimes, and sometimes to players) in particular the statistic conversion.

Like, we are obtaining energy A from energy B at a rate of 36.5%. It is natrual that it takes 365 units of B for us to get 1000 units of A. For what if we want 1 units of A? 3 units?

In the game that I am playing they take the rounding off approach --- of course --- this is beneficial if we goes B->A but not-so-good when we go in another way. For example 1 unit of A is supposed to take 0.365 units of B and now it's rounded off to zero. 3 units of A takes 1 unit of B to convert with. Of course, the system won't let you to obtain 1 unit of A 'with zero unit of B' --- you need at least one unit of input.

The problem comes: in what ratio (in particular, the amount of A I want every time) so that we maximize our gain (i.e. ratio above the supposed rate)? We can now state our problem:

Instance: A real number $r \in (0,1)$
Prroblem: Find $a_0\in \mathbb{N}$ to maximize $f(a_0)=r-\frac{[ra_0]}{a_0}$.

Well, r causes a bit of trouble when it isn't rational, so we modify the instance a bit:

Instance: A sequence of real number $\left\{ r_n \right\} = \left\{\frac{p_n}{q_n}\right\}$ that converges to $r\in (0,1)$. It follows that the sequence is an approximation to $r$ that $p_n,q_n\in \mathbb{N}$ and $(p,q)=1$. Moreover, it follows that $|\frac{p_n}{q_n}-r|\leq |\frac{p}{q}-r|$ for all fractions that $q_n\leq q$. If $r\in \mathbb{Q}$, the sequence constantly equal to the fraction that equals to $r$.

We should also specify that we can't convert to something (larger than zero) using zero resources. So the problem becomes:

Problem: Find $a_0 \in \mathbb{N}$ to maximize $f(a_0)$ as defined above, with $ra_0 \geq 1$.

Where should we start with? It is clear that when $r \in \mathbb{Q}$ the problem can be easily solved. To see this we shall consider rational instance for the rest of (this part of) the passage with the notation $r=\frac{p}{q}$.

Lemma. For $r = \frac{p}{q} \in \mathbb{Q}$, $a_0\leq q-1$.

Proof. For $(p,q)=1$, there is a multiplicative inverse of p mod q. Let $a_0 = p^{-1}$ in $\mathbb{Z}_q$, it is clear that $f(a_0) = \frac{q-1}{a_0q}$.

For $a\geq q$, $f(a)=\frac{k}{aq}\leq \frac{q-1}{aq}\leq \frac{q-1}{a_0q}=f(a_0)$.

It's like that the above lemma gives us a possible answer to the problem, but is it the best answer? Let's divide it in two cases:

Theorem. If $pa_0=q-1$, then $2a_0$ is the optimal answer.

Proof. It is clear that $a_0$ can't be a valid answer, and $f(a)\leq f(2a_0)$ for all $a\geq 2a_0$ using similar arguement with the lemma. To see that $f(a)\leq f(2a_0)$ for $a_0+1\leq a\leq 2a_0$, notice that $a_0p = q-1$ so that the integer part of $\frac{ap}{q}$ do not increase in the given range, the result immediately follows.

Similarly, if $pa_0\geq q$ we check all $1\leq a \leq a_0$ to get the optimal answer. It follows that the optimal answer is at most $a_0$ using the similar arguement.

If we want to be faster, check all crossing and the corresponding $a$ value so that $pa$ is just under the multiple of q, now we should get the answer.

Why 'should'? Think about the situation:

Suppose we get $a_0$ as the 'optimal' answer using the faster way, is $a_0-1$ a better answer? Is this even possible?... We shall see it shortly...