## Ladies and Gentlemen, Stan Wagon: TYI 32 – A Cake Problem.

The following post was kindly contributed by Stan Wagon. Stan (Wikipedea) is famous for his books, papers, snow-sculptures, and square-wheels bicycles (see picture below) !

A round cake has icing on the top but not the bottom. Cut out a piece in the usual shape
(a sector of a circle with vertex at the center), remove it, turn it upside down, and replace
it in the cake to restore roundness. Do the same with the next piece; i.e., take a piece
with the same vertex angle, but rotated counterclockwise from the first one so that one
boundary edge coincides with a boundary edge of the first piece. Remove it, turn it
upside-down, and replace it. Keep doing this in a counterclockwise direction. The figure
shows the situation after two steps when the central angle is 90°. If θ is the central angle
of the pieces, let f (θ) be the number of steps needed so that, under repeated cutting-andflipping just described, all icing returns to the top of the cake, with f (θ) set to ∞ if this
never happens. For example, f(90°) = 8.

### Test your intuition: What is f(181°)?

Source info:
The original source of this problem was Problem 31.2.8.3 in the 1968 Moscow Math Olympiad [L, p. 90] in a slightly different form. The variant given here is in [Winkler].

[L] 60-odd years of Moscow Mathematical Olympiads, G. Leites editor, G. Halperin, A Tolpygo, P Grozman A Shapovalov, V Prasolov, A Fomenko

[W] Mathematical Mind-Benders by Peter Winkler, published by AK Peters, Wellesley, Mass., 2007.

(see here)

This entry was posted in Combinatorics, Guest blogger, Test your intuition and tagged , , . Bookmark the permalink.

### 8 Responses to Ladies and Gentlemen, Stan Wagon: TYI 32 – A Cake Problem.

1. Dan Carmon says:

My first “intuitive” answer was none of the above – it was 720. The intuition being that, as in the f(90) case, in order for the icing to show up again the cuts will have to cover the entire cake an even, integral number of times (so that every 1 degree sub-slice is flipped an even number of times). This happens for the first time after the 720th iteration – the 180th iteration does not flip the sub-slices evenly, and the 360th iteration flips every part of the cake exactly 181 times, which is odd.

I almost certainly would have not realized this logic was flawed if it weren’t for the fact that 720 was not one of the available options! Realizing my error, I worked on the question more rigorously, and in the process all but one of the suggested answers seemed to me like very reasonable contenders for the correct answer — and of course, the one that seemed least reasonable during the process was the one that eventually turned out to be correct.

(Since this is about intuition rather than computation, though, my vote was for 360 as the nearest representative for 720.)

Very nice and surprising riddle!

2. S.G. says:

Studying some base cases, the answer seems infinity. As the recurrence for total flipped angle after every 4 moves remains odd .

3. Setup: Let $1\leq p< q$ be relatively prime (we will rotate the circle by $p/q$). Let $C=\left(\mathbb{Z}/q\mathbb{Z}\right)$ be the cyclic group, $V = \mathbb{F}_2^C$ and let $G = C\ltimes V$ where $C$ acts by translation. Let $\underline{v} \in V$ be the vector with $p$ ones follows by $q-p$ zeroes, and let $c\in C$ be any generator. We need to determine the order of $g=c\underline{v} \in G$.

Calculation: projecting to $G/V \cong C$ we see that the order of $g$ divides the order of $r$ which is $q$. We next compute the its powers: $g^2 = (c^2)(\underline{v}+c^{-1}\cdot \underline{v})$, $g^3 = (c^3)(\underline{v}+c^{-1}\cdot \underline{v} + c^{-2}\cdot \underline{v})$ etc where $\cdot$ is the action of $C$ on $V$. It follows that $g^q = \sum_{r\in C} r\cdot \underline{v}$. But for each standard basis vector $\underline{e}_i\in V$ we have $\sum_{r\in C} r\cdot \underline{e}_i = \underline{u}$ where $\underline{u}$ is the all-ones vector. It follows that $g^q = p \underline{u}$ (scalar multiplication in the vector space $V$) and $g^{2q} = (2p) \underline{u} = \underline{0}$.

Conclusion: The order of $g$ is $q$ if this $p$ is even and $2q$ otherwise.

In particular for $p/q = 181/360$ the order is $720$.

Remark: Note that the argument did not require that the rotation be at the same angle as the size of the wedge that is being reversed.

• A-ha: we don’t need the order of $g$ — we are considering the action of $G$ on $V$ and specifically want the first $k$ such that $g^k \in C=\mathrm{Stab}_G(\underline{0})$ (rotating the cake as a whole doesn’t change the fact that it is the right way up). But this would make $k$ a divisor of $720$ which does not divide $360$ (since after 360 steps the cake is flipped).

But this means $k$ is a multiple of $16$. So let’s compute small powers.
$g^2 = c^2 (\underline{v}+c^{-1}\underline{v}) = c^2 (\underline{u} + \underline{e}_0+\underline{e}_1)$ and $c^2$ is translation by $2$ if $c$ translates by $181$. Since $\underline{u}$ is $C$-invariant we get that $g^4 = c^4 (\underline{e}_0+\underline{e}_1+\underline{e}_2+\underline{e}_3)$. But then $g^{4m}$ flips the first $4m$ bits so before step $360$ some bits are flipped and some aren’t, and the answer is still $720$.

Can someone point out my mistake?

• Dan Carmon says:

Your model of how the cake is affected by flipping a piece of cake is inaccurate. It is not enough to consider the rotation of the cake (by the cyclic group) and whether each 1-degree piece is up or down. When a 181-degree piece of cake is flipped, it affects the relative order of the 1-degree pieces, breaking the previous cyclic order. This has to be taken into consideration. The ambient group is actually the semi-direct product of $S_q$ and $V$, a.k.a. the hyperoctahedral group $B_q$.

4. Stan Wagon says:

A nice variation/extension of the problem is: What is g(theta), where g is the number of steps to return the cake to its exact initial state? But the key is understanding f(theta) first.

5. I can’t help it: $f(181^\circ)=720$. – Apply a scale $[0..360]$ around the cake. At time $t=0$ the cake is white, and the knife is at the point $0$ on the scale, having just made the zeroth cut. Going through the motions one finds that after four steps the cake is again white, apart from the interval $[0,4]$, and the knife is at the point $4$, waiting to make the next cut $181$ units further on counterclockwise. It follows that after $90\cdot 4=360$ steps the knife is again at point $0$, but now the cake is totally black. After another $360$ steps the cake is again white. Counting the number of black unit intervals modulo $4$ it is easily seen that this state of affairs could not happen “by coincidence” at some earlier time.