## Proof By Lice!

From camels to lice. (A proof promised here.)

Theorem (Hopf and Pannwitz, 1934): Let $X$ be a set of $n$ points in the plane  in general position (no three points on a line) and consider $n+1$ line segments whose endpoints are in $X$.  Then there are two disjoint line segments.

Micha Perles’s proof by Lice:

Useful properties of lice: A louse lives on a head and wishes to lay an egg on a hair.

Think about the points in the plane as little heads, and think about each line segments between two points as a hair.

The proof goes as follows:

Step one: You take $n$ lice from your own head and put them on the $n$ points of \$X\$.

Step two: each louse examines the hairs coming from the head and lay eggs (on the hair near the head)

Step three (not strictly needed): You take back the $n$ lice and put them back on your head.

To make it work we need a special type of lice: spoiled-left-wing-louse.

A spoiled-left-wing louse lays an egg on a hair if and only if the area near the head,  180 degrees to the right of this hair is free from other hairs.

Lemma: Every louse lays at most one egg.

Proof of lemma: As you see from the picture, if the louse lays an egg on one hair, this hair disturbs every other hair.

Proof of theorem continued: since there are $n+1$ line segments and only at most $n$ eggs there is a hair X between heads A and B with no eggs.

We look at this hair and ask:

Why don’t we have an egg near head A: because there is a hair Y in the angle 180° to the right.

Why don’t we have an egg near head B: because there is a hair Z in the angle 180° to the right.

Y and Z must be disjoint. Q. E. D.

Remarks: We actually get a ZIG formed by Y, X, and Z

If we use right-wing-spoiled lice we will get a ZAG.

We can allow the points not to be in general position as long as one hair from a head does not contain another hair from the same head.

The topological version of this problem is the infamous Conway’s thrackle conjecture. See also Stephan Wehner page about it.

This entry was posted in Combinatorics, What is Mathematics and tagged . Bookmark the permalink.

### 5 Responses to Proof By Lice!

1. One can ask the question in the dual plane (points become lines and lines become points) and so extend it to pseudo-lines. Thm 1.10 here: https://www.cs.bgu.ac.il/~shakhar/my_papers/pseudolines.ps
extends those idea to pseudolines…

• Gil Kalai says:

Many thanks Shakhar. PS. many people cannot access ps files sp perhaps you can translate it to pdf?

2. shacharlovett says:

are louse = lice?

• Gil Kalai says:

Shachar, my inquiries strongly indicate that the plural of louse is lice. I dont know why the ‘s’ is transformed into ‘c’.

• jj says:

mouse and mice