Let $r_1,r_2,\ldots,r_m$ be positive rational numbers with a sum of $1$. Find the maximum values of the function $f:\mathbb N\to\mathbb Z$ defined by $$f(n)=n-\lfloor r_1n\rfloor-\lfloor r_2n\rfloor-\ldots-\lfloor r_mn\rfloor$$
Problem
Source:
Tags: algebra, floor function, function, optimization
alexheinis
08.04.2021 14:51
I'm sorry, I misread the problem. I will try again.
Wildabandon
08.04.2021 14:55
alexheinis wrote: Easy, we have $f(n)\ge n-\sum_1^m nr_k =0$ with equality when we choose $n$ such that all numbers $nr_k$ are integer. The problem asks maximum, not minimum.
Joshsssss
08.04.2021 15:05
alexheinis wrote:
Easy, we have $f(n)\ge n-\sum_1^m nr_k =0$ with equality when we choose $n$ such that all numbers $nr_k$ are integer.
Using the comment above. The maximum occurs right before $n$ is the $lcm$ of the denominators and $f(n)$ has a value of $m$ (or at least a value very close to $m$) at that point.
We can prove through:
Showing the sum cannot be greater or equal to $m$
$f(n) = n - \sum_1^m \lfloor nr_k \rfloor = \sum_1^m nr_k - \lfloor nr_k \rfloor$
Since each term can have a maximum difference of $1$ and there are $m$ terms the maximum of the function cannot be greater than $m$.
Showing that $f(n)$ reaches the largest real number less than $m$
$\lfloor nr_k \rfloor$ are all integers when $n$ is a multiple of the $lcm$ of the denominators, thus $f(n) = 0$ at this point. We can conclude that before that, all of the $\lfloor nr_k \rfloor$ terms drop by $1$ making $nr_k - \lfloor nr_k \rfloor$ equal to almost one for every valid value of $k$ and using the logic explained above means the value of $f(n)$ is $m$ (or at least really close to it)
[\hide]
alexheinis
08.04.2021 16:02
@above: we have $f(n)<n-\sum_1^m (nr_k-1)=m$ and since $f(n)$ is integer we have $f(n)\le m-1$. It remains to prove that this value can be attained. Let's take an example: $r_1=1/3,r_2=1/5,r_3=7/15$. Then $f(n)=n-[n/3]-[n/5]-[7n/15]$. If $a:=n \mod 3, b:=n\mod 5, c:=7n\mod 15$ then $f(n)=n-{{n-a}\over 3}-{{n-b}\over 5}-{{7n-c}\over {15}}={{5a+3b+c}\over {15}}$. In this case the choice $a=2,b=4,c=8$ gives $f(n)=2$. I'll work on the general proof and post it when I have it.
Joshsssss
08.04.2021 16:49
@above Woops!!!! Well, I think my solution can be modified for it to work. Firstly note that the graph will always have a slope of $1$ when it does have a slope, and secondly note that since $r_m$ is always less than one (except for the case where $m=1$) there will be no jumps between the interval [c-1,c) where $c$ is the LCM of the denominators as the value $nr_k$ would not have changed enough to influence $\lfloor nr_k \rfloor$. Those two facts together forces the answer to be $m-1$