invert at P

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

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 coefficients.

In a similar vein,

so for some choice of th roots of unity and (any) nontrivial th root of unity , we have . But then

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 .)

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.

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.