[Discrete-math-seminar] Wed Mar 7, 11am seminar, Robert Ellis

Robert Ellis rellis at math.iit.edu
Tue Mar 6 12:47:56 CST 2007


Part 2 of this talk below was moved to tomorrow, Wed Mar 7 due to Michael 
presenting on Feb 28 ahead of his conference.

I will concentrate on a proof of Spencer and Winkler related to the last 
paragraph below.

======================
Speaker: Robert Ellis (IIT Applied Mathematics)
Title: Three balls on a cliff, part 2
Time: 11:00am
Location: E1 241

Abstract: Three balls are placed on a cliff at distance k from the edge. Two
players, Paul and Carole, play the following q-round game.  Each round, Paul
splits the balls into two subsets.  Then Carole chooses one of the subsets and
moves each ball in it one step closer to the cliff (at position 0 a ball falls
off).  We discuss winning strategies for q-round games with the following
goals.

1) Paul wins if after q rounds at most 1 ball remains on the cliff.
2) Paul wins if after q rounds at least 1 ball remains on the cliff.

In general, we can consider n balls instead of 3.

The first goal corresponds to an adaptive error-correcting code of very high
radius, and the second to an adaptive covering code of very high radius.  We
present exact formulas for some small cases.

We will discuss what questions are open and also some results of Spencer and
Winkler when n, k, q all go to infinity, but k is a fraction of q (i.e., high
radius adaptive codes).


More information about the Discrete-math-seminar mailing list