Ideas and Graph Theory

Here’s an interesting problem. Consider n people standing in a circle. Each person knows the person just to their left and just to their right. Each person also knows (at most) one more person in the circle, which you, the problem solver, get to choose for them. You give one person a paper with a 0 on it. He’ll give each person he knows a paper with a 1 on it. Each of them will give each person they know a paper with a 2 on it. And at each step of the game, if a person has two papers of different number, he’ll burn the larger one. The question is: when everybody has a paper, what is the maximum number that will be written on any paper, where you’re choosing the graph configuration to minimize this number? Just to check yourself, the first few are n=4,5,…; N(n)=1,2,2,2,2,2,2,3,3.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s