Los Angeles Math Circle

1/20: Circle meeting (Dimitri Shlyakhtenko)

Topics in Shannon s Information Theory
We will discuss a few basic topics from Shannon s information theory. As a warm-up for the circle meeting you may wish to try to devise optimal strategies for the following two games.

Game 1. Someone chooses an integer x between 1 and N. You are allowed to ask questions such as \\\"is x strictly bigger than ...\\\" to guess the value of x. How many questions do you need, and what are the questions?

Game 2. N points are marked on a circle. Someone chooses a point x. You are allowed to ask questions such as \\\"Is x within ... of point ...?\\\" to guess the value of x. How many questions do you need, and what are the questions?