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.

Let . For fixed , let denote the number of positive such that is prime, and suppose for the sake of contradiction that there exists some such that for all . Fix a real ; if is the set of primes, then

\[\begin{align*}
N\sum_{k\ge1}\frac{1}{k^s} &\ge\sum_{k\ge1}\frac{g(k)}{k^s} \\
&=\sum_{p\in\mathbb{P}}\sum_{1\le f(T)for some  independent of . Any  gives the desired contradiction, since the sum of the reciprocals of the primes diverges.



Edit: Thanks.

The key is to realize that we probably want to use pigeonhole somehow (the and are rather ugly for an inductive argument). But this is not really related to the geometry of numbers since we have at least as many equations as variables, so we want to "fix" some sort of vector and then find the 's from there (the three vectors , etc. are orthogonal to ).

Now we want to get a feel of the most natural way to fix . Note that we can parameterize all solutions to by
This gives us the idea of fixing (all nonzero for pigeonhole to work out).

Intuitively, to get the best bounds for this simplest case, we want to take (or all ). (Furthermore, if we had, say, , then it would be hard to control the requirement that are all nonzero.) Luckily, the rest works out easily: to make as small as possible (for pigeonhole to work optimally, since we know all the are less than or equal to ), let the elements of be , and for the , choose from the first set of indices, for , choose from the second set of indices, and for , choose from the last set of indices. We get a total of (optimal by AM-GM) (note that and ), yet only triples with and are possible in the first place (to count all possible triples, we can assume the smallest number chosen is and then choose two larger values in the range ), so by pigeonhole, some must occur at least times, as desired.

Let .

For the minimum, note that we can keep doing the following: take , which kills at most two others in ( if they're in ), and repeat with the new set . Each time we remove at most elements, so we end up with at least elements, which is realized for .

For the maximum, we first analyze the one variable case to gain some intuition: of course, for fixed , we can just consider each residue modulo separately (and it's just alternating in , out , etc. for a fixed residue), where the best ratio is around , achieved for for .

With the proof and construction for the one variable case in mind, we suspect that for will give the maximum (we know it can't be far). Indeed, we can get with .

It remains to show that always. Assume for the sake of contradiction that for some .

First we get some crude estimations from alone: letting for and , we get
If is odd, this becomes , and if is even, then .

Hence . If , then , so and from the previous paragraph, . Thus , so because equality holds everywhere, we must have , which contradicts .

Otherwise, if , then , so , contradiction.

The property (say, goodness) holds iff for every two "polynomials" and (with real but not necessarily integer exponents), then .

We'll show that is good iff it's not a power of 2. To do this, we want to do some sort of bounding with values in (maybe ), algebraic manipulation (especially either using to telescope products some way or differentiation), or just special values. Screwing around, it turns out differentiation is pretty helpful here.

If is not a power of 2, then by the general Leibniz rule on and the fact that
for some polynomials (both facts are easily proven by induction), we can show by induction on (base case is just ) that (sorry for sloppiness, but this is assuming the strong inductive hypothesis for )
which implies for all . Thus (by induction/Stirling numbers) for all integers , so by easy bounding considerations .

Otherwise, let . For the construction, we take to be actual polynomials (i.e. with integer exponents), so taking the induction from the previous paragraph up until , we have that for some polynomial . Plugging this in, we have . We can just take (identically); then the sets of numbers corresponding to and suffice.

Edit: There's a cleaner way using rational approximation (assume all the guys are large integers). If is a root of with multiplicity , then for some . But then means that is a power of 2, as desired.

Suppose by way of contradiction that there's a set intersecting all hyperplanes with . WLOG ; now consider the polynomial (over )
where is taken so that . Since , . Since the coefficient of in is nonzero, CNS guarantees such that (), whence does not intersect the plane (obviously does not belong to it, and because , the second part of vanishes at and so the first cannot, whence does not intersect the plane either), contradiction.

On the other hand, the construction for is obvious: just take the set of with at least of the 's zero (if a plane does not contain the origin, it's WLOG of the form with , and so works).

Comment: This extends directly to any finite field .