In the previous 5 parts, I described several theorems which are useful for finding the maximum value of a function $f$ over integers.  In parts 1, 2, and 3, $f$ was concave.  In part 4, $f$ was continuous.  And in part 5, there were no restrictions on $f$.  In this post, the focus is on finding the maximum value of an investment game function over integers.

What is the maximum of $$f(x)=\exp(\alpha x) (T-x)$$ over all integers?  This function appears in several investment board games including Terraforming Mars, Master of Orion, and Roll for the Galaxy.

EXAMPLE $f(x)=\exp(\alpha x) (T-x)$

Let’s find the maximum of $f:\mathbb{R}\rightarrow\mathbb R$ where $$f(x)=\exp(\alpha x) (T-x),$$ $\alpha>0$, and $T>0$. The $\exp(\alpha x)$ is always postive, so $$f(x)>0\quad\mathrm{\ if\ and\ only\ if\ } x<T.$$

Let $g(x) = f(x+1) – f(x)$ as in “Maximizing a Function over Integers (Part 5)“. Let $\beta=\exp(\alpha)$. We can use some algebra to better understand the behavior of $g$.

$$\begin{aligned}g(x) &= f(x+1) – f(x)\\&= \exp(\alpha (x+1)) (T-(x+1)) – \exp(\alpha x) (T-x)\\&= \beta\beta^x (T-x -1) – \beta^x (T-x)\\&= \beta^x [ \beta(T-x -1) - T+x]\\&=\beta^x [ (1-\beta) x + (\beta-1) T -\beta]\\&=\beta^x [ (\beta-1)(T-x) -\beta].\end{aligned}
$$

So $g(x)>0$ if and only if

$$\begin{aligned}(\beta-1)(T-x) -\beta &>0\\(\beta-1)(T-x) &>\beta\\T-x &>\frac{\beta}{\beta-1} \\T- \frac{\beta}{\beta-1} &> x\\\gamma &> x\end{aligned}
$$
where $$\gamma=T- \frac{\beta}{\beta-1}.$$ Consequently,

$g(x)<0$ if and only if $\gamma < x$,

and by reversing the inequalities in the argument above,

$g(x)>0$ if and only if $\gamma > x$.

(This statement implies that if we restrict $f$ to integer inputs, then $f$ is increasing for inputs less than $\gamma-1$ and decreasing for inputs greater than $\gamma$.)

We can apply the lemmas from Part 5 to conclude that

– if $\gamma$ is an integer, then the maximum value of $f$ amoung all integers is $f(\gamma)$ which is also equal to $f(\gamma+1)$, and
– if $\gamma$ is not an integer, then the maximum value of $f$ amoung all integers is $f(\mathrm{ceil}(\gamma))$ and that maximum value is only attained by the input $\mathrm{ceil}(\gamma)$.

(Technical note: The lemmas in Part 5 can be applied with $b=T+1$ and and real number $a<\gamma-1$.)

$f(x) = 1.1^x (100-x)$

For example, if $$f(x) = 1.1^x (100-x)=\exp(\alpha x)(T-x)$$ with $\alpha=\log(1.1)$ and $T=100$, then

$$\begin{aligned}\beta=\exp(\alpha)&=\exp(\log(1.1)) = 1.1,\quad\mathrm{and}\\ \gamma= T- \frac{\beta}{\beta-1}&= 100- \frac{1.1}{1.1-1}= 100 -11 = 89.\end{aligned}$$

We conclude that the maximum value of $f$ over all integers is $$f(\gamma) =f(\gamma+1) = f(89)=f(90)\approx53130.2$$ Note that $f(88) \approx 52691.1$ and $f(91)\approx 52598.9$.

$f(x)=(1+1/k)^x(T-x).$ for any positive integer $k$

More generally, let $k$ be any positive integer and let $$f(x)=(1+1/k)^x(T-x).$$
Then $$f(x)=\exp(\alpha x)(T-x)$$ with $\alpha=\log(1+1/k),$

$$\begin{aligned}\beta=\exp(\alpha)&=\exp(\log(1+1/k)) =1+1/k,\quad\mathrm{and}\\\gamma= T- \frac{\beta}{\beta-1}&= T – \frac{1+1/k}{1+1/k-1}= T- (k+1) .\end{aligned}$$

We conclude that the maximum value of $f$ over all integers is $$f(\gamma) =f(\gamma+1) = f(T-k-1)=f(T-k).$$

AcknowledgmentS

Thanks to stackedit.io for helping me write the TeX.  GPT3 also recommended a change to one of the sentences in the introductory paragraph.

In parts 1,2, and 3, I described some theorems about finding the integer $i$ which maximizes $f(i)$, the value of a concave function $f:[a,b]\rightarrow \mathbb R$.  In part 4, I described a theorem for finding integers $i$ which maximize $f(i)$ where $f:[a,b]\rightarrow \mathbb R$ is a continuous function.  In part 5, I will describe some rather obvious, but useful facts and lemmas for finding integers $i$ which maximize $f(i)$ for any function $f:[a,b]\rightarrow \mathbb R$.

NOTATION

•  $[a,b]$ is the set of real numbers $x$ where $a\leq x \leq b$, and $a$ and $b$ are real numbers.
• $f:[a,b]\rightarrow \mathbb R$ means that the function $f$ takes as input real numbers from $[a,b]$ and gives as outputs real numbers.  More generally, the notation  $f:A\rightarrow B$ denotes a function $f$ where the input elements are from set $A$ and the outputs are in set $B$.  For example, we could define $f:[1, 10]\rightarrow \mathbb R$ by $f(x) =\log(x)$ for real numbers $x$ between 1 and 10 where the outputs are real numbers.
• We will use  floor$(x)$  to denote the largest integer less than or equal to $x$. You can think of floor($x$) as rounding $x$ down.
• We will use  ceil$(x)$  to denote the smallest integer greater than or equal to $x$.  You can think of ceil($x$) as rounding $x$ up.

MAIN ASSUMPTION

For the rest of this post assume that $a$ and $b$ are real numbers, $a+1\leq b$, and $f$ is a real valued function with domain [a,b].  $f:[a,b] \rightarrow\mathbb{R}$, .

DEFINITIONS

• We say that a function $f$ is increasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) \leq f(x_2).$$ As the value of $x$ increases, the function increases.  If the function is differentiable, this is equivalent to the derivative being non-negative.
• We say that a function $f$ is strictly increasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) <f(x_2).$$If the function is differentiable, this is almost the same as the derivative being positive.
• We say that a function $f$ is decreasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) \geq f(x_2).$$ As the value of $x$ increases, the function decreases.  If the function is differentiable, this is equivalent to the derivative being non-positive.
• We say that a function $f$ is strictly decreasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1)>f(x_2).$$ If the function is differentiable, this is almost the same as the derivative being negative.

SOME OBVIOUS YET USEFUL FACTS

1. If $f$ is a strictly increasing function, then the integer $i$ that maximizes $f(i)$ is $\mathrm{floor}(b)$.
2. If $f$ is an increasing function, then the set of integers that maximize $f$ is non-empty and has the form $\{j,j+1, j+2, \ldots, \mathrm{floor}(b)\}$ where $j$ is an integer and $a\leq j\leq b$.
3. If $f$ is a strictly decreasing function, then the integer $i$ that maximizes $f(i)$ is $\mathrm{ceil}(a)$.
4. If $f$ is a decreasing function, then the set of integers that maximize $f$ is non-empty and has the form $\{\mathrm{ceil}(a),\mathrm{ceil}(a)+1,\ldots, j\}$ where $j$ is an integer and $a\leq j\leq b$.
5. Suppose that the integer $i$ maximizes $f(i)$. Then either

5a) $i=\mathrm{ceil}(a)$ or $i=\mathrm{floor}(b)$ (i.e. $i$ is on the “border” of $[a,b]$), or

5b) $a+1\leq i \leq b-1$, $g(i-1) \geq 0$, and $g(i)\leq 0$ where $$g:[a, b-1]\rightarrow\mathbb R \quad\mathrm{and}\quad g(x) = f(x+1) – f(x).$$ This is equivalent to $f(i-1) \leq f(i)$ and $f(i) \geq f(i+1)$.

 TWO LEMMAS

Fact 5 is related to the following two lemmas. Assume that

• the function $g:[a, b-1]\rightarrow\mathbb{R}$ is defined by $g(x) = f(x+1) – f(x)$,
• $\gamma$ is a real number where $a+1\leq \gamma \leq b-1$,
• $g(x)>0$ if and only if $\gamma > x$, and
• $g(x)<0$ if and only if $x>\gamma$.

Lemma 1: If $\gamma$ is an integer, then the set of integers that maximize $f$ is $\{\gamma, \gamma+1\}$.
Lemma 2: If $\gamma$ is not an integer, then the unique integer that maximizes $f$ is $\mathrm{ceil}(\gamma).$

Proof: Let $i$ be an integer in $[a,b]$ that maximizes $f(i)$. (i.e. $f(i)\geq f(j)$ for all integers $j$ in $[a,b]$.)

If $\gamma > i$ then $g(i)>0$ which implies that $f(i+1)> f(i)$ in which case $f(i)$ is not the maximum of $f$ over all integers in $[a,b]$ contradicting the definition of $i$. Hence $\gamma\leq i$.

If $i-1>\gamma$ then $g(i-1)<0$ which implies that $f(i)< f(i-1)$ and again $f(i)$ is not the maximum of $f$ over all integers in $[a,b]$ contradicting the definition of $i$. Hence $i \leq \gamma+1$.

We conclude that $\gamma\leq i \leq \gamma +1$.

If $\gamma$ is not an integer, then $i=\mathrm{ceil}(\gamma)$ proving Lemma 2.

Notice that $g(\gamma)=0$, so $f(\gamma) = f(\gamma+1)$.  If $\gamma$ is an integer, then $i$ can be either $\gamma$ or $\gamma+1$ proving Lemma 1.

About two years ago, I wrote 3 posts about finding the maximum of a real valued concave functions over a set of consecutive integers.

http://artent.net/2020/12/25/maximizing-a-function-over-integers-part-1/

There is a related theorem for continuous functions.

Theorem:  Suppose that $f:[a,b] \rightarrow\mathbb R$ is continuous with $a+1\leq b$. Let
$$m=\max_{i\in \mathbb Z\cap[a,b]} f(i)\quad\mathrm{and}\quad S=\{ i\in \mathbb Z\cap[a,b]\, | f(i)= m\}.$$
Then $S$ is non-empty, and for all $i\in S\cap[a+1, b-1]$, there exists an $x(i)$ such that $$f(x(i)) = f(x(i)+1)$$ and $x(i)\leq i \leq x(i)+1.$

This is very nice if it is easy to find all the solutions to $f(x) = f(x+1)$ where $a\leq x \leq b$.  If you find those solutions, then the maximizer of $f$ over the set of integers in $[a,b]$ is either the smallest integer in $[a, b]$, the largest integer in $[a, b]$, or it is in the set $[x,x+1]$ where $x$ is one of the solutions to $f(x)=f(x+1)$.

More formally, if $i$ is an integer in $[a,b]$ and $f(i)\geq f(j)$ for all integers $j\in[a,b]$, then either

1. $i$ is on the “border” of $[a, b]$, i.e. $i\in [a, a+1)\cup (b-1, b]$, or
2. there exists a real number $x\in[a, b-1]$ such that $x\leq i \leq x+1$ and $f(x) = f(x+1).$

Proof of the Theorem:

$S$ is non-empty because $[a,b]\cap\mathbb Z$ is compact. Now for any $i\in S\cap[a+1, b-1]$, one of the three following cases must hold,

Case 1: $f(i-1) = f(i)$. In this case, let $x(i) = i-1$ and the theorem holds.

Case 2: $f(i) = f(i+1)$ In this case, let $x(i) = i$ and the theorem holds.

Case 3: $f(i-1) < f(i)$ and $f(i+1) < f(i)$. For this case, define $g:[a, b-1]\rightarrow \mathbb R$ by $$g(x) = f(x+1) – f(x).$$ The continuity of $f$ implies that $g$ is continuous. Also, $g(i-1) >0$, and $g(i)<0$, so by the intermediate value theorem, there exists an $x^*\in(i-1, i)$ such that
$$\begin{aligned}
g(x^*) &=0\quad\mathrm{thus}\\
f(x^* +1) – f(x^*) &=0.
\end{aligned}$$
Setting $x(i)=x^*$ satisfies the theorem for case 3.

We have shown that in all three cases, there exists an $x(i)$ such that $x(i)\leq i \leq x(i)+1$ and $f(x(i)) = f(x(i)+1)$ proving the theorem.