11
$\begingroup$

This is supposedly a problem from a $\textbf{Chinese Math Olympiad team selection test}$ but it looks like an interesting combination of combinoatorics and number theory.

$\textbf{Problem:}$ We have two positive decimal fractional numbers

$X=0.x_1 x_2 ... x_k$ and $Y=0.y_1 y_2 ... y_k$. here $x_k$ and $y_k$ can be zero.

Let $S$ be the number of decimals $0.z_1 z_2 ... z_k$ that satisfy $0.z_1 z_2 ... z_k < X$ and $0.z_k z_{k-1} ...z_1 < Y$ (and similarly $z_k$ and $z_1$ can both be zero), and we view $0.100$ and $0.1$ as the same number.

Prove that $|S - 10^k XY | \leq 9k$

So obviously $10^k$ is the number of decimal $0.z_1 z_2 ... z_k$. What's really awkward is the multiplication of $XY$. I cannot come up with a combinatoric explanation for $XY$ to convert this into an enumeration problem

$\endgroup$
6
  • 1
    $\begingroup$ This looks like a really nice but hard problem $\endgroup$ Commented Aug 18, 2020 at 14:33
  • $\begingroup$ I think it would be helpful to try to figure out when equality holds or is this a strict inequality. $\endgroup$
    – ShBh
    Commented Aug 19, 2020 at 2:41
  • $\begingroup$ I did an exhaustive numerical test for $k = 1,2,3$ (I think the time required should be roughly proportional to $10^{k+1}$, so, with my not optimized software, be some hours for $k = 4$), and searched for the maximum value $d = \max |S - 10^k XY|$ with the following results: $k = 1, d = 2.5, S = 5$ at $X = 0.5, Y = 0.5$; $k = 2, d = 4.75, S = 25$ at $X = 0.45, Y = 0.45$; $k = 3, d = 7.025, S = 255$ at $X = 0.545, Y = 0.455$. The value of $|S - 10^k XY|$ at $k = 2, X = Y = 0.55$ is $4.75$ and at $k = 3, X = Y = 0.555$ is $6.975$. It thus looks like the maximum is at $X \approx Y \approx 5/9$. $\endgroup$ Commented Aug 20, 2020 at 11:31
  • 1
    $\begingroup$ On a very intuitive basis, the first $k/2$ elements in the $z$ sequence are determined by $X$ and the last $k/2$ are determined by $Y$. There will be $X10^{k/2}$ first halves that are less than $X$ and $Y10^{k/2}$ second halves that are less than $Y$, so $XY10^k$ full sequences that are less than both. $9k$ is a very tight bound, however. $\endgroup$ Commented Aug 22, 2020 at 23:44
  • $\begingroup$ The limit of $9k$ suggests that there is only one position in the sequence where it changes from being acceptable to unacceptable. I think this is the key to the proof. $\endgroup$ Commented Aug 23, 2020 at 3:48

1 Answer 1

1
$\begingroup$

This is not a full answer but too long for a comment. I just solve the cases $k = 1$ and $k = 2$ and show how induction could possibly be applied for a full solution.

We first want to compute $S$ exactly as an expression of $X$ and $Y$ digits. To do that, we define $S_k(X, Y)$ as the number of decimal numbers $0.z_1z_2 \ldots z_k$ that satisfy $0.z_1z_2 \ldots z_k < X$ and $0.z_kz_{k-1} \ldots z_1 < Y$.

We then compute $S_1$:

$$ S_1(0.x_1, 0.y_1) = \min\{x_1, y_1\} $$

assuming e.g. $\min\{x_1, y_1\} = x_1$ we have:

$$ S_1(0.x_1, 0.y_1) - 10XY = x_1 - \frac{x_1y_1}{10} = x_1\left(1 - \frac{y_1}{10} \right) \le 9\left(1 - \frac{y_1}{10} \right) \le 9$$

Then, let's compute $S_2$. We can note that all $0.z_1z_2$ with $z_1 < x_1$ and $z_2 < y_1$ satisfy the requirements: the number of these is $x_1y_1$ ($z_1 = 0,1, \ldots ,x_1-1$ and $z_2 = 0,1, \ldots ,y_1-1$). We have left out the cases $z_1 = x_1$ and $z_2 = y_1$. When $z_1 = x_1$ the problem reduces to $0.x_1z_2 \lt 0.x_1x_2$ and $0.z_2x_1 \lt 0.y_1y_2$. The first one is equivalent to $z_2 \lt x_2$ while the second one is equivalent to $z_2 \lt y_1$ when $x_1 \ge y_2$ and $z_2 \lt y_1+1$ when $x_1 < y_2$. When $z_2 = y_1$ the problem reduces to $0.z_1y_1 \lt 0.x_1x_2$ and $0.y_1z_1 \lt 0.y_1y_2$. The second one is equivalent to $z_1 \lt y_2$ while the first one is equivalent to $z_1 \lt x_1$ when $y_1 \ge x_2$ and $z_1 \lt x_1+1$ when $y_1 < x_2$. We can count these solutions with the function:

$$ f(u_1,u_2,v_1,v_2) = \begin{cases} \min\{u_2,v_1\}, & \text{if $u_1 \ge v_2$} \\ \min\{u_2,v_1+1\}, & \text{if $u_1 \lt v_2$} \end{cases} $$

So the solutions when $z_1 = x_1$ are $f(x_1,x_2,y_1,y_2)$ and when $z_2=y_1$ they are $f(y_1,y_2,x_1,x_2)$. For the inclusion-exclusion principle, we must then subtract the possible solution with both $z_1 = x_1$ and $z_2 = y_1$:

$$ g(x_1,x_2,y_1,y_2) = \begin{cases} 1, & \text{if $0.x_1y_1 \lt 0.x_1x_2$ and $0.y_1x_1 \lt 0.y_1y_2$} \\ 0, & \text{otherwise} \end{cases} $$

Combining the above we have:

$$S_2(0.x_1x_2, 0.y_1y_2) = x_1y_1 + f(x_1,x_2,y_1,y_2) + f(y_1,y_2,x_1,x_2) - g(x_1,x_2,y_1,y_2)$$

and

$$S_2(0.x_1x_2, 0.y_1y_2) - 100XY = x_1y_1 + f(x_1,x_2,y_1,y_2) + f(y_1,y_2,x_1,x_2) - g(x_1,x_2,y_1,y_2) - \frac{(10x_1 + x_2)(10y_1 + y_2)}{100} = x_1y_1 + f(x_1,x_2,y_1,y_2) + f(y_1,y_2,x_1,x_2) - g(x_1,x_2,y_1,y_2) - x_1y_1 - \frac{x_1y_2}{10} - \frac{x_2y_1}{10} -\frac{x_2y_2}{100} \le f(x_1,x_2,y_1,y_2) + f(y_1,y_2,x_1,x_2) \le 9 + 9 = 18$$

We can continue by induction, with a step like this:

$$ S_k(0.x_1x_2 \ldots x_k, 0.y_1y_2 \ldots y_k) \approx 10^{k-2}x_1y_1 + S_{k-1}(0.x_2 \ldots x_k, 0.y_1 \ldots y_{k-1}) + S_{k-1}(0.x_1 \ldots x_{k-1}, 0.y_2 \ldots y_k) - S_{k-2}(0.x_2 \ldots x_{k-1}, 0.y_2 \ldots y_{k-1})$$

where the first addendum is $10^{k-2}x_1y_1$ because we have $z_2 \ldots z_{k-1}$ digits that can range from $0$ to $9$ when $z_1 < x_1$ and $z_k < y_1$.

It think it can be seen with some algebra that $S_k$ is near to $10^{k}XY$. The problem is corner cases that we must handle replacing $S_{k-1}$ and $S_{k-2}$ in the induction step with a function like the above $f$ that we have used instead of $S_1$. We cannot use an approximation e.g. like $S_{k-2} \le \ldots$ because $S_{k-2}$ is subtracted. Also, we must verify that $S - 10^kXY \ge 0$ always or handle cases when $S - 10^kXY \lt 0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .