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 , (where A is natrual number larger than 1) maximized at the second crossings. Why?

Definition. Let  be the largest integer that .

The above claim is equivalent to claiming that  is the global maximum of f.

Theorem. .

Proof. , the result follows.

Theorem. iff .

Proof. Straightforward by direct expansion.

Theorem.  maximized at .

Proof. This is equivalent to .

which can be shown using modular arithmetic. (It isn't hard to check: there are only finite case to check.)

How about the case ?

Note that and let . Consider the case  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  (usually the best answer)
2) Find smallest . For each find so that is maximized in the range .

Complexity? Something like . The problem is how often the answer falls on and how should we make the algorithm more efficient? I would leave that part open.

What about irrational case? Let's talk about them next them.

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
Prroblem: Find to maximize .

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 that converges to . It follows that the sequence is an approximation to that and . Moreover, it follows that for all fractions that . If , the sequence constantly equal to the fraction that equals to .

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

Problem: Find to maximize as defined above, with .

Where should we start with? It is clear that when 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 .

Lemma. For , .

Proof. For , there is a multiplicative inverse of p mod q. Let in , it is clear that .

For , .

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 , then is the optimal answer.

Proof. It is clear that can't be a valid answer, and for all using similar arguement with the lemma. To see that for , notice that so that the integer part of do not increase in the given range, the result immediately follows.

Similarly, if we check all to get the optimal answer. It follows that the optimal answer is at most using the similar arguement.

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

Why 'should'? Think about the situation:

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