Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Define $P(S)$ as $$\exists a, b \in S (a - b \in S).$$

Prove that for any subset $S$ of $A = \{1, 2, 3, 4, 5\}$, $P(S)$ or $P(A - S)$ holds.

Please prove it using some graph theory.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Assume $\neg P(S)$ and $\neg P(A-S)$. Since $4-2=2$, at most one of 4 and 2 is in $S$ and at most one of them is in $A-S$, hence exactly one is in $S$ and onw is not. By the same argument, exactly one of 1 and 2 is in $S$. By symmetry in $S$ vs. $A-S$, we may assume that $1\in S$, hence $2\notin S$, $4\in S$. Then we conclude $3=4-1\notin S$, $5=4+1\notin S$. But then $2=5-3$ holds in $A-S$.

share|improve this answer
    
It is a clear proof unrelated to graph theory. –  Anthony Sep 8 '12 at 17:13

Your Answer

 
discard

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.