Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a homework problem asking me to prove that it's impossible to construct a set of integers so that the set has certain characteristics. I've showed the following things:

  1. It's impossible to construct a set of integers modulo 100 so that the set has the required characteristics.
  2. Any set of integers with the required characteristics cannot contain two integers which are equivalent modulo 100.

How do I conclude the target assertion from these two facts? I would probably get full credit if I played the "clearly" card, but it isn't really clear (to me). Is there some simple proof by contradiction here which I'm not seeing?

share|cite|improve this question
Too abstract! Please tell us what the question is. And then, What have you showed! This way, we can tell you, how to conclude. – user21436 Feb 14 '12 at 23:48
@KannappanSampath I think that any more detail will just confuse what I'm trying to ask. If you can, just imagine that the detail is left unspecified and you have to give a proof with only the information I gave. That will give me exactly what I need. :) But if you're really curious, the homework question is asking me to prove that it's impossible to construct a set of 52 different integers such that no two of them have a sum or difference divisible by 100. – Brian Gordon Feb 15 '12 at 0:14
up vote 3 down vote accepted

It depends on just what you mean by (1). If you mean that no set whose members are pairwise incongruent modulo $100$ can have the required characteristics, then you’re done: (1) and (2) impose contradictory requirements on a set having the required characteristics. If, on the other hand, you mean that no subset of $\{0,1,\dots,99\}$ has the required properties, then you need to show something like this:

(3) If $S$ is a set of integers with the required properties, $n\in S$, $m\equiv n\pmod{100}$, and you form a new set $S'$ by replacing $n$ by $m$, (i.e., $S'=(S\setminus{m})\cup{m}$), then $S'$ also has the desired properties.

Then you can argue as follows. Suppose that $S$ is a set of integers with the required characteristics. Using (3) repeatedly, replace each member of $S$ by the unique member of $\{0,1,\dots,99\}$ congruent to it. The resulting set set still has the required characteristics, contradicting (1).

share|cite|improve this answer
Thanks, I think the ambiguity in what exactly I mean by "integers modulo 100" is why I was having a hard time being formal about my conclusion. By explicitly choosing one of your options I can see that the proof will come together much more nicely. Thanks! – Brian Gordon Feb 15 '12 at 0:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.