1
$\begingroup$

From the game Cheat : https://en.wikipedia.org/wiki/Cheat_(game)

Assume that we have 13 cards from 1 to 13 and that we play with 4 players. Each player has at least 1 card and knows where are each of the 13 cards at every moment of the game (complete information).

The first play of the game must call 1; subsequent calls must be exactly one rank higher, with 13 being followed by 1 and continuing again. The player can't use a strategy they can only play their card or pick the cards that are on the table if they can't play.

The objective of the game is to be the first player to get rid of all their cards.

What is the longest possible game you can have (in term of turns) ?

$\endgroup$
  • $\begingroup$ Is the maximisation meant to be over all possible initial configurations (subject to the stated condition that each player has at least one card)? E.g. at the beginning three players might have one card each and one player might have $10$? And do the players follow a particular strategy, or is the maximisation also over all their possible moves? $\endgroup$ – joriki Jun 4 '16 at 23:16
  • $\begingroup$ Is the maximisation meant to be over all possible initial configurations (subject to the stated condition that each player has at least one card)? : Yes and it is not really a game, the player can't use a strategy they can only play their card or pick the cards that are on the table if they can't play $\endgroup$ – Ases Jun 4 '16 at 23:55
  • $\begingroup$ That information should be added to the question; it's not clear from the current phrasing whether someone will always call "cheat" when you lie. More generally, I'd suggest to rewrite the question such that the deterministic process that you're actually interested in is explicit and prominent; you can leave the back story about the game that you derived it from in there to add motivation and spice, but currently there's too much emphasis on it; all five paragraphs are about a game, which rather obscures the crucial aspect that "it's no really a game". $\endgroup$ – joriki Jun 5 '16 at 6:21
0
$\begingroup$

I don't see how to solve this without a computer. Since there are only

$$\sum_{k=0}^4(-1)^k\binom4k(4-k)^{13}=60780720$$

different initial configurations, they're easily checked by computer. Here's code that does so. The result is that the game can take up to $102$ turns, and there are $1537$ initial configurations that lead to this game length, so the probability for a uniformly randomly drawn configuration to lead to this game length is about $25$ in a million. These maximal initial configurations vary greatly, but there are some patterns. The $13$ is always on the last player's hand, and the positions of the higher cards are less variable than those of the lower cards. Only six different distributions of the top six cards occur:

9
12
8 10 11
13

----
9 12
8 10 11
13

----
9 10 12
8
11 13

9
12
8 10
11 13

----
9 12
8 10
11 13

9
10
8 11
12 13

Here's a random sample of maximal initial configurations:

1 3 9
2 4 5 12
7 8 10 11
6 13

3 9
1 12
5 7 8 10 11
2 4 6 13

7
1 9 12
2 5 6 8 10 11
3 4 13

1 4 5 7
6 9 10 12
2 8
3 11 13

1 3
4 9 10 12
5 8
2 6 7 11 13
$\endgroup$
  • $\begingroup$ Awesome, thanks ! $\endgroup$ – Ases Jun 5 '16 at 12:51
  • 1
    $\begingroup$ @joriki I was too slow to edit my message but you had the right interpretation : A would play 1, and then no-one could play up to the point when B plays 10. $\endgroup$ – Ases Jun 6 '16 at 19:58
  • 1
    $\begingroup$ @Ases, thank you for the clarification. Just to be certain, in joriki's third example, where A holds only the 7, do I now understand correctly that essentially nothing happens until D plays the 4? If so, then the rule can be stated as: On the $k$th turn, player $k$ mod $4$ must place card $k$ mod $13$ on the table if he possesses it (and thereby ending the game if doing so leaves him with an empty hand) or else pick up all the cards currently on the table. $\endgroup$ – Barry Cipra Jun 6 '16 at 20:13
  • 1
    $\begingroup$ @BarryCipra Yes, absolutely. You're right. $\endgroup$ – Ases Jun 6 '16 at 20:33
  • 1
    $\begingroup$ On further thought, and a bit of experimentation, it's clear that the (neverending) game can't cycle back to any starting position, because there are some positions from which the game cannot be "unplayed." I was misled by the fact that for four players and $13$ cards, if one player starts with all the cards, the game does cycle back. It also does so if you only have $5$ cards (and obviously cycles with only one card!). But it does not cycle with four players and only $3$ cards. There might be something interesting here, but it's fairly far from what the OP asked about. $\endgroup$ – Barry Cipra Jun 7 '16 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.