13 chocolates and 1 chilli

Question

In a BBC documentary The Secret Rules of Modern Living: Algorithms, professor tells us about a game involving 13 chocolates and a chili. I understand the solution provided by the professor, however, I want to know how can I formulate it?

Basically to understand how are we solving this problem using math? Do we make an algebraic equation? Or is it a combinatorics problem? Or is it just "an algorithm"

Problem Thirteen candies and one hot pepper are placed into a jar. Two people play with the objective to avoid being stuck eating the chili pepper. Each person is allowed to take 1, 2, or 3 candies out of the jar at a time. Turns out the solution is to think mathematically, breaking down the thirteen candies into four even groups. There is a single candy leftover. To win, a person picks one candy first. They wait for their opponnent to pick 1, 2, or 3 candies. It doesn’t matter how many their opponent draws.

Solution As long as the person takes four candies minus how many their opponent took in their turns, they will win. Say the opponent picks three candies, so the person will take only one. In that round, a total of four candies are removed from the jar. This is the winning strategy. By far, this was my favorite segment of the documentary because now I know how to game the system and never have to stoop to eating a whole chili raw.

Found the summary of problem from here - http://dflee.io/the-secret-rules/

P.S. - I'm not sure whether this belongs to math stackexchange. However, I couldn't find any rule which I was voiding by posting here.

Answer 1

This problem belongs to a class that we might call "Nim-type" games and clearly falls under mathematics; e.g., combinatorial game theory. Read the Wikipedia link for more information, including a mathematical formulation. The underlying theory becomes much more interesting when we ask questions such as, for what sizes of the starting heap does the first player to move have a winning strategy? If the rules for the number of heaps and the type of moves are varied, under what circumstances can the first player (or second, or in general if there are any number of players) force a win?

Answer 2

You want to be the one to remove the last candy. No matter what your opponent does, you can make the sum of successive moves by hime and you equal to 4. So, if the number of candies is a multiple of $4$ the second player to move wins.

If you are the first player, realize that after you've move you'll be the second player, so you should leave a multiple of $4$. The way to do this is to divide the number of candies in the jar by $4$ and take the remainder. $12 =3\times 4 + 1,$ so the only winning move is to take $1$.

If you were allowed to take $1,3,\text{ or }5$ candies, and there were $20$ candies to begin with, you would see that you can always make the sum $6$, so the first player should take $2,$ leaving $18$.

Answer 3

I would not think about this problem as solving an equation or a combinatorics problem. I guess I would call it deductive logic and mathematical induction (which is not inductive logic.) Once you have the solution, you can say it is algorithmic to apply it. But, it is not algorithmic thinking to generate the solution.

If I encounter a problem like this, first step is to simplify the problem. What is the strategy if there is one candy in the jar? Easy, I take the one candy. 2,3 are similarly easy.

At 4 it becomes interesting. Clearly I am screwed.

At 5, if 4 screws me, then I know how to screw my opponent.

Once I appear to have a solution for the small and simple cases, does it generalize? Can I extrapolate? Yes, I can.

I am done, I have a strategy that will work so long as I don't start in the "screwed position," and even then I have a chance my opponent will make a mistake.

Answer 4

Figuring out the winning strategy takes some ingenuity that goes beyond pure math, but you can use math to prove that the strategy of taking one candy first, and taking $4$ minus the number of candies the opponent has taken after that, will indeed guarantee that your opponent will have to take the chili.

To prove this, we 'll prove by induction that for any $k$: if there are $4k$ candies left together with the one chili after your turn, then your opponent will end up with the chili, as long as you keep following the strategy.

Base: $k=0$ There are no more candies left, and it is your opponent's turn, so your opponent will have to get the chili

Step: Assume that there are $4(k+1)$ candies left, and it is your opponent's turn. Whether your opponent takes $1$, $2$, or $3$ candies, you will now take $4$ minus that number of candies, and so after your turn there will be $4k$ candies. By inductive hypothesis, this means that your oppponent will end up with the chili.