Proving that if $k\ge60$, then there exists an integer $t$ such that $\frac{3}{11}k \le t \le \frac{2}{7}k$

Question

(Sorry for my bad english, first time using stack exchange) I came up with that "conjecture" solving a problem. With Geogebra I saw that is probably true. Since $\frac{2}{7}k-\frac{3}{11}k=\frac{1}{77}k$, one can use this to prove the conjecture for $k\gt77$. I also tried to prove that for a positive integer $k\ge60$ we have that $\lceil\frac{3}{11}k\rceil\le\frac{2}{7}k$, which clearly implies what we want, but i only could improve it to $k\ge76$:
$\mathit{Claim 1}$: Let be k an integer such that $k\ge76$, then $\frac{3}{11}(k+\frac{76}{21})\lt\frac{2}{7}k$
Proof: Can be easily proved by induction. Note that this inequality is not true for $60\le k \le75$. The reason of the choice of $\frac{76}{21}$ is for proving:
$\mathit{Claim2}$: For any integer $k\ge76$ we have that $\lceil\frac{3}{11}k\rceil\le\frac{2}{7}k$.
Proof: Also by induction. For $k=76$ we have $\lceil\frac{3}{11}(76)\rceil = 21 \lt \frac{2}{7}(76) $. Assume that $\lceil\frac{3}{11}k\rceil\le\frac{2}{7}k$ for a $k\ge76$. Since that $\lceil\frac{3}{11}k\rceil\le\lceil\frac{3}{11}(k+1)\rceil$, we have two cases:
Case 1: If $\lceil\frac{3}{11}k\rceil=\lceil\frac{3}{11}(k+1)\rceil$, then: $\lceil\frac{3}{11}(k+1)\rceil=\lceil\frac{3}{11}k\rceil \le \frac{2}{7}k \lt \frac{2}{7}(k+1)$.
Case 2: If $\lceil\frac{3}{11}k\rceil \lt \lceil\frac{3}{11}(k+1)\rceil$, suppose that $\frac{3}{11}(k+1) \lt \lceil\frac{3}{11}k\rceil $, then $$\lceil\frac{3}{11}k\rceil -1 \lt \frac{3}{11}k \lt \frac{3}{11}(k+1) \lt \lceil\frac{3}{11}k\rceil $$ Thus $\lceil\frac{3}{11}(k+1)\rceil= \lceil\frac{3}{11}k\rceil$, contradiction.
Therefore: $\lceil\frac{3}{11}k\rceil \lt \frac{3}{11}(k+1)$. If $\frac{3}{11}(k+1) \gt \lceil\frac{3}{11}k\rceil+1$, then we have $$\frac{3}{11}k + \frac{3}{11} =\frac{3}{11}(k+1) \gt \lceil\frac{3}{11}k\rceil+1 \gt \frac{3}{11}k +1 $$ contradiction. Thus $\lceil\frac{3}{11}k\rceil \lt \frac{3}{11}(k+1) \le \lceil\frac{3}{11}k\rceil+1$ and this implies that $\lceil\frac{3}{11}(k+1)\rceil = \lceil\frac{3}{11}k\rceil+1 $
Now suppose the contrary of the claim: $\lceil\frac{3}{11}(k+1)\rceil\gt\frac{2}{7}(k+1)$. Then, using the previous claim ($k\ge76$), we get
$$\lceil\frac{3}{11}k\rceil+1 = \lceil\frac{3}{11}(k+1)\rceil \gt\frac{2}{7}(k+1) = \frac{2}{7}k + \frac{2}{7} \gt \frac{3}{11}(k+\frac{76}{21}) + \frac{2}{7} = \frac{3}{11}(k+1) + \frac{3}{11}\cdot(\frac{76}{21}-1) + \frac{2}{7} = \frac{3}{11}(k+1) +1 $$ This implies, $\lceil\frac{3}{11}k\rceil\gt\frac{3}{11}(k+1)$, a contradiction, which was possible due to the choice of $\frac{76}{21}$ in Claim 1. Then $\lceil\frac{3}{11}(k+1)\rceil\le\frac{2}{7}(k+1)$. This completes the induction.
Is this proof correct? Can be improved to prove for $k\ge60$? And if not, is there a proof (no matter how complex) that shows directly for $k\ge60$? I will appreciate any help.

Answer 1

Rephrase the problem as like you hinted in the first line:

Show that for $k \geq 60$, there is a multiple of 77 between $21k$ and $22k$.

Then, like you realized, it is clearly true for $ k \geq 77$ because the interval is wide enough.

To be fair, at this point, one can do case-checking and that's the approach I would have taken for expediency. But let's say we want to generalize this, or are working with much larger numbers, or don't know that there are only 17 cases to check.

Extending the approach further, we see that it is also clearly true for $k \geq 76$, because there are 77 integers in the range from $21 \times 76 \leq 77t \leq 22\times 76$, so one of them will be a multiple of 77.
This is a significant simplification of your solution.

Furthermore, we can extend this argument for when we have fewer than 77 numbers. We just need to know how far we are from the multiple of 77, and hope that we have enough of the $k$ numbers to tide us over. If we do not, then we've found the counterexample.
Verify the following

1. If $ k $ is a multiple of 11, clearly it will work.
   • This corresponds to $b= 0 $ case in the next line.
2. If $k = 11a - b$ (with $ 0 \leq b < 11$), and $ k \geq \left[ 21 b \pmod{77} \right]$ (in the reduced residue class), then $k$ would work. Why?

$21 k = 77\times 3a - 21b \leq 77\times t \leq 22k$

3. In fact, for $ k < 76$, this is a necessary and sufficient condition. Why?

What is the length of the interval?

4. Thus, looking at the values of $ 21b\pmod{77}$, we first find the largest value which is $21 \times 7 \equiv 70 \pmod{77}$.
   • The counter example that it will yield, is $11a - 7 < 70$, which gives us $ a = 7, k = 66-7 = 59$.
5. We do have to check if the other cases might yield a smaller counterexample.
   • For most cases, $21b \pmod{77} < 59$ and so we don't have to determine the counterexample.
   • For $ 21 b \equiv 63 \pmod{77}$, we get $ b = 3$, which might produce a counter-example that is greater than 59. In this case, it gives us $11a - 3 < 63$, or that $a = 5, k = 55 - 3 = 52$.
6. Show that we can also do this for $k = 7a + b$, and arrive at the same counterexample.