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

Top 50 recent answers are included