Drinking Game. (1 Viewer)

[seanieg89]

Stumbled across a pretty funny mathematical drinking game / problem in graph theory posted by someone on Terence Tao's blog:

Say you have a group of n people. The player who is "it" says an integer k strictly between 1 and n+1 and at the same time everyone including this player points at another player. The directions people point form a directed graph. The person who has to drink is the person obtained by traversing k edges of this graph. This person is now "it".

Some interesting questions:

a) If we remove the restriction on how large k can be, prove that the player who is "it" can guarantee that he does not get himself.

b) What is the optimal choice of number for the player who is "it" assuming all pointing is random? (Optimal in the sense that it minimises his risk of getting himself.)

c) How can one 'try' to lose? Both with and without the restrictions on k.

Much more can be said about this game. Eg one can 'target' another player by adding 1 to your answer to c) and pointing at him. Strategies involving cooperation in this game are also probably of interest.

 

[Dedication_]

I'd hate to drink with you people. That is all.

 

[seanieg89]

I'd hate to drink with you people. That is all.

Lucky no-one is asking you to then.

 

[seanieg89]

Sorry in advance for the lack of rigour or proper terminology, I'm no mathematician. I'll try these one at a time.

a) Call the current 'it' player Goldy.

Because we're dealing with a functional graph, when k exceeds n, you're going to fall into a cycle. Let the length of this cycle be c, 2 ≤ c ≤ n (c ≠ 1 because the graph has no loops -- no one points to themselves).

• If this cycle does not involve Goldy, Goldy is guaranteed not to have to drink again, so he is safe!
• If this cycle does involve Goldy, Goldy needs to ensure that for any value of c, his choice of k will not result in him getting picked again, i.e. k ≠ 0 (mod c). That is, k cannot be a multiple of c, for any c in {2, 3, 4, ... n}. Goldy can find such a number by simply choosing k = n! + 1 -- since all potential values of c are factors of n!, none are factors of n! + 1. Because you relaxed the k constraint, this is a valid choice of k for any n that ensures he won't get picked.

Indeed this is correct, my choice was the first prime exceeding n but yours has the advantage of being constructive I guess .

For the record I never ended up solving c) when the restriction is in place. I don't know how difficult that part may be, but the rest is fairly straightforward.

 

[Blue Suede]

seanie come to the meat and this game will be played

 

[seanieg89]

seanie come to the meat and this game will be played

Drinking with bos people sounds tres fun, are onesies permitted/encouraged?