I heard this problem was very easy! Many students submitted full solutions!

I heard only 10 people got a 6 or 7 on this problem.

I'll let someone upload the intended solution. Instead, here is the ugliest solution you've ever witnessed. First partition the points into sets with the same x coordinate in increasing value. Now we construct 6 different classes of rectangles. Let $y_j$ denote heights in each column, and let $x_0 = y_0 = 0$ and $x_{a+1} = y_{a_i+1} = 1$ for simplicity, where $a_i$ is the number of points in the $i$th column, $a$ is the number of columns, and $y$ values corresponds to the correct column, which is up to the reader to intuit: Class A: Rectangle bounded by $x = x_{i-1}, x = x_{i+1}, y = y_j, y = y_{j+1}$ for $1 \leq j \leq a_i - 1$. Class B: If a column has at least three vertical points, draw rectangles bounded by $x = x_{i-1}, x = x_i, y = 0, y = 1$ and $x = x_i, x = x_{i+1}, y = 0, y = 1$. Class C: Draw rectangles over the top of the sets such that adjacent rectangles merge. Adjacent rectangles merge if and only if max(i) = max(i+1), where max(i) denotes the largest y coordinate in column i. for $0 \leq i \leq a$. Class D: Draw rectangles under the bottoms of the sets such that adjacent rectangles merge. Adjacent rectangles merge if and only if min(i) = min(i+1), where min(i) denotes the smallest y coordinate in column i. for $0 \leq i \leq a$. Class E: Draw a rectangle between every pair of adjacent columns such that the i and i+1 columns both have size at most 2 and whose sets of points have nonzero intersection. Class F: Draw a rectangle bounded by $x = 0, x = x_1, y = 0, y = 1$, and one bounded by $x = x_a, x = 1, y = 0, y = 1$. Notice that if a class E rectangle is drawn such that not both sets are size 2 then it implies one of the conditions max(i) = max(i+1) or min(i) = min(i+1) due to size. It is left to the reader to verify that this construction creates at most $2n+2$ rectangles and always covers points if and only if they are desired. Remark: The set of points $(0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)$ requires exactly $12$ rectangles to solve and is sharp. Make sure to check any inductive solutions against this case!

I think the title of this thread deserves an explanation :’) After painfully grading every single one of the 63 TSTST submissions, I can say with certainty that this problem is one of the most difficult problem 1s to ever appear in the history of contest mathematics. With a grand total of only 8 correct solutions, many of which were long, intricate, and casework-heavy, this problem received fewer solves than all but one of the problems on the 2018 TSTST. I think this is probably the closest we will ever get to what would realistically happen if you gave a bunch of students a 3/6 level problem, told them it was 1/4-difficulty, and asked them to solve it. I came up with this problem last March during one of my topology lectures, where we were discussing countable bases for the standard topology over $\mathbb{R}^2$. Since removing a finite number of points from $\mathbb{R}^2$ leaves an open set, it was natural to ask what the minimal number of rectangles needed to cover the set might be. The lower bound construction was not too difficult to come up with, and for the upper bound I partitioned the points by $x$-coordinate and drew rectangles covering each strip. A day later, however, I realized my construction was incorrect; in particular, it failed when two points with adjacent $x$-coordinates share a $y$-coordinate. I quickly found a patch for the solution and submitted it to the TSTST as a 10 MOHS, 1/4-difficulty problem. Fast-forward to the first day of TSTST. After proctoring the exam, I walked to the dining hall for dinner, where I found a group of students demanding to know problem 1’s author (I told them to come to test review to find out). One student, unaware of who the problem authors were, personally came up to me while I was in line and said “I HATE problem 1” and left. While eating, many students realized they fakesolved the problem and felt demoralized after getting swept. Only then did I begin to surmise the true difficulty of the problem. At test review that evening, I presented the solution to problem 1, and after my presentation I was met with intense booing instead of a round of applause. After problems 2 and 3 were presented, I went up to reveal problem authors. I wrote on the board: “Problem 1: Y____ T____” and the students started shouting names: “yang!” “yannick!” “you!”. I turned around, quickly wrote “Yours Truly <3”, and ran out of the room. Back in the dorm, I was greeted by a giant mob of students who demanded that I be held responsible for TSTST day 1. I quickly ran into the grading room, which was a temporary safe haven, but the mob was camping outside of the door. My Discord messages were also spammed with "Mr. Turtle, Mr. Turtle, come out of your shell!" An angry grader told them to disperse, and they decided to move onto their next task… filling up water balloons. I spent the remainder of that evening grading the writeups of the high school seniors (who were taking TSTST just for practice). After spending over three hours grading those four papers, I realized that grading would be no easy task. When I finished I went back to the lounge, where I discovered that the students left behind some… ammunition. I took the water balloons they left behind and filled a few up in my room that night. The next day, I walked around the entire day in my rain poncho and my umbrella, which must have looked ridiculous since it was 90 degrees outside and sunny. At lunch, I was greeted by the same mob of students, who thankfully did not have their water balloons ready. However, it seemed that they wanted me to take a test called the “ELMO Revenge”, a test originally designed to get revenge on the ELMO organizers. (They thought ELMO P4 was a funny joke, and then they were hit with TSTST P1.) I spent much of the afternoon filling water balloons so I could retaliate in self-defense, if necessary. Some students who felt bad for me (or didn’t buy into the mob mentality) also helped me fill up some balloons, so I had a giant trash bag filled with water balloons. At 7:30 that night, I camped out in the backyard of the dorm with my umbrella and rain poncho, waiting for the mob to attack. Finally at 8pm, I was rained on with a torrent of water balloons and water guns. Needless to say, I was thoroughly splashed. That night, I asked Evan how such low marks on this problem could possibly happen. Evan, too, was equally concerned. The TSTST reviewers had rated this as the easiest problem out of the nine that were to appear on the contest (at a 1.25 difficulty level), but clearly the results say otherwise. Upon closer inspection, however, it appeared that the reviewers were… slightly misguided. One wrote “solved in my head in a few minutes,” and another wrote “good easy problem. For the lower bound, put $n$ points in the diagonal, and for the upper bound, use $n+1$ vertical rectangles and $n+1$ horizontal rectangles…” It was clear what had happened. The reviewers fakesolved the problem too, gave it an easy rating, and the test organizers used the ratings to determine the test. The fact I rated it as a 1/4-difficulty problem did not help either. As problem 1 captain, I was obligated to find graders to help grade the problem, yet it became quickly apparent that no one else wanted to grade this problem. Unlike the submissions for the other problems, it was not immediately clear whether or not a given solution was a solve or not, due to the fat stack of messily-written, long, inductive-hypothesis-patching-type solutions many students spent 4+ hours writing. I was in it, alone. I didn’t want to grade either. But it had to be done. As a result, I stayed up until 2-3am every night to grade, and I also graded while proctoring days 2 and 3 of TSTST, even while accompanying students to the bathroom. If I was to get any revenge for this problem, this would have been the ultimate revenge – hours spent deciding whether or not the student’s five cases or their six types of rectangles actually were truly correct solutions. It took so long that I was still assigned to grade problem 1 when Day 2 rolled around, and for Day 3 I was assigned to grade problem 9 (which had practically no submissions) so I could have more time to finish problem 1. By the sixth day of grading, almost every submission had been double-graded, thanks to our wonderful head grader and another grader who was willing to put himself through misery. By the end of the night, grading for the other eight problems were finished, and I had one ugly solution left to read. Then, a miracle happened: I finished reading the solution. I entered the last score into the spreadsheet. I was free! In the words of Brandon Wang: “Holden dug himself into a very deep hole. And then he dug himself out of it.” I lived through my worst nightmare. Now, it’s time for what you’ve all been waiting for: the solution to one of the most notorious olympiad problems in recent history. Original statement wrote: In terms of $n \in \mathbb{Z}^+$, find the smallest integer $k$ for which $(0, 1)^2 \setminus S$ is a union of $k$ axis-aligned open rectangles for every set $S \subset (0, 1)^2$ of size $n$.

Solution summary: This problem's easiest case is very close to RMM 2017/5, the sieve problem. Ruthlessly force the harder cases to also look like that problem.

The_Turtle wrote: I think the title of this thread deserves an explanation :’) After painfully grading every single one of the 63 TSTST submissions, I can say with certainty that this problem is one of the most difficult problem 1s to ever appear in the history of contest mathematics. With a grand total of only 8 correct solutions, many of which were long, intricate, and casework-heavy, this problem received fewer solves than all but one of the problems on the 2018 TSTST. I think this is probably the closest we will ever get to what would realistically happen if you gave a bunch of students a 3/6 level problem, told them it was 1/4-difficulty, and asked them to solve it. I came up with this problem last March during one of my topology lectures, where we were discussing countable bases for the standard topology over $\mathbb{R}^2$. Since removing a finite number of points from $\mathbb{R}^2$ leaves an open set, it was natural to ask what the minimal number of rectangles needed to cover the set might be. The lower bound construction was not too difficult to come up with, and for the upper bound I partitioned the points by $x$-coordinate and drew rectangles covering each strip. A day later, however, I realized my construction was incorrect; in particular, it failed when two points with adjacent $x$-coordinates share a $y$-coordinate. I quickly found a patch for the solution and submitted it to the TSTST as a 10 MOHS, 1/4-difficulty problem. Fast-forward to the first day of TSTST. After proctoring the exam, I walked to the dining hall for dinner, where I found a group of students demanding to know problem 1’s author (I told them to come to test review to find out). One student, unaware of who the problem authors were, personally came up to me while I was in line and said “I HATE problem 1” and left. While eating, many students realized they fakesolved the problem and felt demoralized after getting swept. Only then did I begin to surmise the true difficulty of the problem. At test review that evening, I presented the solution to problem 1, and after my presentation I was met with intense booing instead of a round of applause. After problems 2 and 3 were presented, I went up to reveal problem authors. I wrote on the board: “Problem 1: Y____ T____” and the students started shouting names: “yang!” “yannick!” “you!”. I turned around, quickly wrote “Yours Truly <3”, and ran out of the room. Back in the dorm, I was greeted by a giant mob of students who demanded that I be held responsible for TSTST day 1. I quickly ran into the grading room, which was a temporary safe haven, but the mob was camping outside of the door. An angry grader told them to disperse, and they decided to move onto their next task… filling up water balloons. I spent the remainder of that evening grading the writeups of the high school seniors (who were taking TSTST just for practice). After spending over three hours grading those four papers, I realized that grading would be no easy task. When I finished I went back to the lounge, where I discovered that the students left behind some… ammunition. I took the water balloons they left behind and filled a few up in my room that night. The next day, I walked around the entire day in my rain poncho and my umbrella, which must have looked ridiculous since it was 90 degrees outside and sunny. At lunch, I was greeted by the same mob of students, who thankfully did not have their water balloons ready. However, it seemed that they wanted me to take a test called the “ELMO Revenge”, a test originally designed to get revenge on the ELMO organizers. (They thought ELMO P4 was a funny joke, and then they were hit with TSTST P1.) I spent much of the afternoon filling water balloons so I could retaliate in self-defense, if necessary. Some students who felt bad for me (or didn’t buy into the mob mentality) also helped me fill up some balloons, so I had a giant trash bag filled with water balloons. At 7:30 that night, I camped out in the backyard of the dorm with my umbrella and rain poncho, waiting for the mob to attack. Finally at 8pm, I was rained on with a torrent of water balloons and water guns. Needless to say, I was thoroughly splashed. That night, I asked Evan how such low marks on this problem could possibly happen. Evan, too, was equally concerned. The TSTST reviewers had rated this as the easiest problem out of the nine that were to appear on the contest (at a 1.25 difficulty level), but clearly the results say otherwise. Upon closer inspection, however, it appeared that the reviewers were… slightly misguided. One wrote “solved in my head in a few minutes,” and another wrote “good easy problem. For the lower bound, put $n$ points in the diagonal, and for the upper bound, use $n+1$ vertical rectangles and $n+1$ horizontal rectangles…” It was clear what had happened. The reviewers fakesolved the problem too, gave it an easy rating, and the test organizers used the ratings to determine the test. The fact I rated it as a 1/4-difficulty problem did not help either. As problem 1 captain, I was obligated to find graders to help grade the problem, yet it became quickly apparent that no one else wanted to grade this problem. Unlike the submissions for the other problems, it was not immediately clear whether or not a given solution was a solve or not, due to the fat stack of messily-written, long, inductive-hypothesis-patching-type solutions many students spent 4+ hours writing. I was in it, alone. I didn’t want to grade either. But it had to be done. As a result, I stayed up until 2-3am every night to grade, and I also graded while proctoring days 2 and 3 of TSTST, even while accompanying students to the bathroom. If I was to get any revenge for this problem, this would have been the ultimate revenge – hours spent deciding whether or not the student’s five cases or their six types of rectangles actually were truly correct solutions. It took so long that I was still assigned to grade problem 1 when Day 2 rolled around, and for Day 3 I was assigned to grade problem 9 (which had practically no submissions) so I could have more time to finish problem 1. By the sixth day of grading, almost every submission had been double-graded, thanks to our wonderful head grader and another grader who was willing to put himself through misery. By the end of the night, grading for the other eight problems were finished, and I had one ugly solution left to read. Then, a miracle happened: I finished reading the solution. I entered the last score into the spreadsheet. I was free! In the words of Brandon Wang: “Holden dug himself into a very deep hole. And then he dug himself out of it.” I lived through my worst nightmare. Now, it’s time for what you’ve all been waiting for: the solution to one of the most notorious olympiad problems in recent history. Original statement wrote: In terms of $n \in \mathbb{Z}^+$, find the smallest integer $k$ for which $(0, 1)^2 \setminus S$ is a union of $k$ axis-aligned open rectangles for every set $S \subset (0, 1)^2$ of size $n$.

L+Ratio+Didn't Ask+Bozo(This is a joke please take it lightly and I also took the TSTST)

The_Turtle wrote: I spent the remainder of that evening grading the writeups of the high school seniors (who were taking TSTST just for practice). After spending over three hours grading those four papers, I realized that grading would be no easy task. Inconsistent wrote: I'll let someone upload the intended solution. Instead, here is the ugliest solution you've ever witnessed. Here is the sketch of a solution which probably contends the aforementioned, quoted solution for the award of 'ugliest.' In fact, most of the three hours mentioned in The_Turtle's quote were spent parsing and understanding the original submission which contained it. Sketch: The bound is the same as everyone else's, so we will only cover the construction. Replace the large square with a rectangle, which does not affect the problem. Proceed by induction. The inductive hypothesis is as follows. There exists a construction satisfying the following conditions: (1) The initial problem conditions are satisfied, (2) If $P$ is the lowest point in $S$, then there exists a rectangle $R$ whose bottom edge coincides with the bottom edge of the large rectangle, and whose top edge coincides with the horizontal line $\ell$ through $P$, (3) There exists a set of disjoint rectangles $R_1, R_2, \ldots, R_k$ such that $R_i$ and $R_{i+1}$ share a vertical edge and such that $R$ is 'strictly' covered by the union of the $R_i$ (i.e. even the boundary of $R$ is in this union) and (4) There are at most $2n+2$ rectangles used, but if $|S \cap \ell| \geq 3$, then there are at most $2n+1$ rectangles. Now, the proof of this claim. The base cases are 'easy' to verify. Next we split into five (sub)cases, all of which are not difficult: (i) $|S \cap \ell| = k \geq 3$ (ii) $|S \cap \ell| = 2$ (iii) $S \cap \ell = P$ has cardinality $1$: there are the following three possibilities. Let $\ell_2$ denote the second lowest horizontal line containing points in $S$. Then: (iii.a) The point $Q \in \ell_2$ directly above $P$ vertically is not in $S$ (iii.b) $Q \in S$ but $|\ell_2 \cap S| \geq 3$ (iii.c) $Q \in S$ but $|\ell_2 \cap S| \leq 2$ It turns out that each of these cases may be resolved by extending, deleting, and adding only a few rectangles. And so the solution is over (after all conditions of the hypothesis and all cases are checked). A few remarks are in store. First, I think the idea of using induction is natural on this type of integer-based problem with a linear answer. When one attempts this approach, though, it turns to be incredibly easy to fakesolve. And hence this absurd-looking hypothesis was born — I actually fakesolved the problem a couple times, and each time realized that some certain condition would help. Essentially then, the number of issues eventually dwindled until the solution worked (granted, surprisingly). Second, this type of 'induction-bash' turns out to be commonly useful. Sometimes, wishfully trying to expand your hypothesis is useful. In addition, even if the direct induction does not solve the problem, it may allow you to assume certain conditions (i.e., if induction works in some cases, you may assume you are not in any of these cases). So at any rate, one obtains some potentially useful information, which may be further pushed to resolve the problem.

Not bad for a TST Q1. I didn't take the test that year, but here's my sol: Let the $n$ points be $(x_1,y_1)$, $(x_2,y_2)$, $\ldots$, $(x_n,y_n)$ on the cartesian plane. Define a sequence of coordinates $p$ to be $p_i = (x_i,y_i)$. Sequence $X$ is a rearrangement of the x coords from smallest to largest, and sequence $Y$ is a rearrangement of the y coords from smallest to largest. Let R(a,b,c,d) denote the rectangle with edges $x=a$, $x=b$, $y=c$, and $y=d$. Let $R(0,1,0,1)$ be the unit square the points in S are constrained in. Claim 1) It is always possible to construct $2n+2$ rectangles that satisfy the given conditions pf) Construct $R(0,X_1,0,1)$, $R(X_1,X_2,0,1)$, $R(X_2,X_3,0,1)$, $\ldots$, $R(X_{n-1},X_n,0,1)$ and $R(0,1,0,Y_1)$, $R(0,1,Y_1,Y_2)$, $\ldots$, $R(0,1,Y_{n-1},Y_n)$. We can easily see that these $2n+2$ rectangles satisfy the given conditions. Claim 2) $2n+2$ is the minimum value for $k$ pf) In order to prove this, we first prove Claim 2.1 Claim 2.1) Let a point be adjacent to a rectangle if it is on one of the edges of the rectangle. Let $deg(P)$ denote the number of rectangles adjacent to point P. For all $i$, $deg(p_i) \geq 4$. pf) Let $\epsilon$ be an infinitesimally small number. For some $p_i$, $(x_i+\epsilon,y_i)$ must be in the interior of some rectangle. Therefore, there must be a rectangle to the right of $p_i$ that is adjacent to it. By using the same logic, there must be at least four rectangles on the bottom, top, right, and left of $p_i$ that are adjacent to $p_i$. Therefore, $deg(p_i) \geq 4$ Arrange the n points such that $p_i = (\frac{i}{n+1},\frac{i}{n+1})$. We can easily see that one rectangle can be adjacent to at most two points at once. Furthermore, the leftmost rectangle, rightmost rectangle, highest rectangle, and lowest rectangle can only be adjacent to 1 point. Call $A$ the number of pairs of points and rectangles such that the point is adjacent to the rectangle. By claim 2.1 we can see that $4n \leq A \leq 2k-4$. Therefore, $k \geq 2n+2$ Comment: Is there something wrong with my sol? The above posts seem to imply that the intended sol for this question is extremely casework-heavy.

Bound: Same as everyone else's Construction: (Please correct me if I fakesolved this, I have a feeling it is a fakesolve). Draw lines parallel to each of the square's sides, through each of the $n$ points (these are not necessarily pairwise distinct). However, we have at most $2n$ lines, meaning that the number of vertical strips and horizontal strips is at most $2n+2$. Let these strips be the (at most) $2n+2$ rectangles, and we are done (?)

NoctNight wrote: Bound: Same as everyone else's Construction: (Please correct me if I fakesolved this, I have a feeling it is a fakesolve). Draw lines parallel to each of the square's sides, through each of the $n$ points (these are not necessarily pairwise distinct). However, we have at most $2n$ lines, meaning that the number of vertical strips and horizontal strips is at most $2n+2$. Let these strips be the (at most) $2n+2$ rectangles, and we are done (?) What happens if $3$ points are collinear (there exists a line passing through them parallel to one of the sides of the square)? Then no rectangle exists between these points.

S.Das93 wrote: NoctNight wrote: Bound: Same as everyone else's Construction: (Please correct me if I fakesolved this, I have a feeling it is a fakesolve). Draw lines parallel to each of the square's sides, through each of the $n$ points (these are not necessarily pairwise distinct). However, we have at most $2n$ lines, meaning that the number of vertical strips and horizontal strips is at most $2n+2$. Let these strips be the (at most) $2n+2$ rectangles, and we are done (?) What happens if $3$ points are collinear (there exists a line passing through them parallel to one of the sides of the square)? Then no rectangle exists between these points. oh but between the three collinear points (assume WLOG horizontally collinear) there will be vertical strips that are rectangles between them right?

yes but there wont be horizontal rectangles

S.Das93 wrote: yes but there wont be horizontal rectangles what about the horizontal strip rectangles?

they wont exist because points are collinear

bhan2025 wrote: Not bad for a TST Q1. I didn't take the test that year, but here's my sol: Let the $n$ points be $(x_1,y_1)$, $(x_2,y_2)$, $\ldots$, $(x_n,y_n)$ on the cartesian plane. Define a sequence of coordinates $p$ to be $p_i = (x_i,y_i)$. Sequence $X$ is a rearrangement of the x coords from smallest to largest, and sequence $Y$ is a rearrangement of the y coords from smallest to largest. Let R(a,b,c,d) denote the rectangle with edges $x=a$, $x=b$, $y=c$, and $y=d$. Let $R(0,1,0,1)$ be the unit square the points in S are constrained in. Claim 1) It is always possible to construct $2n+2$ rectangles that satisfy the given conditions pf) Construct $R(0,X_1,0,1)$, $R(X_1,X_2,0,1)$, $R(X_2,X_3,0,1)$, $\ldots$, $R(X_{n-1},X_n,0,1)$ and $R(0,1,0,Y_1)$, $R(0,1,Y_1,Y_2)$, $\ldots$, $R(0,1,Y_{n-1},Y_n)$. We can easily see that these $2n+2$ rectangles satisfy the given conditions. Claim 2) $2n+2$ is the minimum value for $k$ pf) In order to prove this, we first prove Claim 2.1 Claim 2.1) Let a point be adjacent to a rectangle if it is on one of the edges of the rectangle. Let $deg(P)$ denote the number of rectangles adjacent to point P. For all $i$, $deg(p_i) \geq 4$. pf) Let $\epsilon$ be an infinitesimally small number. For some $p_i$, $(x_i+\epsilon,y_i)$ must be in the interior of some rectangle. Therefore, there must be a rectangle to the right of $p_i$ that is adjacent to it. By using the same logic, there must be at least four rectangles on the bottom, top, right, and left of $p_i$ that are adjacent to $p_i$. Therefore, $deg(p_i) \geq 4$ Arrange the n points such that $p_i = (\frac{i}{n+1},\frac{i}{n+1})$. We can easily see that one rectangle can be adjacent to at most two points at once. Furthermore, the leftmost rectangle, rightmost rectangle, highest rectangle, and lowest rectangle can only be adjacent to 1 point. Call $A$ the number of pairs of points and rectangles such that the point is adjacent to the rectangle. By claim 2.1 we can see that $4n \leq A \leq 2k-4$. Therefore, $k \geq 2n+2$ Comment: Is there something wrong with my sol? The above posts seem to imply that the intended sol for this question is extremely casework-heavy. I think $A=(x=X_i) \cap (y=Y_j)$ & $A \notin S$ isn't in the interior of any rectangle for some $i$ , $j$

Answer: 2k+2 Construction: For any n points, WLOG, their x and y coordinates are all pairwise distinct. WLOG, they lies on a $(n+1)\times(n+1)$ grid. (This makes sense because we only concern their relative position) Then, place (n+1) bars vertically and (n+1) bars horizontally. Lower bound: We pick n points on the diagonal. WLOG, they lies on a $(n+1)\times(n+1)$ grid. So there coordinates are $(1,1), (2,2)\cdots, (n,n)$. We color 2n+2 segments $(0,1)-(1,1)$, $(1,0)-(1,1)$, $\cdots, $ $(i-1,i)-(i,i)$, $(i,i-1)-(i,i)$, $\cdots $ red. Each rectangle can only cover one red segment, thus we need at least 2n+2 rectangles. Maybe a fakesolve, please check.

IS THIS A FAKESOLVE. oh it is

i have covered the evidence quick grab water balloons

fixed with motivation i guess (this question is for the most part killed by small cases, which both let you get an idea of what to do and let you confirm estimates/possible solves) The original grid construction doesn't work, because it leaves all intersections in the grid empty. That means we can't use strips; instead, we need to use "fatter" rectangles to deal with the empty spaces. For convenience, let's let the spacing between vertical lines be $1$. Suppose there are $x_1,\dots,x_m$ points along each vertical line. With \[(x_1+1)+\dots+(x_m+1)\]rectangles centered at all of the vertical lines, we handle most cases. With $2$ extra rectangles this provides $n+m+2$ rectangles. Now we just need to handle the case where there are adjacent vertices with the same $y$-coordinate. Obviously (I read this step, so no it's not obvious, also the same idea in 2020 C5) we can WLOG the number of different $y$-coordinates is at least $m$ (or we can just rotate $90^{\circ}$) hence there are at most $(n-1)-(m-1)=n-m$ pairs which fail. Use up $n-m$ vertical strips to handle these, we used $n+m+2+n-m=2n+2$ rectangles in total. Done. About the WLOGing step, I suppose a more natural way is: \[\text{need lower bound on y-coordinate}\to \text{draw a really "short" grid}\to \text{realize the argument is symmetric}\to \text{done}\]

This problem is so beautiful; shame it has a bad reputation because of its backstory. And I don't think it's too bad—I could see it being 30/35M at most, but not a 3/6 level problem.

The answer is $2n+2$. Adopt the labeling conventions I just described; in particular, draw all the lines $\ell_1, \ell_2, \dots, \ell_r$ and $m_1, m_2, \dots, m_c$ that pass through at least one of the points in $S$ and are parallel to the axis. Bound: Let the points be $(0, 0), (1, 1), (2, 2), \dots, (n-1, n-1)$ (suitably scaled). Then consider all points of the form $(i, i+1)$ and $(i+1, i)$ for $-1 \leq i \leq n-1$. No two of these points (across all $i$) can be part of the same rectangle without the rectangle covering at least one of the points in $S$. Hence, we need at least $2n+2$ rectangles. Construction: We may assume that all the points are uniformly distributed (in other words, they are lattice points on a $(r+1) \times (c+1)$ grid). For any row $i$, suppose that the points of $S$ in row $i$ are $(k_1, i), (k_2, i), \dots, (k_{a_i}, i)$, where there are $a_i$ points in row $i$. Furthermore, between all the rows, suppose that there exist $a$ pairs of points of the form $(j, i)$ and $(j, i+1)$ in $S$. Let $b$ be the analog amount for columns. We construct rectangles with vertices at $(k_j, i+1), (k_j, i-1), (k_{j+1}, i+1)$, and $(k_{j+1}, i-1)$ for each $0 \leq j \leq a-i$, where $k_0=0$ and $k_{a_i+1} = c$. Furthermore, we also construct two rectangles with vertices at $(0, 0), (c, 0), (0, 1), (c, 1)$ and its horizontal reflection about the horizontal axis of symmetry. Observe that: None of these rectangles cover any point in $S$, and These rectangles cover every relevant point and segment except for (open) segments of the form $(j, i)$ and $(j, i+1)$ where both endpoints are in $S$. To resolve the last few open segments, we have the following claim: Claim. Suppose that there are $b$ such pairs of points when we consider the rectangle by columns instead of rows. Then either $n-r \geq a$ or $n - c \geq b$. Proof. Suppose both are not true. Then notice that among the $a$ pairs of points that share a $y$-coordinate, there are at most $a$ columns, so there are in total at most $n-a$ columns, which yields the inequality $c \leq n-a$. Similarly, $r \leq n-b$, so adding the inequalities, $r+c+a+b \leq 2n$. However, the assumption yields $r+c+a+b > 2n$ by adding the two inequalities, which yields a contradiction. $\blacksquare$ In particular, suppose $n - r < a$. Then we may cover each of these $a$ open segments with one rectangle whose sides lie on rows $i$ and $i+1$. In total, we have $$2 + \sum_{i=1}^r (a_i+1) + a = n+a+2+r \leq n+n+2=2n+2$$rectangles by the claim, as needed.

The answer is $2n+2$. WLOG we can assign integer coordinates to all points such that there are no gaps, with the minimum possible $x$ coordinate being $1$ and the minimum possible $y$ coordinate also being $1$. The equality case is attained by selecting the points \[(1,1), (2,2), \dots, (n,n),\]since the $2n+2$ locations \[\{ (1,0.5), (2, 1.5), \dots, (n, n-0.5) \} \bigcup \{ (0.5, 1), (1.5, 2), \dots, (n-0.5, n) \} \bigcup \{ (n+0.5, n+0.5) \}\]must belong in distinct rectangles. To always cover the square with $2n+2$ rectangles: let $a$ be the number of distinct $x$-coordinates across all points, let $b$ be the number of distinct $y$-coordinates across all points, let $c$ be the number of unordered pairs of points which have the same $x$-coordinate and have one-apart $y$-coordinates, and let $d$ be the number of unordered pairs of points which have the same $y$-coordinate and have one-apart $x$-coordinates. Clearly, $a+c \leq n$ and $b + d \leq n$, so \[ a+b+c+d \leq 2n.\]WLOG, assume that $a+d \leq n$. Now we construct: first, draw the rectangles with width $1$ and height $b+1$ on the leftmost and rightmost side of the grid. Now, for all integers $i$ with $1 \leq i \leq a$, draw rectangles whose leftmost edge has $x$-coordinate $i-1$, rightmost edge has $x$-coordinate $i+1$ and whose topmost and bottommost edges contain points or the boundary of the square. In total, we have drawn $2 + n + a$ rectangles so far. The only parts of the square we have not covered are the horizontal segments of length $1$ between two points. There are exactly $d$ of these segments, so we just cover each one up individually and we're done.

For bound consider $n$ points equally spaced along the diagonal, draw lines parallel to both sides from those points, consider the lines directly above and to the right of the points. Clearly we have that each rectangle can only completely cover $1$ of these lines, so we get $2n$ points need and by considering the line down and to the left from the bottom point to cover these sections completely requires another $2$ rectangles so we get $2n+2$ rectangles. Now for the construction. Let the coordinates of the points be $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. WLOG that there are at least as many points with equal $y$ coordinate than with equal $x$ coordinate. Also suppose that $x_1\leq x_2\leq \dots \leq x_n$. If $3$ adjacent points have different $x$ coordinate draw the rectangle from the top to the middle points and the bottom to the middle point and end those rectangles at the point on either side. If $2$ or more adjacent points have the same $x$ coordinate instead split the two rectangles into multiple rectangles each having its top and bottom at either the top or bottom of the square or at one of the adjacent points with the same $x$ coordinate. Thus this construction covers all but the line connecting two adjacent points with equal $y$ coordinate and the very edges, for the edges add two long vertical rectangles. As for every time we have two points with equal $x$ coordinate we reduce the number of rectangles we used by $1$ for every time we have two points with equal $y$ coordinate we can draw a rectangle inbetween them so all areas are covered.

Supposedly solved with MathLuis, but we didn't do any solving together to be honest. Honestly, I don't really think this problem is that monstrous. I'd rate it at 20-25 MOHS at most and I'm supposed to be really bad at combinatorics. The fact that this rectangle is a unit square, barely matters, we solve it for an arbitrary rectangle. We throw the rectangle on the cartesian plane, with the lower-left corner at $(0,0)$. We claim that the answer is $2n+2$ rectangles. Lower Bound : Consider a set of $n$ points inside the rectangle, such that no two points have the same $x$ coordinate or the same $y$ coordinate. Through each point $(a,b)$ marked inside the rectangle, we draw the lines $x=a$ and $y=b$. Now, consider the $2n+2$ line segments highlighted in red, in the following picture. [asy][asy] size(150); pair A = (0.1, 0.9); pair B = (0.2, 0.8); pair C = (0.9, 0.1); draw((0,0)--(0,1)--(1,1)--(1,0)--cycle); pen hh = red+dashed; pen vv = blue+dashed; draw((0.1, 0)--(0.1, 0.8), vv); draw((0.1,0.8)--(0.1,1),hh); draw((0.2, 0)--(0.2, 0.7), vv); draw((0.2, 0.7)--(0.2, 0.8), hh); draw((0.2, 0.8)--(0.2, 1), vv); draw((0.9, 0)--C, hh); draw((0, 0.1)--(0.8,0.1), vv); draw((0.8, 0.1)--(0.9,0.1), hh); draw(C--(1,0.1), hh); draw(C--(0.9,1),vv); draw((0, 0.8)--(0.1, 0.8), vv); draw((0.1, 0.8)--(0.2, 0.8), hh); draw((0.2, 0.8)--(1, 0.8), vv); draw((0, 0.9)--(0.1, 0.9), hh); draw((0.1, 0.9)--(1, 0.9), vv); dot(A, black+8bp); dot(B, black+8bp); dot(C, black+8bp); [/asy][/asy] Note that no rectangle can covered more than one of these segments, without covering one of the marked points in the process. Thus, we require atleast $2n+2$ rectangles, proving the bound. Construction : We show that $2n+2$ rectangles is always sufficient, via induction on the number of points $n$ in $S$. When $n=1$ it is clear that $4$ rectangles suffice. Now, consider a set $S$ of $n$ points. Let the leftmost point have $x$ coordinate $x_m$ and the rightmost point $x_M$. Similarly, let the topmost point have $y$ coordinate $y_M$ and the bottom-most point $y_m$. Consider the rectangle $\mathcal{R}$ formed by the bottom-side of our rectangle, the right-side, $x=x_m$ and $y=x_M$. It is easy to see that there are strictly less than $n$ points inside this rectangle (since there are atleast two points on its boundary). Let its left side and top side together be denoted by $\mathcal{L}$. We proceed in two cases. Case 1 : The point $(x_m,y_M)$ belongs in $S$. If it does, we look at the points $(x_m,y_m)$ and $(x_M,y_M)$. If atleast one of these are not in $S$ we rotate the rectangle by $\frac{\pi}{2}$ such that the new corresponding point for $(x_m,y_M)$ is not in $S$, and proceed as in the next case. Else, there are atleast three points on $\mathcal{L}$. In this case, we perform the following algorithm. Say there are $m$ points on $\mathcal{L}$. Then, we cover the rectangle $\mathcal{R}$ which has $n-m$ points inside it, using $2n-2m+2$ rectangles. Afterwards, we place rectangles as follows, between the $m$ points on $\mathcal{L}$. [asy][asy] size(150); draw((0, 0) -- (0, 5) -- (5, 5) -- (5, 0) -- cycle); draw((1,0)--(1,4)--(5,4)--(5,0)--cycle,dashed); real eps = 0.1; void rect(real l, real r, real b, real t, pen p) { l += eps; r -= eps; b += eps; t -= eps; filldraw((l, b) -- (l, t) -- (r, t) -- (r, b) -- cycle, p + opacity(0.5)); } void dottedrect(real l, real r, real b, real t) { l += eps; r -= eps; b += eps; t -= eps; draw((l, b) -- (l, t) -- (r, t) -- (r, b) -- cycle, dashed); } rect(5-eps,2+eps,5-eps,3,red); rect(1-eps,2+eps,5-eps,3,blue); rect(0-eps,2+eps,1-eps,4+eps,green); rect(0-eps,2+eps,1-eps,0+eps,orange); dot((1, 4)); dot((1, 1)); dot((2, 4)); dottedrect(0-eps,1+eps,5-eps,0+eps); dottedrect(0-eps,5+eps,5-eps,4+eps); [/asy][/asy] Then, the leftmost rectangle, and the topmost rectangle are also added (dashed in the picture above), to cover the entire rectangle. Note that this uses a total of $m+3$ rectangles. Thus, we need a total of, \[k \le 2n-2m+2 + m+3 = 2n-m+5 \le 2n+2\]since $m\ge 3$, as noted above. Case 2 : The point $(x_m,y_M)$ does not belong in $S$. Here, we perform the following algorithm. Say there are $m$ points on $\mathcal{L}$. Then, we cover the rectangle $\mathcal{R}$ which has $n-m$ points inside it, using $2n-2m+2$ rectangles. Afterwards, we place rectangles as follows, between the $m$ points on $\mathcal{L}$. [asy][asy] size(150); draw((0, 0) -- (0, 5) -- (5, 5) -- (5, 0) -- cycle); draw((1,0)--(1,4)--(5,4)--(5,0)--cycle,dashed); real eps = 0.1; void rect(real l, real r, real b, real t, pen p) { l += eps; r -= eps; b += eps; t -= eps; filldraw((l, b) -- (l, t) -- (r, t) -- (r, b) -- cycle, p + opacity(0.5)); } void dottedrect(real l, real r, real b, real t) { l += eps; r -= eps; b += eps; t -= eps; draw((l, b) -- (l, t) -- (r, t) -- (r, b) -- cycle, dashed); } rect(5-eps,3+eps,5-eps,3,red); rect(2-eps,3+eps,5-eps,3,blue); rect(0-eps,2+eps,5-eps,1+eps,orange); rect(0-eps,2+eps,1-eps,0+eps,green); dottedrect(0-eps,1+eps,5-eps,0+eps); dottedrect(0-eps,5+eps,5-eps,4+eps); dot((1, 1)); dot((3,4)); dot((2, 4)); [/asy][/asy] Then, the leftmost rectangle, and the topmost rectangle are also added (dashed in the picture above), to cover the entire rectangle. Note that this uses a total of $m+3$ rectangles. Thus, we need a total of, \[k \le 2n-2m+2 + m+3 = 2n-m+5 \le 2n+2\]for $m\ge 3$. However, if $m<3$ ($m=2$) then note that one of the sides of $\mathcal{L}$ can be covered using a single rectangle, so the dotted rectangle in this direction can be removed. Thus, we only need $m+2$ rectangles, so again the total is at most $2n+2$. Thus, the induction is complete and we can always guarantee being able to cover the rectangle using at most $2n+2$ rectangles, as desired.