{"id":255,"date":"2006-06-20T17:57:37","date_gmt":"2006-06-20T06:57:37","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/2006\/06\/20\/unsolved-puzzle-algorithmic-thief-assignment\/"},"modified":"2006-06-20T17:57:37","modified_gmt":"2006-06-20T06:57:37","slug":"unsolved-puzzle-algorithmic-thief-assignment","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2006\/06\/20\/unsolved-puzzle-algorithmic-thief-assignment\/","title":{"rendered":"Unsolved Puzzle: Algorithmic Thief Assignment"},"content":{"rendered":"

I learnt a new Cheapass<\/a> card game recently. It was an interesting and thought-provoking game, but I am not going to talk about the game-play today. I am going to talk about the initial set-up, and an unsolved puzzle it brings up.<\/p>\n

Introduction to the Game Set-Up<\/h3>\n

Reverse-engineering the requirements, the game developers needed everyone to start with three equivalently-valued chips or tokens that are exchanged with other players thoughout the game. They also needed exactly one of the players to be secretly nominated with a special role (they arbitrarily call it the “Thief”). If the Thief spends their last chip, the game is over.<\/p>\n

The simplest solution to nominating the thief is to deal out a short deck of cards equal to the number of players (I think it works with four to nine players) and the person who receives the Joker takes on the Thief role.<\/p>\n

The game developers at Cheapass have optimised this slightly. <\/p>\n

Firstly, they use the Ace of Spades instead of the Joker – presumably because some decks don’t have Jokers.<\/p>\n

Secondly, they eschew chips, and instead deal three cards per player. The person with the Ace of Spades takes on the Thief role, and then the cards are used as chips. The thief should only spend the Ace of Spades as the last card (and hence end the game). If the card was given to another player in the middle of the game, the thief’s identity would be revealed, so it shouldn’t be done..<\/p>\n

The Problem<\/h3>\n

The downside to this system is that the thief can accidentally reveal themselves by being cautious about which cards that they exchange. Similarly, non-thieves can give away their status by being cavalier about which cards they use.<\/p>\n

Conventions Can Help<\/h3>\n

There are a couple of partial solutions that can be adopted by the players. <\/p>\n

The first is to enforce a strict rule that, once play starts, cards must remain face down. This system is subject to both accidental and malicious reveals.<\/p>\n

A similar method is a convention of how to place the thief card (always the leftmost card in your hand, or always the bottom of the pile on the table) and which card to spend (always the rightmost card in your hand or always the top card on the pile). In practice, the non-thieves forget to follow this convention strictly, even though it reduces the chances of both them and the thief that they will win.<\/p>\n

The Puzzle: An Algorithmic Solution?<\/h3>\n

Here’s the puzzle:<\/p>\n

Either come up with an function, f<\/code>, that satisfies the following requirements, or prove that such an function is impossible:<\/p>\n