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 textThis 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
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 textLet
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
.)
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 textFor
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 textSince 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.
In other news, December TST is this Thursday and MIT decisions
should will come out
soon Saturday.
This post has been edited 10 times. Last edited by math154, May 9, 2013, 2:29 PM
by ntu0301, Mar 23, 2025, 7:37 AM 
that satisfy the following condition: For every integer k such that 
there always exists a positive integer 
that is divisible by n and 
. 
: sum of elements of 
is drawn externally on side 
of 
. Point 
is taken on 
. Find 
if 
.
for all 
.
the point 
is located on the side ![$[AB]$](http://latex.artofproblemsolving.com/a/d/a/ada6f54288b7a2cdd299eba0055f8c8d19916b4b.png)
, and 
is the foot of the perpendicular from 
on the line 
. The point 
belongs to the line 
. 
and 
with respect to the lines 
, respectively. Prove that:
is square and the quadrilateral 
is rhombus.
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 
.
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.
be a connected graph disconnected by the removal of (all of the edges of) any odd cycle. Prove that 
July 2014
June 2014
all distinct points on opposite sides; for Pascal, no two opposite sides parallel)
,
on 
,
is above, 
is below 
is a plane, etc.
,
,
,
,
are coplanar, so 
and 
intersect at a point on the line equal to the intersection of planes 
and 
,
and 
,
,
,
(possibly degenerate, but then the result's obvious) intersects plane 
,
,
,
and go by contradiction. For motivation we look at the 
case. WLOG 
are ``minimal'' in the sense that 
for 
.
for all 
is the minimal polynomial of 
over the rationals, so 
.
;
and we can easily get a contradiction by considering the ![$[x^{k_1-1}]$](http://latex.artofproblemsolving.com/a/1/3/a131a3600dec6f0f8fc7d7d771d8e0224b7b78cc.png)
coefficients.![\[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)
t
and (any) nontrivial 
t
,
.![\[ 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)
are all positive, but then 
would be in 
.
there are two; we restrict our attention to 
.
.
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 
(there are 
total) are neighboring, and 
has a 1 for each entry 
that 
(whence 
must be the all-zero vector and there's exactly one solution)---note that for 
(as we're working 
that contributes 1 to the sum (i.e. doesn't vanish), draw an arrow from 
for each 
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 
,
)
,
,
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.
where 
,
,
is Fibonacci, as all dominoes intersecting one of two axes must lie within the axes (by symmetry). By induction we get 
.
)
boards using the same recursive linear algebra ideas, but when both of 
are even it seems hard to reduce the problem.
be two positive integers. A graph 
is 
-
such that 
and 
are 
-
-
to a vertex colored 
in 
,
,
and 
,
for 
and 
and define 
by the first and second coordinates, respectively---the induced subgraphs 
can easily be split in the desired form.) 
and 
are both bipartite.
without inducing an odd cycle. Now assume for the sake of contradiction that 
)
,
.
and 
(indices modulo 
)
are connected in 
for all 
.
is connected in 
to at least one vertex of 
,