Spinning switches on a wreath product Peter Kagey October 19 2022

2025-05-03 0 0 500.88KB 27 页 10玖币

侵权投诉

Spinning switches on a wreath product

Peter Kagey

October 19, 2022

Abstract

In this paper, we attempt to classify an algebraic phenomenon on

wreath products that can be seen as coming from a family of puzzles

about switches on the corners of a spinning table. Such puzzles have

been written about and generalized since they were ﬁrst popularized by

Martin Gardner in 1979. In this paper, we provide perhaps the fullest

generalization yet, modeling both the switches and the spinning table as

arbitrary ﬁnite groups combined via a wreath product. We classify large

families of wreath products depending on whether or not they correspond

to a solvable puzzle, completely classifying the puzzle in the case when

the switches behave like abelian groups, constructing winning strategies

for all wreath product that are p-groups, and providing novel examples for

other puzzles where the switches behave like nonabelian groups, including

the puzzle consisting of two interchangeable copies of the monster group

M. Lastly, we provide a number of open questions and conjectures, and

provide other suggestions of how to generalize some of these ideas further.

1 Overview and preliminaries

This paper is organized into six sections. This section, Section 1 provides a

brief history of this genre of puzzles and introduces some of the ﬁrst approaches

to generalizing the puzzle further. Section 2 models these generalizations in

the context of the wreath product, and formalizes the notation of puzzles being

solvable. Section 3 explores situations where the puzzle does not have a winning

strategy, and provides reductions that allow us to prove that entire families of

puzzles are not solvable. Section 4 constructs a strategy for switches that behave

like p-groups, and gives us ways of building strategies from smaller parts. Section

5 provides novel examples of puzzles that do not behave like p-groups, but still

have winning strategies. Lastly, Section 6 provides further generalizations, and

contains dozens of conjectures, open questions, and further directions.

1.1 History

Generalized spinning switches puzzles are a family of closely related puzzles

that were ﬁrst popularized by Martin Gardner in a puzzle called “The Rotating

arXiv:2210.09408v1 [math.CO] 17 Oct 2022

Table” in the February 1979 edition of his column “Mathematical Games” [2].

Gardner writes that he learned of the puzzle from Robert Tappay of Toronto

who “believes it comes from the U.S.S.R.,” a history that is not especially

forthcoming.

My preferred version of the puzzle appears in Peter Winkler’s 2004 book

Mathematical Puzzles A Connoisseur’s Collection [16]

Four identical, unlabeled switches are wired in series to a light bulb.

The switches are simple buttons whose state cannot be directly ob-

served, but can be changed by pushing; they are mounted on the

corners of a rotatable square. At any point, you may push, simulta-

neously, any subset of the buttons, but then an adversary spins the

square. Show that there is a deterministic algorithm that will enable

you to turn on the bulb in at most some ﬁxed number of steps.

(Winkler’s version will be a working example in many parts of this paper,

so it is worth keeping in mind. An illustration can be found in Figure 1.)

Over the last three decades, various authors have considered generalizations

of this puzzle. Here, we build on those results and go further. The ﬁrst place

authors looked to generalize was suggested by Gardner himself. In his March

1979 column the following month, he provided the answer to the original puzzle

and wrote

The problem can also be generalized by replacing glasses with objects

that have more than two positions. Hence the rotating table leads

into deep combinatorial questions that as far as I know have not yet

been explored. [3]

In 1993, Bar Yehuda, Etzion, and Moran [17]. took on the challenge and

developed a theory of the spinning switches puzzle where the switches behave

like roulettes with a single “on” state. In this paper we take Gardner’s charge to

its logical conclusion and consider switches that behave like arbitrary “objects

that have more than two positions”.

Another generalization of this puzzle could look at other ways of “spinning”

the switches. In 1995, Ehrenborg and Skinner [1] did this in a puzzle they

call ”Blind Bartender with Boxing Gloves”, that analyzed this puzzle while

allowing the adversary to use an arbitrary, faithful group action to “scramble”

the switches. We analyze our generalized switches within this same context.

This puzzle was re-popularized in 2019 when it appeared in “The Riddler”

column from the publication FiveThirtyEight [11]. Shortly after this, in 2022,

Yuri Rabinovich synthesized Bar Yehuda and Ehrenborg’s results in a paper

that modeled the collection of switches as a vector space over a ﬁnite ﬁeld, and

modeled the “spinning” or “scrambling” as a faithful, linear group action on

this vector space.

For more background, see Sidana’s [13] detailed overview of the history of

this and related problems.

Figure 1: An illustration of Winkler’s Spinning Switches puzzle and a two-switch

analog.

1.2 A solution to Winkler’s Spinning Switches puzzle

We will start by discussing the solution to Winkler’s version of the puzzle be-

cause the solution provides some insights and intuition for the techniques that

we use later. Before solving the four-switch version of the puzzle, we will make

Peter Winkler proud by beginning with a simpler, two-switch version.

Example 1. Suppose that we have two identical unlabeled switches on opposite

corners of a square table, as in Figure 1

Then we have a three-step solution for solving the problem. We start by

toggling both switches simultaneously, and allow the adversary to spin the table.

If this does not turn on the light, this means that the switches were (and still)

are in diﬀerent states.

Next, we toggle one of the two switches to ensure that the switches are both

in the same state. If the light has not turned on, both must be in the oﬀ state.

The adversary spins the table once more, but to no avail. We know both

switches are in the oﬀ state, so we toggle them both simultaneously, turning on

the lightbulb.

In order to bootstrap the two-switch solution into a four-switch solution, we

must notice two things:

1. First, if we can get two switches along each diagonal into the same state

respectively, then we can solve the puzzle by toggling both diagonals (all

four switches), followed by both switches in a single diagonal, and lastly

both diagonals again. In this (sub-)strategy, toggling both switches along a

diagonal is equivalent to toggling a single switch in the two-switch analog.

2. Second, we can get both diagonals into the same state at some point by

toggling a switch from each diagonal (two switches on any side of the

square), followed by a single switch from one diagonal, followed by again

toggling a switch from each diagonal.

We will interleave these strategies in a particular way, following the notation

of Rabinovich [10].

Deﬁnition 2. Given two sequences A={ai}N

i=1 and B={bi}M

i=1, we can

deﬁne the interleave operation as

A~B= (A, b1, A, b2, A, . . . , bM, A) (1)

= (a1, . . . , aN

| {z }

, b1, a1, . . . , aN

| {z }

, b2, a1, . . . , aN

| {z }

, . . . , bM, a1, . . . , aN

| {z }

).(2)

which has length (M+ 1)N+M=MN +M+N.

Typically it is useful to interleave two strategies when Asolves the puzzle

given that the switches are in a particular state, and Bgets the switches into

that particular state. We also need Anot to “interrupt” what Bis doing. In

the problem of four switches on a square table, Bwill ensure that the switches

are in the same state within each diagonal, and Awill turn on the light when

that is the case. Moreover, Adoes not change the state within either diagonal.

Proposition 3. There exists a ﬁfteen-move strategy that guarantees that the

light in Winkler’s puzzle turns on.

Proof. We begin by formalizing the two strategies. We will say that the ﬁrst

strategy S1where we toggle the two switches in a diagonal together will consist

of the following three moves:

1. Switch all of the bulbs (A).

2. Switch the diagonal consisting of the upper-left and lower-right bulbs (D).

3. Switch all of the bulbs (A).

We will say that the second strategy S2where we get the two switches within

each diagonal into the same state consists of the following three moves:

1. Switch both switches on the left side (S).

2. Switch one switch (1).

3. Switch both switches on the left side (S).

Then the 15 move strategy is

S1~S2= (A, D, A, S, A, D, A, 1, A, D, A, S, A, D, A) (3)

We will generalize this construction in Theorem 21, which oﬀers a formal

proof that this strategy works.

(It is worth brieﬂy noting that S1~S2is the fourth Zimin word (also called

asequipower ), an idea that comes up in the study of combinatorics on words.)

1.3 Generalizing switches

Two kinds of switches are considered by Bar Yehuda, Etzion, and Moran in

1993 [17]: switches with a single “on” position that behave like n-state roulettes

(Zn) and switches that behave like the ﬁnite ﬁeld Fq, both on a rotating k-gonal

table. We generalize this notion further by considering switches that behave like

arbitrary ﬁnite groups.

Example 4. In Figure 2, we provide a schematic for a switch that behaves like

the symmetric group S3. It consists of three identical-looking parts that need to

be arranged in a particular order in order for the switch to be on.

We could also construct a switch that behaves like the dihedral group of the

square, D8. This switch might look like a ﬂat, square prism that can slot into a

square hole, such that only one of the |D8|= 8 rotations of the prism completes

the circuit.

Note 5. One subtlety of using a group Gto model a switch is that both the

“internal state” of a switch itself and the set of “moves” or changes are modeled

by G. Therefore it may be useful to think of the state as the underlying set of

Gwhere the moves act via a right group action of Gon itself.

The reason that it is appropriate to use a group to model a switch is because

groups have many of the properties we would expect in a desirable switch.

Note 6. The axioms for a group (G, ·)closely follow what we would expect from

a switch.

1. (Closure) The group (G, ·) is equipped with a binary operation, ·:G×G→

G. That is, for all pairs of elements g1, g2∈Gtheir product is in G

g1·g2∈G. (4)

In the context of switches, this means that if the switch is in some state

g1∈Gand the puzzle-solver applies the move g2∈Gto it, then the

resulting state g1·g2∈Gis in the set of possible states.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SpinningswitchesonawreathproductPeterKageyOctober19,2022AbstractInthispaper,weattempttoclassifyanalgebraicphenomenononwreathproductsthatcanbeseenascomingfromafamilyofpuzzlesaboutswitchesonthecornersofaspinningtable.SuchpuzzleshavebeenwrittenaboutandgeneralizedsincetheywererstpopularizedbyMartinGard...

展开>> 收起<<

Spinning switches on a wreath product Peter Kagey October 19 2022.pdf

共27页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Spinning switches on a wreath product Peter Kagey October 19 2022

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: