Let $ p$ be a prime number and let $ 0\leq a_{1}< a_{2}<\cdots < a_{m}< p$ and $ 0\leq b_{1}< b_{2}<\cdots < b_{n}< p$ be arbitrary integers. Let $ k$ be the number of distinct residues modulo $ p$ that $ a_{i}+b_{j}$ give when $ i$ runs from 1 to $ m$, and $ j$ from 1 to $ n$. Prove that a) if $ m+n > p$ then $ k = p$; b) if $ m+n\leq p$ then $ k\geq m+n-1$.
Problem
Source: Bulgarian Math Olympiad MO 2004, problem 6
Tags: induction, number theory unsolved, number theory
pete_ross
18.05.2004 01:22
a) Let 0<=k<p Let B={b_1,...,b_n} Suppose that contrary is true. if a_1>k then distinct numbers p+k-a_1,p+k-a_2,...,p+k-a_m are not in B therefore n=|B|<=p-m contradiction if a_m<=k then distinct numbers k-a_1,...,k-a_m are not in B therefore n=|B|<=p-m contradiction if a_1<=k<a_m let a_t<=k<a_{t+1} then distinct numbers k-a_1,...,k-a_t,p+k-a_{t+1},...,p+k-a_m are not in B therefore n=|B|<=p-m contradiction
Charlydif
18.05.2004 06:23
This is know as Cauchy-Davenport Inequality.....
Sung-yoon Kim
28.06.2004 12:17
There is simple solution of the first problem. It's the neccesary-sufficient condition that for every integer i, (0<=i<p) there must be two numbers a_j and b_k, (1<=j,k<=p) so that a_j + b_k is divisible by p. Now consider the pairs : (0,i) (1,i-1) (2,i-2) ... (i-1,1) (i,0) (i+1,p-1) ... (p-1,i+1) In the each pair, the first number can be a_1,a_2,...,a_p, the second number can be b_1,b_2,...,b_p. There are 2p numbers, and we take more than p numbers. So by Pigeon's hole principle, there must be a pair that all of two numbers is chosen. Therefore there exists a pair (a_j,b_k) such that a_j+b_k = i(mod p). And the proof ends here. Isn't there anyone who proved the second problem? I have tried to prove it but it seems very difficult. Please post the solution of the second problem if solved.
tom11784
27.07.2004 21:45
I have a reasoning in my head, but I can't lay out a fully formal proof of it: Let us assume without loss of generality that m<=n. First off we know for (b) that when we use a<sub>1</sub> we get n distinct sums modulo p since none of a<sub>1</sub>+b<sub>1</sub>,a<sub>1</sub>+b<sub>2</sub>,...,a<sub>1</sub>+b<sub>n</sub> are equal. From here we view the modulos contributed by a<sub>2</sub> and note that at least one of these must be different since if they were the same as from a<sub>1</sub> it would mean that b<sub>1</sub>, b<sub>2</sub>,...,b<sub>n</sub> were equally spaced and that a<sub>2</sub>+b<sub>n</sub> = a<sub>1</sub>+b<sub>j</sub> for some j, which is a contradiction since p is prime and n<p. Now if a<sub>2</sub> contributes only 1 new modulo it can be shown that a<sub>3</sub> contributes at least 1 new modulo, and so on producing at least 1 new modulo for a<sub>2,3,...,m</sub> which when added to the n from a<sub>1</sub> gives at least m+n-1. The problem I arrive at proving is when for example a<sub>2</sub> provides 2 new modulos there is no longer a requirement for a<sub>3</sub> to make a contribution, but if it fails to then a<sub>4</sub> must and so on, and similar requirements if a<sub>2</sub> contributes 3,4,...,m-2 new modulos. I hope this helps someone "get their light-bulb shining". -Tom
ali
22.03.2005 21:20
when you think on something a lot you get to prove the problem in many ways and all of them have a hole! I hope this one doesn't have that. O.k, here is how it goes. part a) was proved by at least 3-4 people here. part b) I will use induction on min(m,n). The hypothesis is trivial for min(m,n)=1,2. the proof for min(m,n)=2 appears in the last post by Tom. Now suppose that the statement is true for min(m,n)<=k. I shall prove it for min(m,n)=k+1. Towards this goal, let us consider an arbitrary set a1,...,am and b1,...,bn suppose that the set of common elements of A and B is denoted by x1,...,xt where we shall assume here that 1<=t<min(m,n) wlog assume that m>=n. then the span of ai+bj is the bigger than the span of the two new sets: B' and A'. where B'={x1,...,xt} and A'= A :cup: (B-B') note that in the new case min(m,n) is decreased by at least one, since 0<t<n. So by our assumption the total number of elements is t+(m+n-t) -1 =m+n-1. Now the only scenario's we need to take care of, are cases with t=0, min(m,n) for case 1: just subtract (a1-b1) from all elements of set A. the new sets A', B have the same number of elements in A' + B as before , and now clearly A' and B have at least one common element b1. Finally, let us consider the case t=min(m,n). In this case B is a subset of A. we would be done if we could find some number x, such that A={ai-x}(1=<i<=m) and B have t common elements with n>t>0. To prove this I shall assume on contrary that for every x=ai-bj, the set B is a subset of A'={ai-x}. Let the set of all possible values of x be denoted by X. wlog, assume that b1=0. then A is a subset of X. and therefore since B is a subset of {ai-x} we have that for every ai, ai+bj belongs to A. and therefore the span of A+B is exactly m, but thanks to the proof by Tom in the last post, this is impossible, unless n=1, which is the base of induction. -Ali
georgew_bush
03.12.2005 12:12
I could not understand any solution of yours.Maybe yours all have something not correct.
ali
04.12.2005 06:02
I don't think so. The question is can you find any error?