Problem A. 849. (March 2023)
A. 849. For real number \(\displaystyle r\) let \(\displaystyle f(r)\) denote the integer that is the closest to \(\displaystyle r\) (if the fractional part of \(\displaystyle r\) is 1/2, let \(\displaystyle f(r)\) be \(\displaystyle r-1/2\)). Let \(\displaystyle a>b>c\) rational numbers such that for all integers \(\displaystyle n\) the following is true: \(\displaystyle f(na)+f(nb)+f(nc)=n\). What can be the values of \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\)?
Submitted by Gábor Damásdi, Budapest
(7 pont)
Deadline expired on April 11, 2023.
First observation:
\(\displaystyle f(x)+f(-x)=0\), except for the case when the fractional part of \(\displaystyle x\) is \(\displaystyle \frac{1}{2}\), in which case \(\displaystyle f(x)+f(-x)=-1.\)
We know that for every \(\displaystyle n\)
\(\displaystyle f(na)+f(nb)+f(nc)+f(-na)+f(-nb)+f(-nc)=n-n=0,\)
which is only possible if the fractional parts of \(\displaystyle na\), \(\displaystyle nb\) and \(\displaystyle nc\) are not \(\displaystyle \frac{1}{2}\) for every \(\displaystyle n\)-re, thus using the simplied form of \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) the denominators must be odd.
Second observation:
The difference between \(\displaystyle n(a+b+c)\) and \(\displaystyle f(na)+f(nb)+f(nc)=n\) can be at most \(\displaystyle \frac{3}{2}\), thus dividing by \(\displaystyle n\) we get the following for every \(\displaystyle n\):
\(\displaystyle 1-\frac{3}{2n}\le a+b+c\le 1+\frac{3}{2n}.\)
Thus \(\displaystyle a+b+c=1\).
Third observation:
If we write a number as the sum of its integer and its fractional part, \(\displaystyle x=\lfloor x \rfloor+\{x\}\), then for all \(\displaystyle n\) \(\displaystyle f(nx)=n\lfloor x \rfloor+f(n\{x\}).\)
Since \(\displaystyle \lfloor a \rfloor+\lfloor b \rfloor+\lfloor c \rfloor\) is integer and \(\displaystyle a+b+c=1\), \(\displaystyle \{a\}+\{b\}+\{c\}\) is also an integer. Clearly \(\displaystyle 0\le \{a\}+\{b\}+\{c\}<3.\)
\(\displaystyle \{a\}+\{b\}+\{c\}=0\) implies that \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) are all integers and their sum is \(\displaystyle 1\). In this case \(\displaystyle f(na)=na\), \(\displaystyle f(nb)=nb\) and \(\displaystyle f(nc)=nc\), thus indeed \(\displaystyle f(na)+f(nb)+f(nc)=n\).
If \(\displaystyle \{a\}+\{b\}+\{c\}=1\), then \(\displaystyle \lfloor a \rfloor+\lfloor b \rfloor+\lfloor c \rfloor=0\), and thus for every \(\displaystyle n\): \(\displaystyle n\lfloor a \rfloor+n\lfloor b \rfloor+n\lfloor c \rfloor=0,\) and consequently for every \(\displaystyle n\): \(\displaystyle f(n\{a\})+f(n\{b\})+f(n\{c\})=n\).
We can also observe that
\(\displaystyle f(nx)=n(\lfloor x\rfloor +1)-f(n(1-\{x\}))\)
is true, unless the fractional part of \(\displaystyle nx\) is \(\displaystyle \frac{1}{2}\), but we have already established that this is not the case for \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\).
If \(\displaystyle \{a\}+\{b\}+\{c\}=2,\) then
\(\displaystyle n(\lfloor a\rfloor +1)+n(\lfloor b\rfloor +1)+n(\lfloor c\rfloor +1)=2n,\)
thus
\(\displaystyle f(n(1-\{a\}))+f(n(1-\{b\}))+f(n(1-\{c\}))=n\)
for every \(\displaystyle n\).
So far we have proved that \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) are integers, or \(\displaystyle a=m_1+a'\), \(\displaystyle b=m_2+b'\) and \(\displaystyle c=m_3+c'\), where \(\displaystyle m_1+m_2+m_3=0\) integers, or \(\displaystyle a=m_1-a'\), \(\displaystyle b=m_2-b'\) and \(\displaystyle c=m_3-c'\), where \(\displaystyle m_1+m_2+m_3=2\) integers, and in both cases \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\) are non-negative rational numbers satisfying
\(\displaystyle f(na')+f(nb')+f(nc')=n.\)
It is also clear that if we find integers \(\displaystyle m_1, m_2, m_3\) then the above constructions give solutions for \(\displaystyle a, b, c\). Thus we have reduced the problem to the non-negative case.
—–
First consider the case when one of the numbers is \(\displaystyle 0\):
Let \(\displaystyle a'=0\) és \(\displaystyle c'=1-b'\). In this case (since the fractional part of \(\displaystyle nb'\) is never \(\displaystyle \frac{1}{2}\)) \(\displaystyle f(nc')=n+f(-nb')=n-f(nb')\), and thus the condition is fulfilled. So if the denominator of \(\displaystyle b'\) is odd, then \(\displaystyle 0\), \(\displaystyle b'\) and \(\displaystyle 1-b'\) is a solution.
Now we assume that \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\) are positive rational numbers.
—
During the solution \(\displaystyle x\), \(\displaystyle y\) and \(\displaystyle z\) denote one of the numbers \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\).
Let us create sequence \(\displaystyle S\) from \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\) such that \(\displaystyle n^{\text{th}}\) member is \(\displaystyle x\) if \(\displaystyle f(nx)>f((n-1)x)\). Since \(\displaystyle f\) is increasing and \(\displaystyle f(na')+f(nb')+f(nc')=1+f((n-1)a')+f((n-1)b')+f((n-1)c')\), this means that for every \(\displaystyle n\) exactly one of the values of \(\displaystyle f(na')\), \(\displaystyle f(nb')\) and \(\displaystyle f(nc')\) will be greater then the corresponding value of \(\displaystyle f((n-1)a')\), \(\displaystyle f((n-1)b')\) or \(\displaystyle f((n-1)c')\), thus sequence \(\displaystyle S\) is well defined. All three values \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\) will appear in sequence \(\displaystyle S\) since for a positive \(\displaystyle x\) there exists \(\displaystyle n\) for which \(\displaystyle f(nx)\) is not \(\displaystyle 0\).
Let \(\displaystyle K\) be the common denominator of rational numbers \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\). Then sequence \(\displaystyle S\) is periodic by \(\displaystyle K\). We can also observe that \(\displaystyle S_n\) and \(\displaystyle S_{1-n}\) is the same, since \(\displaystyle nx\) will jump over a number with fractional part \(\displaystyle \frac{1}{2}\) compared to \(\displaystyle (n-1)x\) if and only if \(\displaystyle -(n-1)x\) jumps over a number with fractional part \(\displaystyle \frac{1}{2}\) compared to \(\displaystyle -nx\) (again, we use the fact that the fractional part of \(\displaystyle nx\) cannot be \(\displaystyle \frac{1}{2}\)). This means that sequence \(\displaystyle S\) has a center of symmetry.
Let us also observe that for an arbitrary positive integer \(\displaystyle k\) the number of occurences of \(\displaystyle x\) for \(\displaystyle k\) consecutive members of \(\displaystyle S\) can be the floor or ceiling of \(\displaystyle kx\), thus the number of occurrences of \(\displaystyle x\) for two sequences of \(\displaystyle k\) consecutive members of \(\displaystyle S\) can be at most one.
Consider the first \(\displaystyle K\) members of \(\displaystyle S\). Let the first \(\displaystyle t\) members of \(\displaystyle S\) be \(\displaystyle x\). Then we have already seen that the last \(\displaystyle t\) members of this block is also \(\displaystyle x\). This means that we have a block of \(\displaystyle 2t\) \(\displaystyle x\)'s (the union of the last \(\displaystyle t\) elements of the first block and the first \(\displaystyle t\) elements of the second block). We know that we have the same element at both ends of this block, which we call \(\displaystyle y\). Every block of \(\displaystyle 2t\) consecutive elements must contain at least \(\displaystyle 2t-1\) \(\displaystyle x\)'s, thus when we find \(\displaystyle z\) in the sequence, on both sides of it we must have at least \(\displaystyle 2t-1\) \(\displaystyle x\)'s. Thus we have a block of \(\displaystyle 4t-1\) members not containing \(\displaystyle y\), but we also know a block of \(\displaystyle 2t+2\) members that contain two \(\displaystyle y\)'s, thus every block of \(\displaystyle 2t+2\) elements has to contain at least a \(\displaystyle y\), and thus \(\displaystyle 2t+2>4t-1\), thus \(\displaystyle t=1\). We also know that \(\displaystyle S\) starts with \(\displaystyle xy\), and because of the symmetry we have discussed earlier, there is a block of \(\displaystyle yxxy\).
Now let's make some simple observations about \(\displaystyle S\):
(1) because of \(\displaystyle xx\) we have at least one \(\displaystyle x\) among any two consecutive elements. This also means that \(\displaystyle y\) and \(\displaystyle z\) cannot be next to each other.
(2) because of block \(\displaystyle yxxy\), we must have a \(\displaystyle y\) among any four consecutive elements.
(3) the environment of \(\displaystyle z\) must be \(\displaystyle yxzxy\). Indeed, the neighbors of \(\displaystyle z\) must be \(\displaystyle x\)'s, and then the second neighbors must be \(\displaystyle y\)'s, otherwise we would have four consecutive elements with no \(\displaystyle y\) among them.
(4) since we have a block of \(\displaystyle yxz\), this means that we cannot have more than two \(\displaystyle x\)'s among three consecutive elements.
(5) since we have a block of \(\displaystyle yxzxy\), we cannot have more than three \(\displaystyle x\)'s among fice consecutive elements. This also means that two blocks of two \(\displaystyle x\)'s cannot be separated with a single element.
(6) since we have a block of \(\displaystyle xzx\), any three consecutive elements can contain at most one \(\displaystyle y\).
\(\displaystyle S\) starts with \(\displaystyle xy\). According to (1), it has to continue with \(\displaystyle x\). According to (5), the fourth element cannot be \(\displaystyle x\), and according to (6) it cannot be \(\displaystyle y\). Thus it continues with \(\displaystyle z\). Now using (3) we get that \(\displaystyle S\) starts with \(\displaystyle xyxzxy\). Again, by (1) it continues with \(\displaystyle x\). Thus the beginning of \(\displaystyle S\) is \(\displaystyle xyxzxyx\). We will prove that this is a period of \(\displaystyle S\).
(7) if we go in the negative direction, we get a block of \(\displaystyle xyxxyx\). Thus any six consecutive elements can contain at most one \(\displaystyle z\).
Based on (6), \(\displaystyle xyxzxyx\) cannot continue with \(\displaystyle y\), and based on (7) it cannot continue with \(\displaystyle z\). Thus we have an \(\displaystyle x\), yielding a block of \(\displaystyle xx\).
After \(\displaystyle xx\), we cannot have \(\displaystyle x\) (4) and we cannot have \(\displaystyle z\) (3), thus it must be \(\displaystyle y\). Now we must have an \(\displaystyle x\) again (1). After \(\displaystyle xxyx\) we cannot have \(\displaystyle x\) (5) and cannot have \(\displaystyle y\) (6), thus we have \(\displaystyle z\). Now we use 5 to get \(\displaystyle xxyxzxy\). Then we have an \(\displaystyle x\) (1), and then we cannot have \(\displaystyle y\) (6) and cannot have \(\displaystyle z\) (7), so we have \(\displaystyle xx\) again. This means a repeating pattern, because we have shown in this paragraph how can we continue \(\displaystyle xx\).
Thus \(\displaystyle K=7\), so the common denominator of \(\displaystyle a'\), \(\displaystyle b'\) and \(\displaystyle c'\) must be 7. Since \(\displaystyle S_1=x\), \(\displaystyle x\) must be greater than \(\displaystyle \frac{1}{2}\), so at least \(\displaystyle \frac{4}{7}\). We cannot have two equal fractions, thus the other two must be \(\displaystyle y=\frac{2}{7}\) and \(\displaystyle z=\frac{1}{7}\) (since their sum is 1). It is easy to check that these give the desired repeating pattern of \(\displaystyle xyxzxyx\), and thus they yield a good solution.
—
Summarizing the above the solutions are:
1.) \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) are integers and \(\displaystyle a+b+c=1\).
2.) \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) are of form \(\displaystyle m_1\), \(\displaystyle m_2+r\) and \(\displaystyle m_3-r\) where \(\displaystyle m_1+m_2+m_3=1\) integers and \(\displaystyle r\) is a rational number with an odd denominator.
3.) \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) are of the form \(\displaystyle m_1+\frac{1}{7}\), \(\displaystyle m_2+\frac{2}{7}\) and \(\displaystyle m_3+\frac{4}{7}\), where \(\displaystyle m_1+m_2+m_3=0\) integers.
4.) \(\displaystyle a\), \(\displaystyle b\) and \(\displaystyle c\) are \(\displaystyle m_1-\frac{1}{7}\), \(\displaystyle m_2-\frac{2}{7}\) and \(\displaystyle m_3-\frac{4}{7}\), where \(\displaystyle m_1+m_2+m_3=2\) integers.
Statistics:
11 students sent a solution. 7 points: Móricz Benjámin, Sida Li, Varga Boldizsár. 2 points: 1 student. 1 point: 2 students. 0 point: 5 students.
Problems in Mathematics of KöMaL, March 2023