Let $p$ be a prime number. For integers $r, s$ such that $rs(r^2 - s^2)$ is not divisible by $p$, let $f(r, s)$ denote the number of integers $n \in \{1, 2, \ldots, p - 1\}$ such that $\{rn/p\}$ and $\{sn/p\}$ are either both less than $1/2$ or both greater than $1/2$. Prove that there exists $N > 0$ such that for $p \geq N$ and all $r, s$, \[ \left\lceil \frac{p-1}{3} \right\rceil \le f(r, s) \le \left\lfloor \frac{2(p-1)}{3} \right\rfloor. \]
Problem
Source: USA TST 2000, Problem 1
Tags: inequalities, number theory, fractional part
Pascual2005
12.02.2005 21:58
a clue: you can assume $r=1$ mod p.
RobertuX
13.02.2005 01:02
Alexander Lenin wrote: Let p be a prime number. For integers r, s such that rs(r <sup>2</sup> -s <sup>2</sup> ). is not divisible by p, let f(r,s) denote the number of integers n belongs to {1, 2, . . . , p-1}such that {rn/p} and{sn/p} are either both less than 1/2 or both greater than 1/2. Prove that there exists N greater than 0 such that for p >= N and all r, s, [(p-1)/3]+1 <= f(r,s) <= [2(p-1)/3] Sorry for my dude, $\{x\}$ means the rational part? i.e. $x-[x]$? or what!
Pascual2005
13.02.2005 08:45
yes, it does.
Alexander Lenin
13.02.2005 09:40
Alexander Lenin wrote: [(p-1)/3]+1 <= f(r,s) <= [2(p-1)/3] In the left, it means the number is integer but not less than (p-1)/3, but I don't know how to type the symbol of that, and I typed it as [(p-1)/3]+1, but now I know that this is not correct and I had made a mistake, I'm sorry . Who would like to help me in this problem? Thank you!
Alexander Lenin
13.02.2005 09:48
Pascual2005 wrote: a clue: you can assume $r=1$ mod p. Sorry, I can't understand. So... Could you tell me the full procedure if you have time?
Pascual2005
17.02.2005 03:24
well, i have to remember my solution wich was long, so when i do it i will post it. However, here goes the first thing: we can asume $r=1$, because $f(ar,as)=f(r,s)$ since the numbers $a,2a,3a...,(p-1)a$ are $1,2,3...,p-1$ modulo $p$ in some order for $a$ not divisible by $p$. since non of $r$ or $s$ is divisible by $p$, we can put $a=r^{-1}$ and we can asume it. now we must prove $f(1,r)$ satisfy those bounds. since $f(1,r)+f(1,-r)=p-1$ we can assume $r<(p+1)/2$ and work with it. I dont remember how I proceded, so i will try it later, I just have ugly, brute force aproach from here.
Alexander Lenin
17.02.2005 07:38
Wait......
Bluesea
10.03.2006 09:43
i have the offical solution for this problem(of zumingfeng if you want i can post it
cauchyguy
19.03.2006 03:43
Please post it, bluesea
Bluesea
30.04.2006 17:44
sorry for delay:We assume that p is suffciently large. Since f(r; s) = f(br; bs) for any b not divisible by p, we may assume r = 1 and simply write f(s) instead of f(r; s). Also notice that f(s) = p-1-f(-s), so we may assume $1\leq\ s\leq\ \frac{p-1}{2}$. Moreover, s = 1 is forbidden, f(2) = (p-1)/2 or (p-3)/2, and one easily checks that f(3) = [2(p-1)/3]. So we may assume s>=4. Let g1(s) be the number of ${a \in \{1;2...\frac{p-1}{2}}$ such that {as/p} < 1/2; and let g2(s) be the number of ${a \in \{\frac{(p + 1)}{2};...; p-1}$ such that {as}{p}> 1/2. Note that {as/p} + {(p-a)s/p}= 1: Thus g1(s) = g2(s) = f(s)/2. We consider two cases. (a) s\in [4;p/4]. Note that $|f(s)-\frac{p-1}{2}|=|g_1(s)-(\frac{p-1}{2}-g_1(s)|\leq\ \frac{s}{2}+\frac{p}{2s}$ To see this, divide s;2s;...;(p-1)s/2 into groups depending on which of the intervals (0; p); (p; 2p); : : : they fall into. In each group except the last one, at most one more number falls into one half of the interval than into the other half. Since the largest of these numbers is less than sp/2, the number of such groups is at most s=2. In the last group, the maximum discrepancy is the greatest quantity of the numbers that fit into one half of the interval, which is at most p/2s. For s\in [4; p/4], the right side of the above inequality achieves its maximum value at the endpoints of the interval. Thus we get the upper bound |f(r;s)-(p-1)/2|<2+p/8 and the right side is less than (p-1)/6 for p sufficiently large. (b) s\in [(p-1)/4; (p-1)/2]. In this case, there cannot exist three consecutive values of a\in {1;...; (p-1)/2} or three consecutive values of a\in {(p + 1)/2;.... ; p-1} such that the three values of {as/p}all lie in a single interval of length 1/2. For 6|p-1 this implies [{p-1/3}]<= f(s)<= [{2(p-1)/3]; for 6|p-5, the lower bound is true. To violate the upper bound, f(s)>= 4k + 3 where p = 6k + 5. Since f(s) = 2g2(s), g2(s)>=2k + 2. But we can regroup 3k + 2 numbers {1; 2;....; (p-1)/2} as {(1; 2); (3; 4; 5);....; (3k; 3k + 1; 3k + 2)}} k+1 groups From the earlier observation, each group can provide at most two a's such that {as/p} <1/2. Hence {s/p}; {2s/p} < 1/2. Since 1<=s <=(p-1)/2; {2s/p} = 2{s/p}. But then s=p-1/4 and 4s < p. Now p > 4s > p-1, which is impossible for integers s and p.
bilarev
23.10.2007 22:51
Here http://www.mathlinks.ro/Forum/viewtopic.php?t=171037 hjbrasch proves stronger claim.
Pathological
12.04.2019 03:39
Essentially just turns into casework upon observing that you can set $r = 1$, which is easy to justify.
First of all, observe that the lower bound implies the upper bound since the two sides add to $p-1$ and so we can just use the lower bound for $(r, -s)$ to imply the upper bound. So let's show the lower bound. By scaling, we can clearly assume that $r = 1$. Furthermore, by the previous logic, we can let $s < \frac{p}{2}$. From now on we'll write $a = \frac{p-1}{2}$ for convenience.Let $n \in \{1, 2, \cdots, p-1\}$ be called $(r,s)-\mathbf{good}$ if $\{ \frac{rn}{p}\}, \{ \frac{sn}{p}\}$ are on the same side of $\frac12$ and $(r, s)-\mathbf{bad}$ else. Then, observe that $n$ is $(r, s) -good$ iff $p-n$ is, and so it suffices to show that at least $\frac13$ of $\{1, 2, \cdots, \frac{p-1}{2}\}$ are $(r, s)-good, bad$ respectively. Consider the intervals $[0, \frac{p}{2}], [\frac{p}{2}, p], \cdots, [\frac{p(s-1)}{2}, \frac{ps}{2}].$ Let $n_0, n_1, \cdots, n_{s-1}$ be the number of $s, 2s, \cdots, as$ in each of the $s$ intervals from before. We wish to show that the sum of the odd-indexed $n_i$'s is at most twice that of the even-indexed ones.We will consider a few cases on $s$. If $s$ is small ($\{1, 2, 3\}$), then it's very easy to check. Otherwise let's suppose that $3 < s \le a.$ If $3 < s \le \frac{a}{2}$, then all of the $n_i$'s are either $x$ or $x+1$, for some $x \ge 2$. Since $s > 4$ the sum of the even-indexed $n_i$'s is at least $\frac{s-1}{2} \cdot x$ and the sum of the odd-indexed $n_i$'s is at most $\frac{s+1}{2} \cdot (x+1)$. This finishes unless $\frac{s+1}{s-1} > \frac{4}{3}$, i.e. $s<7.$ These cases can again be easily checked. Finally, let's suppose that $\frac{a}{2} < s \le a.$ Then, all the $n_i$'s are either $1$ or $2$. Thus, in the "worst case", all the even-indexed $n_i$'s are $1$ and the odd-numbered ones are $2$. If $s$ is even, this this finishes perfectly. Otherwise, we have that $n_0, n_{s-1}$ must both be $1$ clearly, and so we're still done since they sum up to at most $2$.
$\square$
China_BW
01.06.2023 14:42
Pascual2005 wrote: a clue: you can assume $r=1$ mod p. It's just the easiest and the first step in this problem...