Random Stuff
by math154, Dec 9, 2012, 10:59 PM
So I haven't updated in a long time... Here's some random stuff.
1. 3-D proofs for Brianchon and Pascal.
Click to reveal hidden text
2. Let
be positive rational numbers and let 
be integers greater than 1. If ![$\sum_{i=1}^{n}\sqrt[k_i]{a_i}\in\mathbb{Q}$](//latex.artofproblemsolving.com/6/d/3/6d3268640d63424770f2abb2e6c42657d054ace0.png)
, show that ![$\sqrt[k_i]{a_i}\in\mathbb{Q}$](//latex.artofproblemsolving.com/1/e/9/1e98b3af4db054d32f00d529032658c15875251a.png)
for all 
.
Click to reveal hidden text
3. (Russia 1998) Each square of a
square board contains either 
or 
. Such an arrangement is deemed successful if each number is the product of its neighbors. Find the number of successful arrangements.
Click to reveal hidden text
4. (Russia 2010) Let
be a connected graph disconnected by the removal of (all of the edges of) any odd cycle. Prove that is 4-partite.
Click to reveal hidden text
In other news, December TST is this Thursday and MIT decisionsshould will come out soon Saturday.
1. 3-D proofs for Brianchon and Pascal.
Click to reveal hidden text
This proof only works for non-degenerate cases (for Brianchon, 
all distinct points on opposite sides; for Pascal, no two opposite sides parallel)
circumscribes the circle with tangency points 
(
on 
, 
on 
, etc.)
lift stuff alternately by constant angles so that
is above, 
is below 
, etc. so that 
is a plane, etc.
now we get three planes of the form, 
, etc. that are not the same, but have pairwise intersections exactly equal to lines 
, 
, 
, which means that the three planes must intersect in a point, which must lie on all three lines; now project everything onto the plane of to get a proof of brianchon
for pascal, note that
are coplanar, so 
and 
intersect at a point on the line equal to the intersection of planes 
and 
, which also contains 
and 
if
, 
, 
, then the plane 
(possibly degenerate, but then the result's obvious) intersects plane at a line containing 
, 
, 
, so we're done
all distinct points on opposite sides; for Pascal, no two opposite sides parallel) circumscribes the circle with tangency points 
(
on 
, 
on 
, etc.)lift stuff alternately by constant angles so that
is above, 
is below 
, etc. so that 
is a plane, etc.now we get three planes of the form
, 
, etc. that are not the same, but have pairwise intersections exactly equal to lines 
, 
, 
, which means that the three planes must intersect in a point, which must lie on all three lines; now project everything onto the plane of to get a proof of brianchonfor pascal, note that
are coplanar, so 
and 
intersect at a point on the line equal to the intersection of planes 
and 
, which also contains 
and 
if
, 
, 
, then the plane 
(possibly degenerate, but then the result's obvious) intersects plane at a line containing 
, 
, 
, so we're done2. Let
be positive rational numbers and let 
be integers greater than 1. If ![$\sum_{i=1}^{n}\sqrt[k_i]{a_i}\in\mathbb{Q}$](http://latex.artofproblemsolving.com/6/d/3/6d3268640d63424770f2abb2e6c42657d054ace0.png)
, show that ![$\sqrt[k_i]{a_i}\in\mathbb{Q}$](http://latex.artofproblemsolving.com/1/e/9/1e98b3af4db054d32f00d529032658c15875251a.png)
for all 
.Click to reveal hidden text
Let 
and go by contradiction. For motivation we look at the 
case. WLOG 
are ``minimal'' in the sense that 
for 
. Then our assumption is equivalent to 
for all .
Note that
is the minimal polynomial of 
over the rationals, so 
. But then 
; by symmetry 
and we can easily get a contradiction by considering the ![$[x^{k_1-1}]$](//latex.artofproblemsolving.com/a/1/3/a131a3600dec6f0f8fc7d7d771d8e0224b7b78cc.png)
coefficients.
In a similar vein,
![\[x^{k_1}-a_1\mid \prod_{\omega_i^{k_i}=1,2\le i\le n}(S-x-\sum_{i=1}^{n}\omega_i a_i^{1/k_i})\in\mathbb{Q}[x],\]](//latex.artofproblemsolving.com/1/c/e/1ce1cb394f58859b98d50fe5b410b813d4c9a5a1.png)
so for some choice of
th roots of unity 
and (any) nontrivial 
th root of unity 
, we have 
. But then
![\[ 0=\Re(S-S) = \Re(a_1^{1/k_1}(1-\omega_1))+\sum_{i=2}^{n}\Re((1-\omega_i)a_i^{1/k_i}) > \sum_{i=2}^{n}\Re((1-\omega_i)a_i^{1/k_i}) \ge 0,\]](//latex.artofproblemsolving.com/2/3/9/2399ccddd04a1f97962cffb620d26fa61541fa66.png)
contradiction. (We can also take magnitudes and use the triangle inequality: for equality, the must be in the same positive direction since the 
are all positive, but then 
would be in 
.)
and go by contradiction. For motivation we look at the 
case. WLOG 
are ``minimal'' in the sense that 
for 
. Then our assumption is equivalent to 
for all .Note that
is the minimal polynomial of 
over the rationals, so 
. But then 
; by symmetry 
and we can easily get a contradiction by considering the ![$[x^{k_1-1}]$](http://latex.artofproblemsolving.com/a/1/3/a131a3600dec6f0f8fc7d7d771d8e0224b7b78cc.png)
coefficients.In a similar vein,
![\[x^{k_1}-a_1\mid \prod_{\omega_i^{k_i}=1,2\le i\le n}(S-x-\sum_{i=1}^{n}\omega_i a_i^{1/k_i})\in\mathbb{Q}[x],\]](http://latex.artofproblemsolving.com/1/c/e/1ce1cb394f58859b98d50fe5b410b813d4c9a5a1.png)
so for some choice of
th roots of unity 
and (any) nontrivial 
th root of unity 
, we have 
. But then![\[ 0=\Re(S-S) = \Re(a_1^{1/k_1}(1-\omega_1))+\sum_{i=2}^{n}\Re((1-\omega_i)a_i^{1/k_i}) > \sum_{i=2}^{n}\Re((1-\omega_i)a_i^{1/k_i}) \ge 0,\]](http://latex.artofproblemsolving.com/2/3/9/2399ccddd04a1f97962cffb620d26fa61541fa66.png)
contradiction. (We can also take magnitudes and use the triangle inequality: for equality, the
must be in the same positive direction since the 
are all positive, but then 
would be in 
.)3. (Russia 1998) Each square of a
square board contains either 
or 
. Such an arrangement is deemed successful if each number is the product of its neighbors. Find the number of successful arrangements.Click to reveal hidden text
For 
there are two; we restrict our attention to 
. Let 
. Take the 
of each entry so we're working in 
instead; we're choosing some of the 
entires to be 1. Viewing this as the equation 
(where boundary cases are 0 for convenience), we can set up a matrix equation 
where 
iff entries and 
(there are 
total) are neighboring, and 
has a 1 for each entry we include in the successful arrangement.
We show by induction on
that 
(whence 
must be the all-zero vector and there's exactly one solution)---note that for the matrix equation doesn't actually correspond to the original problem, but this is not an issue. To do this, observe that 
(as we're working ). Now for a fixed permutation 
that contributes 1 to the sum (i.e. doesn't vanish), draw an arrow from to 
for each ; we get a partition of the original 
board into disjoint directed cycles of size 1 or 
for some 
(arrows connect neighboring elements---these directed cycles correspond to permutation cycles). These cycles are nontrivially ``reversible'' iff 
, so pairing up the permutations with their reversals (this corresponds to 
), we're left (mod 2, of course) with the number of tilings of the grid using 
, 
, and 
tiles. Reflecting over the horizontal axis we're left with horizontally symmetric tilings; now reflecting over the vertical axis we're left with tilings that are both horizontally and vertically symmetric.
For odd
it's easy to check that 
where 
, 
, 
is Fibonacci, as all dominoes intersecting one of two axes must lie within the axes (by symmetry). By induction we get 
.
Comment. We can use this kind of symmetry argument directly on the original problem (e.g. consider the product of a successful arrangement with its vertical reflection, which results in another successful arrangement), which is slightly weaker but still works for the particular problem (we don't immediately get
), but the linear algebra setting is perhaps more motivated. It may be possible to do nontrivial general analysis on 
boards using the same recursive linear algebra ideas, but when both of 
are even it seems hard to reduce the problem.
there are two; we restrict our attention to 
. Let 
. Take the 
of each entry so we're working in 
instead; we're choosing some of the 
entires to be 1. Viewing this as the equation 
(where boundary cases are 0 for convenience), we can set up a matrix equation 
where 
iff entries and 
(there are 
total) are neighboring, and 
has a 1 for each entry we include in the successful arrangement.We show by induction on
that 
(whence 
must be the all-zero vector and there's exactly one solution)---note that for the matrix equation doesn't actually correspond to the original problem, but this is not an issue. To do this, observe that 
(as we're working ). Now for a fixed permutation 
that contributes 1 to the sum (i.e. doesn't vanish), draw an arrow from to 
for each ; we get a partition of the original 
board into disjoint directed cycles of size 1 or 
for some 
(arrows connect neighboring elements---these directed cycles correspond to permutation cycles). These cycles are nontrivially ``reversible'' iff 
, so pairing up the permutations with their reversals (this corresponds to 
), we're left (mod 2, of course) with the number of tilings of the grid using 
, 
, and 
tiles. Reflecting over the horizontal axis we're left with horizontally symmetric tilings; now reflecting over the vertical axis we're left with tilings that are both horizontally and vertically symmetric.For odd
it's easy to check that 
where 
, 
, 
is Fibonacci, as all dominoes intersecting one of two axes must lie within the axes (by symmetry). By induction we get 
.Comment. We can use this kind of symmetry argument directly on the original problem (e.g. consider the product of a successful arrangement with its vertical reflection, which results in another successful arrangement), which is slightly weaker but still works for the particular problem (we don't immediately get
), but the linear algebra setting is perhaps more motivated. It may be possible to do nontrivial general analysis on 
boards using the same recursive linear algebra ideas, but when both of 
are even it seems hard to reduce the problem.4. (Russia 2010) Let
be a connected graph disconnected by the removal of (all of the edges of) any odd cycle. Prove that is 4-partite.Click to reveal hidden text
Since we need to find a 4-(vertex)-coloring, the following lemma will help:
Lemma. Let
be two positive integers. A graph 
is 
-colorable iff there exists an edge partition 
such that 
and 
are 
- and 
-colorable, respectively.
Proof. Just use product coloring for the ``if'' direction: we can assign the color
to a vertex colored 
in 
, respectively.
Conversely, if is -colorable, then split the graph into sets 
, each containing the vertices of exactly colors; we can then take defined by 
and 
, which are - and -colorable, respectively. Alternatively, label the colors 
for 
and 
and define 
by the first and second coordinates, respectively---the induced subgraphs are clearly - and -colorable, and we can then remove duplicate edges from until we get an edge partition. (The idea is that independent sets behave like single vertices, and 
can easily be split in the desired form.) 
In view of the lemma, we try to find an edge partition such that
and 
are both bipartite.
Let be a maximal bipartite subgraph; then we can't add any more edges to 
without inducing an odd cycle. Now assume for the sake of contradiction that (where 
) has an odd cycle 
, 
. By the maximality of , 
and 
(indices modulo 
) are connected by a (simple) path of even length in (i.e. with edges in ) for all , so in particular 
are connected in 
for all 
. Then since is connected, every vertex 
is connected in 
to at least one vertex of 
, whence must be connected as well, contradicting the problem hypothesis. Hence must be bipartite and since is bipartite by construction, we're done by the lemma.
Comment. In fact, we could've taken to be a maximal forest (any spanning tree) instead of a maximal bipartite graph.
Lemma. Let
be two positive integers. A graph 
is 
-colorable iff there exists an edge partition 
such that 
and 
are 
- and 
-colorable, respectively.Proof. Just use product coloring for the ``if'' direction: we can assign the color
to a vertex colored 
in 
, respectively.Conversely, if
is -colorable, then split the graph into sets 
, each containing the vertices of exactly colors; we can then take defined by 
and 
, which are - and -colorable, respectively. Alternatively, label the colors 
for 
and 
and define 
by the first and second coordinates, respectively---the induced subgraphs are clearly - and -colorable, and we can then remove duplicate edges from until we get an edge partition. (The idea is that independent sets behave like single vertices, and 
can easily be split in the desired form.) 
In view of the lemma, we try to find an edge partition such that
and 
are both bipartite.Let
be a maximal bipartite subgraph; then we can't add any more edges to 
without inducing an odd cycle. Now assume for the sake of contradiction that (where 
) has an odd cycle 
, 
. By the maximality of , 
and 
(indices modulo 
) are connected by a (simple) path of even length in (i.e. with edges in ) for all , so in particular 
are connected in 
for all 
. Then since is connected, every vertex 
is connected in 
to at least one vertex of 
, whence must be connected as well, contradicting the problem hypothesis. Hence must be bipartite and since is bipartite by construction, we're done by the lemma.Comment. In fact, we could've taken
to be a maximal forest (any spanning tree) instead of a maximal bipartite graph.In other news, December TST is this Thursday and MIT decisions
This post has been edited 10 times. Last edited by math154, May 9, 2013, 2:29 PM
July 2014
June 2014