Let $ p\geq 5$ be a prime number.Prove that for any partition of the set $ P=\{1,2,3,...,p-1\}$ in $ 3$ subsets there exists numbers $ x,y,z$ each belonging to a distinct subset,such that $ x+y\equiv z (mod p)$
Problem
Source: Romania TST 1993
Tags: search, number theory unsolved, number theory
05.08.2009 22:41
What a nice problem! Anybody replied, so I'll post my attempt. Let $ P$ be partitioned by the sets $ A$, $ B$ and $ C$. Suppose for now that $ A$ has only one element, and call it $ a$. Set $ B$ has the $ n$ elements $ b_1,b_2,...,b_n$ and $ p-a$ is not in $ B$ (for if it was we could work with set $ C$ instead). Consider the sums $ a+b_i$ modulo $ p$. None of these sums equals zero or $ a$, so if one of them was not in $ B$ we'd be done. Suppose that all the sums are in $ B$, that is, sor all $ b_i$ we have $ a+b_i\equiv{b_j} (mod p)$ for some $ b_j$. Note that the $ b_j$'s are all distinct. Adding up all the $ b_i$'s we get $ na\equiv{0} (mod p)$. As $ p$ is a prime it must divide either $ a$ or $ n$, wich is an absurd. So we are done for this special case. Consider now that all the sets $ A$, $ B$ and $ C$ have more than one element. Using a similar reasoning we find that for each $ a_i$ there must be a $ b_i$ or a $ c_i$ such that $ a_i+b_i$ is nonzero and is not in $ B$ (or $ a_i+c_i$ is nonzero and is not in $ C$). If one of these $ a_i+b_i$ sums were not in $ A$ we'd be done. Assuming that all these sums actually are in $ A$ we must achieve a contradiction. Unfortunately I couldn't make it work. Can someone help me?
14.08.2009 09:06
It was posted before here http://www.mathlinks.ro/viewtopic.php?search_id=1712261343&t=74320 but recieved no solution. on the other hand here http://www.mathlinks.ro/viewtopic.php?search_id=1712261343&t=87906 you can find two solutions.