Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a table there are n columns and m rows, n > m. Some cells are marked by stars, and in each column there's at least one star. Show that there is a star for which there are less stars in its column than in its row.

share|improve this question
1  
What level of formalism is expected? What is the context? The result is completely obvious, so to submit an acceptable 'proof', knowing this would help. –  gnometorule Feb 28 '13 at 13:41
    
The result doesn't seem that obvious to me. Can you show me an informal proof? –  muzzlator Feb 28 '13 at 13:44
    
the same goes here. and as much as formalism that you can. –  user64370 Feb 28 '13 at 15:25
    
@muzzlator: This sounded a bit glib, for which I apologize. I meant (and still think) that this I'd obvious when you look at it; but this doesn't mean a proof is (it is not). I have one though, and am typing this up. –  gnometorule Feb 28 '13 at 16:35

2 Answers 2

up vote 2 down vote accepted

First,  

$\underline{Note}$: If the result holds for a matrix $A^{m, m +k}:=B$, it holds for $A^{m, m+k + 1}:=C$, for $k \ge 1$, the same matrix $B$ with a column added.  

This is obvious: there is at least one row-column combination in $B$ where the result holds. Adding one or more stars in a new column cannot change this.  

So, wlog, one can assume in what follows that the matrix is of form $$A \in M^{m, m+1}.$$ Note next that the sum of stars $r_i$ in row $i$ and the sum of stars $r^j$ in column $j$ must satisfy.  $$\sum_{i = 1}^m r_i = \sum_{j=1}^{m+1} r^j \quad (1),$$ and that, by construction, $$r^j \geq 1 \text{ for all j} \quad (2).$$ Now, assume to the contrary that the claim is wrong.  Then  $$r_i \leq r^i \text{ for all i} \quad (3)$$ But then:   $$\begin{align} \sum_{j=1}^{m+1} r^j & = r^{m+1} + \sum_{j=1}^m r^j \\ & \geq r^{m+1} + \sum_{i=1}^m r_i \quad \text{using (3)} \\ & \gt \sum_{i=1}^m r_i \quad \text{using (2), } \\ \end{align}$$ which contradicts (1). So there is at least one $i$ for which (3) is false, which was to be shown. 

Edit (03/04): See Macavity's comment below for how to complete the argument (thank you!).

share|improve this answer
    
I'm a bit confused about how this proof works, why is equation $(3)$ the claim? It doesn't say that the stars have to belong to the diagonal of the matrix which is almost what $(3)$ is saying? –  muzzlator Mar 1 '13 at 3:14
    
@muzzlator: You're right, it's a bit careless. To be perfectly precise, you need to link a column with a specific row thar has an entry in the column. It gets less elegant, but it goes through in essence. –  gnometorule Mar 1 '13 at 3:47
    
@muzzlator: To be perfectly honest, I read this, them thought about it while walking, and remembered it as exactly what i proved... The adjustment though I strongly believe is minor, even very formal, but requires careful indexing. I really don't want to keep beating this horse, but if you feel like finishing off from here, you got my upvote coming in. :) –  gnometorule Mar 1 '13 at 4:10
    
now i'm confuse.. –  user64370 Mar 1 '13 at 7:18
2  
@gnometorule In the interests of completing this argument, you could note that whether the matrix satisfies the condition or not is invariant to (1) removing all empty rows (2) re-ordering of columns (or rows). Thus it is sufficient to consider an $m$ by $(m+1)$ matrix with non-empty rows (and columns); and by reordering columns, one can always have an equivalent matrix with stars in all $a_{i, i}$. Your argument then applies. –  Macavity Mar 4 '13 at 4:49

While completing @gnometorule's argument was easier, I thought the following approach is also worth mentioning:

Let $S(i, j)$ denote a function which gives $1$ if there is a star in cell from column $i$ and row $j$, and $0$ otherwise. Then we have,

$\sum_{i, j} S(i, j) = X$, the total number of stars.

Also if $C_i$ denotes the number of stars in column $i$ and $R_j$ denotes the number of stars in row $j$, we have
$\sum_{i=1}^n C_i = \sum_{j=1}^m R_j = X$

Further, it can be noted that $\sum_j S(i,j) = C_i$ and $\sum_i S(i,j) = R_j$

If all starred cells $(i, j)$ are such that $C_i \ge R_j$, then summing over all cells we have:
$\sum_{i, j} (C_i - R_j) S(i, j) \ge 0$

$\implies \sum_{i, j} C_i S(i, j) \ge \sum_{i, j} R_j S(i, j) $

$\implies \sum_{i} C_i C_i \ge \sum_{j} R_j R_j $

$\implies \sum_{i=1}^n C_i^2 \ge \sum_{j=1}^m R_j^2 $

Now, I believe the above inequality is not possible for such column and row sums, i.e. if:
$0 < C_i \le m$ and $0 \le R_j \le n$ with $n > m$, but have not been able to prove it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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