I have got this task at high school contest-math seminar. The theme is graph theory.
Let us have $mn$ board, $m \geq n$. The board is empty from the start. You can tick a chosen square if there are three empty squares that stand in vertices of a rectangle with the one you chose, i.e there are only two distinct x-coordinates and only two distinct y-coordinates in the set of coordinates of four squares.
What is the maximal number of ticks for given $ (m,n)$. Is it true that no matter how you go, you will place ✓in $ (n-1)(m-1)$ squares.
I see that the answer is less that $mn-(m)$ because there is at least one unticked square at each row.
I tried to use Turan theorem and some modified Hall lemma.
The squares can be treated as vertices, and the equal coordinate can be treated as an edge. But this leads to many cliques. You can treat each rectangle as a vertex and then you have an edge between rectangles if they share a square.
This cases didn't lead to some good construction alas.
Update #1: the task was different although equal: let us have a board with some squares ticked. We can put a new tick if the new tick forms a new ticked rectangle with other three ticks. What is the minimal number of ticks needed so we could tick the whole board. I feel that those tasks are equal, because the uncolored squares from the first task are coloured ones in the second.
Update #2: I treat rows as vertices of one part and edges as vertices of another. The rectangle means 4-cycle.
So we have a bipartite graph and we can colour an edge if a coloured 4-cycle that has this edge occurs. What is the minimal number of uncolored edges we should have?
I don't know how to eliminate the case when the newly colored edge lets colour the edge that couldn't be coloured before
Notice, that if you have a bipartite graph with no 4-cycles then your graph is a tree. The task now reformulates: lets have a bipartite graph, you can add an edge if a cycle appears. This operation preserves the amount of connectivity components. So we have a tree connecting all the vertices. Hence the answer is $m+n-1 = E-1$.
That means that there is really no difference in which order I tick the squares in the second task situation.