The nine entries of a $3 \times 3$ grid are filled with the integers -1, 1 and 0. Use the Pigeonhole Principle to prove among the eight resulting sums (three rows , three columns or two diagonals) there will always be two that add to the same number.

Support with the aid of an arrow diagram clearly indicating the elements of the domain and co domain.

Please help!!!!


Try this:

1- Compute all the possible sums of three of the numbers in $\{ 1,-1,0\}$

2- Compare the number of sums with the number of resulting sums

3- Use the Pigeonhole Principle

Like this: All the possible sums of three of the numbers $1,-1,0$ are: $3,2,1,0,-1,-2,-3$. Those are the possible sums that will appear in the eight resulting sums. By the pigeonhole principle, at least 2 of the resulting sums will be equal.

| cite | improve this answer | |
  • 2
    $\begingroup$ Instead of all combinations in step 1, simply find what is the maximal and what is the minimal sum $\endgroup$ – Hagen von Eitzen Aug 8 '13 at 12:22
  • $\begingroup$ Exactly! I will edit. $\endgroup$ – Marra Aug 8 '13 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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