Maths Olympiad Prep

Library / /32 of 64

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

For each real number xx, let
f(x)=nSx12n, f(x) = \sum_{n\in S_x} \frac{1}{2^n},
where SxS_x is the set of positive integers nn for which nx\lfloor nx \rfloor is even. What is the largest real number LL such that f(x)Lf(x) \geq L for all x[0,1)x \in [0,1)? (As usual, z\lfloor z \rfloor denotes the greatest integer less than or equal to zz.)

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is L=4/7L = 4/7. For SNS \subset \mathbb{N}, let F(S)=nS1/2nF(S) = \sum_{n\in S} 1/2^n, so that f(x)=F(Sx)f(x) = F(S_x). Note that for T={1,4,7,10,}T = \{1,4,7,10,\ldots\}, we have F(T)=4/7F(T) = 4/7.

We first show by contradiction that for any x[0,1)x \in [0,1), f(x)4/7f(x) \geq 4/7.
Since each term in the geometric series n1/2n\sum_n 1/2^n is equal to the sum of all subsequent terms, if S,SS,S' are different subsets of N\mathbb{N} and the smallest positive integer in one of S,SS,S' but not in the other is in SS, then F(S)F(S)F(S) \geq F(S'). Assume f(x)<4/7f(x) < 4/7; then the smallest integer in one of Sx,TS_x,T but not in the other is in TT. Now 1Sx1 \in S_x for any x[0,1)x \in [0,1), and we conclude that there are three consecutive integers n,n+1,n+2n,n+1,n+2 that are not in SxS_x: that is, nx\lfloor nx\rfloor, (n+1)x\lfloor (n+1)x\rfloor, (n+2)x\lfloor (n+2)x\rfloor are all odd. Since the difference between consecutive terms in nxnx, (n+1)x(n+1)x, (n+2)x(n+2)x is x<1x<1, we conclude that nx=(n+1)x=(n+2)x\lfloor nx\rfloor = \lfloor (n+1)x\rfloor = \lfloor (n+2)x\rfloor and so x<1/2x<1/2. But then 2Sx2\in S_x and so f(x)3/4f(x) \geq 3/4, contradicting our assumption.

It remains to show that 4/74/7 is the greatest lower bound for f(x)f(x), x[0,1)x\in [0,1).
For any nn, choose x=2/3ϵx = 2/3-\epsilon with 0<ϵ<1/(9n)0<\epsilon<1/(9n); then for 1kn1\leq k\leq n, we have 0<mϵ<1/30<m\epsilon<1/3 for m3nm \leq 3n, and so
\begin{align*}
\lfloor (3k-2)x \rfloor &= \lfloor (2k-2)+2/3-(3k-2)\epsilon \rfloor = 2k-2 \\
\lfloor (3k-1)x \rfloor &= \lfloor (2k-1)+1/3-(3k-1)\epsilon \rfloor = 2k-1 \\
\lfloor (3k)x \rfloor &= \lfloor (2k-1)+1-3k\epsilon \rfloor = 2k-1.
\end{align*}
It follows that SxS_x is a subset of S={1,4,7,,3n2,3n+1,3n+2,3n+3,}S = \{1,4,7,\ldots,3n-2,3n+1,3n+2,3n+3,\ldots\}, and so
f(x)=F(Sx)f(S)=(1/2+1/24++1/23n+1)+1/23n+1f(x) = F(S_x) \leq f(S) = (1/2+1/2^4+\cdots+1/2^{3n+1})+1/2^{3n+1}. This last expression tends to 4/74/7 as nn\to\infty, and so no number greater than 4/74/7 can be a lower bound for f(x)f(x) for all x[0,1)x\in [0,1).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.