Is There a Clever Strategy to Solve This Week's Math Challenge?

[Ackbach]

Here is this week's POTW:

-----

Let $a_j,b_j,c_j$ be integers for $1\leq j\leq N$. Assume for each $j$, at least one of $a_j,b_j,c_j$ is odd. Show that there exist integers $r$, $s$, $t$ such that $ra_j+sb_j+tc_j$ is odd for at least $4N/7$ values of $j$, $1\leq j\leq N$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 265 - May 30, 2017

This was Problem B-1 in the 2000 William Lowell Putnam Mathematical Competition.

Congratulations to Opalg for what I consider to be a particularly clever solution to this week's POTW:

Spoiler

We are only interested in whether the numbers are even or odd, so we may as well reduce mod 2 and assume that all the numbers $a_j,b_j,c_j$, and also $r,s,t$ are $0$ or $1$.

There are eight possible triples $(0,0,0)$, $(0,0,1)$, $(0,1,0)$, $(0,1,1)$, $(1,0,0)$, $(1,0,1)$, $(1,1,0)$, $(1,1,1)$. None of the triples $(a_j,b_j,c_j)$ can be equal to $(0,0,0)$ (because each of them must contain an odd number). Also, $(r,s,t) \ne (0,0,0)$ (because then $ra_j + sb_j + tc_j = 0$ for all $j$, which is not what we want).

Let $P$ be the $3\times7$ matrix whose columns are the seven possible choices for $(r,s,t)$: $P = \begin{bmatrix} 0&0&0&1&1&1&1 \\ 0&1&1&0&0&1&1 \\ 1&0&1&0&1&0&1 \end{bmatrix}.$ Then $$P^{\small \textsf T}P = \begin{bmatrix}0&0&1 \\ 0&1&0 \\ 0&1&1 \\ 1&0&0 \\ 1&0&1 \\ 1&1&0 \\ 1&1&1 \end{bmatrix} \begin{bmatrix} 0&0&0&1&1&1&1 \\ 0&1&1&0&0&1&1 \\ 1&0&1&0&1&0&1 \end{bmatrix} = \begin{bmatrix} 1&0&1&0&1&0&1 \\ 0&1&1&0&0&1&1 \\ 1&1&0&0&1&1&0 \\ 0&0&0&1&1&1&1 \\ 1&0&1&1&0&1&0 \\ 0&1&1&1&1&0&0 \\ 1&1&0&1&0&0&1 \end{bmatrix}$$ (where the product is formed using mod 2 arithmetic). Notice that each row of $P^{\small \textsf T}P$ contains exactly four $1$s.

Let $M$ be the $N\times3$ matrix whose rows are the triples $(a_j,b_j,c_j)$: $M = \begin{bmatrix} a_1&b_1&c_1 \\ a_2&b_2&c_2 \\ \vdots&\vdots&\vdots \\ a_N&b_N&c_N \end{bmatrix}.$ The $(j,k)$-element of the product $MP$ is $ra_j + sb_j + tc_j$, where $(r,s,t)$ is the $k$th column of $P$. Each row of $MP$ is the same as one of the rows of $P^{\small \textsf T}P$ and therefore contains four $1$s. Thus $MP$ contains $4N$ $1$s in total. But $MP$ has seven columns, so at least one column must contain at least $4N/7$ $1$s. This says that if $(r,s,t)$ is the corresponding column of $P$ then $ra_j + sb_j + tc_j = 1$ for at least $4N/7$ values of $j$.