Conference rusure::math

This is a pretty application of the pigeonhole principle.  Of course, the real
problem is to solve for the general case of an alphabet of size k.  The smallest
n which satisfies the conditions is n=2^k.

Let a1,a2,... be an infinite alphabet, and assume we are only using the first k
symbols from it.  Consider an arbitrary string of length n of these symbols.

For each i, 0<=i<=n, let v(i) be the vector (o1,...,ok) where om is the number
of occurrences (mod 2) of am in the initial substring of length i.  (v(0) will
be a vector of zeros).  Then a nonempty substring starting at index r and ending
at s has an even number of occurrences of every letter iff v(r-1)=v(s).  (The
substring can be obtained by lopping off a [possibly empty] initial substring
from a longer initial substring.)

If n=2^k, there are 2^k+1 values of the vector, so by the pigeonhole principle
the values at some indexes i0 and i1, where i0<i1, must be equal.  Then the
substring extending from indexes i0+1 to i1 is a nonempty substring in which
every letter occurs an even number of times.

It remains to show that for n=2^k-1 we can construct a string which does not
have this property.  Let c(1)=a1, and c(k+1)=c(k) ak c(k).  Then every nonempty
substring of c(k) either contains the middle ak exactly once, hence contains ak
an odd number of times, or it is a substring of the initial or final c(k), so
contains some letter an odd number of times by induction.

For the given problem, k=11, so n=2048.

There is a simple generalization based on the fact that "no letter occurs an odd
number of times" is equivalent to "every letter occurs an even number of times."

If we replace that phrase with "every letter occurs a multiple of s times" for
some integer s>=1, the answer becomes s^k rather than 2^k.  Indeed, we can go so
far as to give each letter ai its own modulus mi>=1, and make the phrase "each
letter ai occurs a multiple of mi times."  The answer is then the product P of
all the moduli.

The construction of the string of length P-1 needs to be slightly modified: let
c(0) be the empty string, and c(k) = { c(k-1) ak }^(mk-1) c(k-1), so that
c(k)=c(k-1) if mk=1.  That is, c(k) is mk copies of {c(k-1) ak} with the final
ak removed.

    Several times in this conference I have seen references to the
    "Pigeonhole Principle".
    
    This is something that never came up in maths lessons and I have never
    seen a formal definition.
    
    At first I thought that it just said (for example) if 15 objects are
    distributed amongst 5 pigeonholes, then at least one pigeonhole gets at
    least 3 objects. But I think there must be more to it than that.
    
    Dick

As I learned it, the pigeonhole principle just says that if you put more than N
things into N pigeonholes, some pigeonhole must get more than one thing.

        If you put more than kN pigeons into N holes, then at least
        one hole gets at least k+1 pigeons (k and N positive integers).
        
        Dan

        I've even seen the term "pigeonhole principle" applied to
        infinite sets.  A finite union of finite sets is finite, so if
        the elements of an infinite set are partitioned into finitely
        many classes then at least one class is infinite. A countable
        union of countable sets is countable (in the general case one
        normally uses the countable axiom of choice to show this) so
        if the elements of an uncountable set are partitioned into
        countably many classes then at least one class is uncountable
        (assuming the countable axiom of choice).
        
        Dan