Math Proofs of Google Code Jam Qualification Round 2013 Problems

Problems of Google Code Jam Qualification Round 2013 can be found at http://code.google.com/codejam/contest/2270488/dashboard

$\newcommand{\lyxlock}{}$

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use $0,i,1,-1$ to represent “ “, T, O, X. So if$\left\Vert \sum_{i=1}^{4}a_{i,i}\right\Vert >3$ , then some one won.

2 Problem B. Lawnmower

Theorem.$\left(a_{i,j}\right)$ is a possible pattern if $$a_{i,j}=\min\left(\max\left(\left\{ a_{i,k}\right\} \right),\max\left(\left\{ a_{k,j}\right\} \right)\right)$$ for every $i,j$ .

Proof.

Can be easily proved by induction on $N=\sum_{i,j}M-a_{i,j}$ , where $M=\max\left(\left\{ a_{i,j}\right\} \right)$ .

         

     

3 Problem C. Fair and Square

Let $$N=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots+a_{1}10+a_{0}$$ , where $a_{i}\in\left\{ 0,1,\ldots9\right\}$ and $a_{n}\neq0$ . Denote by $\delta_{k}\left(x\right)$ the $\left(n-k+1\right)$ -th digit of $x$ , then we have $\delta_{k}\left(x\right)=a_{k}$ .

Assume $N$ is a palindrome, i.e., $a_{i}=a_{n-1}$ for every $i$ .

Let $b_{k}$ be the coefficient of $x^{k}$ of $$\left(a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}+a_{0}\right)^{2},$$ that is, $$b_{k}=\sum_{i=\max\left(0,k-n\right)}^{\min\left(k,n\right)}a_{i}a_{k-i}.$$

Theorem. $N^{2}$ is also a palindrome iff $b_{k}\leq9$ for all $k$ .

Proof.

($\Leftarrow$ )

Trivial.

($\Rightarrow$ )

Observe that $b_{k}=b_{2n-k}$ for all $k$ . We prove the statement by mathematical induction on $k$ for $k\leq n$ .

Case $k=0$ :

Since $$a_{n}^{2}10^{2n}\leq N^{2}<\left(a_{n}+1\right)^{2}10^{2n}$$ and $$\delta_{0}\left(N^{2}\right)=\delta_{0}\left(a_{0}^{2}\right)=\delta_{0}\left(a_{n}^{2}\right),$$ it is easy to see that $a_{0}=a_{n}\in\left\{ 1,2,3\right\}$ . So $b_{0}=a_{0}^{2}\leq9$ .

Moreover, we also know that $N^{2}$ has $2n+1$ digits and hence $\delta_{2n-k}\left(N^{2}\right)=\delta_{k}\left(N^{2}\right)$ for all $k\leq2n$ .

Case $k>0$ :

Suppose $b_{i}\leq9$ for all $i<k$ , we want to show $b_{k}\leq9$ .

By the induction hypothesis, we know that $\delta_{2n-i}\left(N^{2}\right)=\delta_{i}\left(N^{2}\right)=b_{i}=b_{2n-i}$ for all $i<k$ . So

$$\begin{eqnarray*} 10^{2n-k-1}\cdot\left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \sum_{i=2n-k-1}^{2n}\delta_{i}\left(N^{2}\right)10^{i}\\ & = & \sum_{i=2n-k-1}^{2n}b_{i}10^{i} \end{eqnarray*}$$

On the other hand, $$\begin{eqnarray*} \left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \left\lfloor \frac{\sum_{i=0}^{2n}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor \\ & = & \frac{\sum_{i=2n-k-1}^{2n}b_{i}10^{i}}{10^{2n-k-1}}+\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor . \end{eqnarray*}$$ Therefore, $\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor =0$ , hence $$b_{k}=b_{2n-k}\leq\frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k}}<10.$$

  

  

Corollary. $N^{2}$ is also a palindrome iff $\sum_{i=0}^{n}a_{i}^{2}\leq9$ .

Proof.

$b_{n}=\sum_{i=0}^{n}a_{i}a_{n-i}=\sum_{i=0}^{n}a_{i}^{2}$ .

($\Leftarrow$ )

$b_{n}\geq b_{k}$ for every $k$ by Cauchy-Schwarz inequility.

($\Rightarrow$ )

Trivial.

In particular, if $N\neq3$ , then $a_{i}\in\left\{ 0,1,2\right\}$ .

4 Problem D. Treasure

Let $T\subseteq\mathbb{N}$ be the set of all key types. Assume $0\notin T$ .

Construct a directed graph $G=\left(V,E\right)$ as following:

• $V=T\cup\left\{ 0\right\}$
• $\left(0,j\right)\in E$ iff we starts with at least one key of type $j$ .
• If $i\neq0$ , then $\left(i,j\right)\in E$ iff there is a key of type $j$ in a box of type $i$ .$b_{n}\geq b_{k}$ for every palidrone $N$ by Cauchy-Schwarz inequility.

Denote by $B\left(i\right)$ the number of boxes of type $i$ and $K\left(i\right)$ the total number of keys of type $i$ (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Proof.

($\Rightarrow$ )

If $B\left(j\right)>K\left(j\right)$ , then we don’t have enough keys of type $j$ to open all boxes of type $j$ .

If there is no path from $0$ to $j$ , then it means we are unable to get any key of type $j$ .

($\Leftarrow$ )

We prove this by induction on the number of boxes. Denote by $N$ the number of boxes.

Assume for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Case $N=1$ :

Then all vertices in $G$ are leaves except $0$ and the type of the only box. So there must be an edge from 0 to the type of the box.

Case $N>1$ :

Suppose the theorem holds for the case with $N-1$ boxes.

There are at least one $\left(0,i\right)\in E$ . Consider we open a box of type $i$ (that contains a key of type $i$ if possible). Assume we destroy the key and the box just opened, then we have a setting of $N-1$ boxes. In this setting, we still have $B\left(j\right)\leq K\left(j\right)$ for all $j$ . Let $G'=\left(V',E'\right)$ be the directed graph of this $\left(N-1\right)$ -box setting.

If $B\left(i\right)=1$ , then all children of $j$ in $G$ become children of $0$ , $0$ can still reach all other types in $G'$ .

Assume $B\left(i\right)>1$ .

If $\left(i,i\right)\in E$ , then we can open a box of type $i$ that contains a key of type $i$ .

Otherwise, because $K\left(i\right)\geq B\left(i\right)>1$ , we still hold at least one key of type $i$ after we open a box of type $i$ (and destroy the key).

Either way, $\left(0,i\right)\in E'$ . Therefore, for every child $j$ of $i$ in $G$ , either

1. $\left(0,j\right)\in E'$ (if a key of type $j$ is in the box we just opened), or

2. $\left(i,j\right)\in E'$ and so there is a path from $0$ to $i$ and then to $j$ .

So $0$ can still reach very vertex in $G'$ .

By induction hypothesis, the remaining $N-1$ can also be opened.

  

  

By the proof of the theorem, there is a simple algorithm to open all boxes: open any box unless you have just one key of that type and box does not contain a key that can open itself.

However, this algorithm may not yield a "lexicographically smallest" way to open the boxes.

The solve the problem, you should open the box with smallest number such that either this box is the last one of type $i$ or there is still a way to get a type $i$ key.

---

Document generated by eLyXer 1.2.5 (2013-03-10) on 2013-04-16T11:23:46.409386