$ 1650$ students are arranged in $ 22$ rows and $ 75$ columns. It is known that in any two columns, the number of pairs of students in the same row and of the same sex is not greater than $ 11$. Prove that the number of boys is not greater than $ 928$.
Problem
Source: CWMO 2003, Problem 8
Tags: inequalities, function, vector, graph theory, combinatorics unsolved, combinatorics
03.01.2009 22:29
I like this kind of problems. Let $ A_1,...,A_{75}$ be subsets of $ B=\{1,2,...,22\}$ definded like it folows: Let $ j\in B$, then $ j\in A_i \Longleftrightarrow$ student at $ (i,j)$ is boy. We are interested at $ \sum_{i=1}^{75}|A_i| =: a$. Define bipartite graph like this: For $ b\in B$ and pair $ \{A_i,A_j\}$: \[ b\sim \{A_i,A_j\} \Longleftrightarrow x\in A_i\cap A_j \vee x\in A'_i\cap A'_j\] Let $ b\in B$ be in $ x$ set among $ A_1,A_2...$. Then degree of $ b\in B$ is \[ d(b) = {x\choose 2} +{75-x \choose 2} = x^2-75x +75\cdot 37=: f(x)\] By asumption each pair $ \{A_i,A_j\}$ is connected with at most 11 elements from $ B$, so $ a_{i,j}\leq 11$, where $ a_{i,j}$ is degree of pair $ \{A_i,A_j\}$. Now we have (double counting): \[ \sum_{b\in B}d(b) = \sum_{i<j}a_{i,j}\leq {75\choose 2}\cdot 11\] On the other hand left side is by Jensen inequality (function $ f$ is convex): \[ 22f({a\over 22})\leq \sum_{b\in B}d(b)\] From here we can easly get $ a\leq 520$.
14.09.2010 04:53
Probably the mistake in the above proof is just in the last computation - clearly $a$, the number of boys, cannot be at most $520$, as the problem being symmetrical in boys and girls, it will mean $g$, the number of girls, is also at most $520$, but the total number of children is $22\cdot 75 = 1650$. Alternative Solution. Consider a $2m \times n$ array, where on any pair of columns the number of gender differences of children on a same row is at least $m$. Denote by $b_i$ the number of boys on row $i$, by $g_i = n - b_i$ the number of girls, by $B = \sum_{i=1}^{2m} b_i$ the total number of boys, by $N$ the total number of such gender differences in the array. Then $N = \sum_{i=1}^{2m} b_i(n-b_i) \leq 2m\left(\dfrac {\sum_{i=1}^{2m} b_i} {2m}\right)\left(n - \dfrac {\sum_{i=1}^{2m} b_i} {2m}\right) = \dfrac {B(2mn - B)} {2m}$ by Jensen's inequality, since the function $\varphi(x) = x(n-x)$ is concave. On the other hand (by double counting over all pairs of columns) $N \geq \binom {n} {2} m = \dfrac {mn(n-1)} {2}$. It follows $B^2 - 2mnB + m^2n(n-1) \leq 0$, so $m(n-\sqrt{n}) \leq B \leq m(n+\sqrt{n})$. Under the conditions of the problem, with $m=11$ and $n=75$, it follows that $730 \leq B \leq 920$. The punch line however comes now! Replace the boys by $+1$ and the girls by $-1$; the statement of the problem now reads that the column vectors, seen as real vectors in $\mathbb{R}^{2m}$, have pairwise non-positive dot product. It can be proven though that the maximum number of such vectors in $\mathbb{R}^{d}$ is $2d$, with equality only if $d$ of them are pairwise orthogonal, while the other $d$ are negative multiples of the first $d$ (thus also pairwise orthogonal, with the pairs of collinear vectors having as dot product the product of their norms with a minus sign), which of course can be achieved (take the $\pm$ versors of the axes). However, our vectors need have entries equal to $\pm 1$; or a complete set of such pairwise orthogonal vectors can exist only if $d$ is a multiple of $4$ - check Hadamard matrices topic (the conjecture is that they always exist if $4 \mid d$). What this all means in our case is that the object of the problem is empty; $n=75$ is too large as compared to $2d=4m=44$, while even that cannot be achieved, since $d=2m=22$ is not a multiple of $4$, so not even $44$ columns may be possible in such an array! Just fall back on the general proof for $m$ and $n$, keeping in mind the limitations described in the above.
27.08.2018 01:33
Nice solution with double counting (maybe similar to above not sure)Number of boys is $X$.We double count number of pairs boy,boy or girl,girl that are in same row(this number is $T$ ).Number rows from $1$ to $22$ (starting from top) and let $d_i$ be number of boys in row $i$.Now $T=\sum_{i=1}^{22}\binom{d_i}{2}\binom{75-d_i}{2}$ and from quadratic arithmetic inequality we get $T\ge\frac{1}{2}(\frac{X^2}{22}-X+\frac{(1650-X)^2}{22}-(1650-X))$ Now we see that this identity grows as $X$ grows and it starts when $X\ge824.5$ so $\frac{1}{2}(\frac{X^2}{22}+\frac{(1650-X)^2}{22}-1650)\ge\frac{1}{2}(\frac{929^2}{22}+\frac{(1650-929)^2}{22}-1650)=30604,136\cdots$ .On the other hand in any pair of columns there is less than or equal to $11$ pairs so $T\le11\binom{75}{2}$ from which follows $T\le30525$ .Collecting $30525\ge T \ge30604,136\cdots$ contradiction and we are done .