6
$\begingroup$

A table $10\times 10$ is divided in $100$ unit squares. We color each unit square with one color so that no column or row contains more than $5$ colors. How many colors can we use at most?

Any idea how to solve it with more graph theoretical aproach?

Wrong: I was thinking about to define a graph with $100$ vertices and two are connected if they are of the sam color and in the same line (row or column).Then each component is exactly the set of all vertices of the same color and thus we need to find a maximum number of components...

$\endgroup$
4
  • 1
    $\begingroup$ "Then each component is exactly the set of all vertices of the same color" isn't quite right. For example if all the diagonals were color A, and the off-diagonal were color B, then we would have 11 components, 10 of which correspond to the diagonal elements. $\endgroup$ – Calvin Lin Jul 16 '20 at 2:26
  • $\begingroup$ Yes, I see @CalvinLin I suppose that buried all my hopes there is a solution using graphs. $\endgroup$ – Aqua Jul 16 '20 at 13:54
  • 1
    $\begingroup$ My straightforward graph-theoretical model provides a weaker bound than L3435’s answer as follows. Consider a complete bipartite graph $G=K_{10,10}$ with the bipartition parts $\{v_1,\dots, v_{10}\}$ and $\{u_1,\dots, u_{10}\}$. For each $1\le i,j\le 10$ let an edge between $v_i$ and $v_j$ has a color of a square at the intersection of $i$-th row and $j$-th column. $\endgroup$ – Alex Ravsky Jul 18 '20 at 15:47
  • 1
    $\begingroup$ Then the problem condition means that to each vertex of $G$ are incident edges of at most $5$ colors. Assume that there are $c$ colors in total. When we pick an edge for each of the colors we obtain a subgraph $H$ of $G$ with $c$ edges. Since each edge of $H$ has degree at most $5$, we have $c\le 50$. Maybe picking edges more carefully we can obtain a better bound, but now I don’t see an easy way to do this. So I can guess that to develop a proper graph-theoretical approch to solve this problem can be a harder task than to obtain a combinatorial answer. $\endgroup$ – Alex Ravsky Jul 18 '20 at 15:47
12
+100
$\begingroup$

We claim the answer is $41$. To see that we can indeed reach $41$ colours, just choose $4$ diagonals and colour each square on those diagonals with a different colour, resulting in $40$ colours, and every other square with the $41$st colour.

enter image description here

Suppose there exist two rows that share no colours. That gives at most $10$ different colours, but seeing as each column can only get us $3$ new colours, we reah a bound of $10+3\cdot 10=40<41$.

Now suppose every two rows share a colour. In particular, every row shares a colour with the first row. That gives us at most $5$ new colours in the first row and at most $4$ in the following $9$ rows, with $5+9\cdot 4=41$ colours in total.

$\endgroup$
6
  • 1
    $\begingroup$ Why are there $4$ diagonals? The table has $2$ diagonals. Did I misunderstand something? (I didn't downvote. I think you were onto something, but I wasn't sure.) $\endgroup$ – Batominovski Jul 10 '20 at 11:10
  • $\begingroup$ They meant paralell to main diagonal? $\endgroup$ – Aqua Jul 10 '20 at 11:11
  • 2
    $\begingroup$ OK, so I guess, the answer would probably be clearer if the "diagonals" are specified. Say, all $40$ cells indexed by $(i,j)$ where $j-i\equiv 0,1,2,3\pmod{10}$ have $40$ distinct colors, and all other cells have the same color. $\endgroup$ – Batominovski Jul 10 '20 at 11:17
  • 2
    $\begingroup$ Beautiful solution. Would never have thought of this myself. $\endgroup$ – K.defaoite Jul 10 '20 at 14:26
  • 1
    $\begingroup$ @Aqua In case this idea may lead you to a solution, my construction was using the rows and columns as one set of vertices, and the colors as another set of vertices. Then, you have a bipartite graph where an edge connects between a color and a row/column that contains that color. Then, each color has degree at least $2$. Each row/column has degree at most $5$. Then, no more idea. $\endgroup$ – Batominovski Jul 16 '20 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.