5
$\begingroup$

I saw this question but I couldn't find the answer. Assume that we have a 10x10 table, and it's filled with 0 to 9 numbers ( 10 of each of them are in the table, 10x zero, 10x one, and ... )

By using graph, prove that we have a column or a row that we can find at least 4 different numbers in it.

edit: I have found this method to create a graph from any table-matrix : https://www.math3ma.com/blog/matrices-probability-graphs

after that, I thought that it would be a good way to use coloured edges. and now the thing to prove is to have a vertex with at least four colour edges connected to it. maybe with pigeonhole, the problem can be solved but I couldn't

$\endgroup$
  • 1
    $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ – José Carlos Santos Jun 25 at 7:34
  • $\begingroup$ Thank you for your advice, I'll do that $\endgroup$ – III_phr Jun 25 at 7:40
6
$\begingroup$

For each number $i$ from $0$ to $9$ let $r_i$ and $c_i$ be the number of rows and columns, respectively, containing the number $i$. Since all ten instances of $i$ are contained in a table with dimensions $r_i$ and $c_i$, we have $r_i\times c_i\ge 10$. It easily follows $r_i+c_i\ge 7$. It follows $\sum_i r_i+c_i\ge 70$. Wthout loss of generality we can suppose that $\sum r_i\ge 35$. The pigeonhole principle implies that there exists a row which is counted in at least four $r_i$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for your neat and simple proof. But the question asks us to prove the term by using the graph theory. $\endgroup$ – III_phr Jun 26 at 4:32
  • 2
    $\begingroup$ @III_phr I was started from a graph interpretation of the question (We have a coloring of edges of a complete directed graph with $10$ vertices into colors from $0$ to $9$. For each $i$ let $r_i$ (resp. $c_i$) be the number of vertices which have an incoming (resp. outgoing) edge of color $i$. Show that there exists a vertex incident to edges of four distinct colors). But then, dealing with the adjacency matrix, I saw this solution. It turned out that the solution can be more simply presented without graph interperetation, so I skipped it as non-needed. $\endgroup$ – Alex Ravsky Jun 26 at 5:48
  • 1
    $\begingroup$ Oh, your right, it's a simpler way of presentation of your way. and to be considered, I think that just implementing the question by graph and then solving it is enough, and there is no need to use special graph theorems. Thanks again! $\endgroup$ – III_phr Jun 26 at 6:08

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.