amparvardi wrote: For an integer $n \geq 3$, let $\mathcal M$ be the set $\{(x, y) | x, y \in \mathbb Z, 1 \leq x \leq n, 1 \leq y \leq n\}$ of points in the plane. What is the maximum possible number of points in a subset $S \subseteq \mathcal M$ which does not contain three distinct points being the vertices of a right triangle? Is the question same as , finding number of points sets S such that no 3 points in it form a right triangle?

Post 1: no...you have to find the maximum number $ m $ such that exists a subset $ S $ such that there are no right triangles with the vertexes in $ S $ with $ m $ elements. Post 2: I think the maximum is $ 2n-2 $ but I'm not sure... I have an idea...I'll finish it and if works I'll post it. Post 3: each point can be of $ 3 $ types: 1. his column and his row doesn't have any point in $ S $ say blue. 2. only his column has points in $ S $ say green. 3. only his row has points in $ S $ say red. where the points are in a $ (n-1)X(n-1) $ square. but I don't obtain anything ... some ideas?

It's easy to show that answer is $2n-2$ if we think about generalization $ \{(x, y) | x, y\in\mathbb{Z}, 1\leq x\leq m, 1\leq y\leq n\} $, where answer is $m+n-2$ (except case when $min(m, n)=1$) and use induction.

I got this solution. It's not hard to find a solution with $2n - 2$ points (choose $n-1$ points in the first row and the other $n-1$ points in the column that has no points in the first row). Now suppose we have at least $2n-1$ points and let $a_1\geq a_2\geq \ldots\geq a_n$ be the number of points in the rows. If $a_1 = n$ then a right angle surely appears: if suffices to choose one of the remaining $n-1$ points and two of the points from the complete row. So we can suppose $a_1 \leq n-1$. Let $k$ be the number of $a_i$'s greater than one. Then $n-k$ $a_i$'s are equal to one and $a_1 + a_2 + \cdots + a_k = 2n-1-(n-k) = n + k - 1$. Since $a_1 \leq n$, we cannot have $k = 1$, so $k \geq 2$. But this means that $a_1 + a_2 + \cdots + a_k > n$, so two of the rows overlap and we have a right-angled triangle, and we are done.

2n-2 Construction: n-1 points in intersection of first row and every column except first, another n-1 points in intersection of first column and every row except first. Proof that 2n-2 is maximum number of points by induction: Base: n=3 Suppose that we have 5 points. By dirichlet 2 must be in same row. 2 columns in which these points are are forbidden now, so all 3 another points must be in third row, what gives us right triangle. Suppose that for every i >=3 and i=<n-1 maximum number of points is 2i-2. Induction step: Suppose that for n we can have 2n-1 points. By dirichlet, 2 points must be in same row. 2 columns in which these points are are forbidden now. We have now 2n-3 points and n-2 columns. By dirichlet 2 points have to be in same column, but none of these new points can be in same row with previous ones. In that way we occupied 2 rows and 2 columns, or 2n +2n -4 spots. We have now remaining n²-4n+4 or (n-2)² spots, and 2n-5 points left to mark. We supposed that for n-2 max number of points is 2(n-2)-2 or 2n-6, but we must mark another 2n-5 points, so contradiction.