Google Jam 2013 資格賽題目的數學證明
Posted by tjwei 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
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: 數學
0 意見:
張貼留言