Google Jam 2013 資格賽題目的數學證明

Posted by TJ Wei on 星期一, 4月 15, 2013 with No comments

這篇用英文打的,就不轉成中文了。原來的題目可以在這裡找到。

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use to represent “ “, T, O, X. So if , then some one won.

2 Problem B. Lawnmower

Theorem. is a possible pattern if for every .
Proof.
Can be easily proved by induction on , where .
         
     

3 Problem C. Fair and Square

Let , where and . Denote by the -th digit of , then we have .
Assume is a palindrome, i.e., for every .
Let be the coefficient of of that is,

Theorem. is also a palindrome iff for all .
Proof.
( )
Trivial.
( )
Observe that for all . We prove the statement by mathematical induction on for .
Case :
Since and it is easy to see that . So .
Moreover, we also know that has digits and hence for all .
Case :
Suppose for all , we want to show .
By the induction hypothesis, we know that for all . So
On the other hand, Therefore, , hence
  
  
Corollary. is also a palindrome iff .
Proof.
.
( )
for every by Cauchy-Schwarz inequility.
( )
Trivial.
In particular, if , then .

4 Problem D. Treasure

Let be the set of all key types. Assume .
Construct a directed graph as following:
  • iff we starts with at least one key of type .
  • If , then iff there is a key of type in a box of type . for every palidrone by Cauchy-Schwarz inequility.
Denote by the number of boxes of type and the total number of keys of type (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every , and there is a directed path from to in graph .
Proof.
( )
If , then we don’t have enough keys of type to open all boxes of type .
If there is no path from to , then it means we are unable to get any key of type .
( )
We prove this by induction on the number of boxes. Denote by the number of boxes.
Assume for every , and there is a directed path from to in graph .
Case :
Then all vertices in are leaves except and the type of the only box. So there must be an edge from 0 to the type of the box.
Case :
Suppose the theorem holds for the case with boxes.
There are at least one . Consider we open a box of type (that contains a key of type if possible). Assume we destroy the key and the box just opened, then we have a setting of boxes. In this setting, we still have for all . Let be the directed graph of this -box setting.
If , then all children of in become children of , can still reach all other types in .
Assume .
If , then we can open a box of type that contains a key of type .
Otherwise, because , we still hold at least one key of type after we open a box of type (and destroy the key).
Either way, . Therefore, for every child of in , either
1. (if a key of type is in the box we just opened), or
2. and so there is a path from to and then to .
So can still reach very vertex in .
By induction hypothesis, the remaining 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 or there is still a way to get a type key.
Categories: