New answers tagged

0 votes

$n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

In order for Bob to win, he needs that at least $\delta n$ columns have values at least $\delta n$ each. So Alice just needs to shuffle the colors to prevent this. In other words, we need $n$ subsets ...
user avatar
50 votes

Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

One cannot arrange 5 points in that manner, even if the coordinates are allowed to be any real numbers. Indeed, assume that the 5 points are $(x_n,y_n)$ with $x_1\leq\dotsb\leq x_5$. By the Erdős-...
user avatar
  • 85.1k

Top 50 recent answers are included