1
$\begingroup$

NOTE: Looking for a hint,not the whole solution.

BdMO 2012 Nationals Secondary

Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always be a right triangle with vertices among these $2n-1$ points.

If we are trying to get a right triangle,we need a point which has one more point in the row that it is in and one more point in the column that it is in.Now,we have to prove that it is impossible to pick $2n-1$ points from $n\times n$ grid without having a point that satisfies the above property.I think we can somehow use the Pigeonhole Principle to prove that.

If we pick $n$ points from the same row/column,then picking one more point would result in a right triangle.If we pick only one point from each column and row(resulting in $n$ chosen points),then picking one more point would give us a right triangle.

I of course did not mention all possible cases in the last paragraph,and quite frankly,I am not sure if listing out the cases would help here.A nudge in the correct direction will be appreciated.

EDIT: I also tried induction but with no luck.

$\endgroup$
2
$\begingroup$

Here is a hint: try picking a pair of points in the same horizontal line.

Note that $2n-2$ points can be arranged without a triangle by filling the left column and the bottom row, but missing the corner.

Further hint: When you have two points in the same horizontal line, which must exist when $2n-1\gt n$ i.e. $n\gt 1$ - and no right-angled triangle - there can be no other points in the two columns containing those points. You can delete the two columns, taking out two points, and leaving a rectangular arrangement with no right-angled triangle. Can you see how to use a similar argument in the rectangle, which would recover a smaller square arrangement?

$\endgroup$
  • $\begingroup$ Okay,I tried the problem for a while but didn't make any improvements.Could you please give one further hint? $\endgroup$ – rah4927 Feb 12 '14 at 4:34
  • $\begingroup$ @rah4927 I've added another hint. $\endgroup$ – Mark Bennet Feb 12 '14 at 7:59
  • $\begingroup$ I am interested:can this proof be rephrased as a pigeonholing argument?I think it can,since the proof relies on showing that there are less columns than required. $\endgroup$ – rah4927 Jul 12 '14 at 8:39
  • $\begingroup$ @rah4927 You are right, it is essentially a pigeonhole argument in form. $\endgroup$ – Mark Bennet Jul 12 '14 at 8:44

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.