返回题库

纠结!

Tangled!

专题
Probability / 概率
难度
L7

题目详情

在 Terniquaternaria 度假时,Decimus 体验到了 该国的传统民俗舞蹈,他们称之为“打哈欠”。 Terniquaternaria 的人们以自己的理性为荣,所以 他们按照以下严格的规则跳哈欠鱼。四位舞者 握住两根长绳子的一端,决不松手。他们 最初采取以下立场:

`AD _________/


/
公元前 `

整个舞蹈过程中,只允许两种动作:

  • 整个团体逆时针旋转90度(即舞者 A 中的舞者移至 B,B 中的舞者移至 C,等等)。这一步称为 “旋转”(R)。

  • C 和 D 的舞者交换位置,D 握住绳子,而 C 正从下面经过。此步骤称为“交换”(S)。

从初始配置开始,舞蹈大师连续喊出 R/S随机舞步,伴舞者孜孜不倦地执行 音乐。在此之后,通常会有相当混乱的绳索 中间!

然后人群中的参与者可以向前迈出一步并尝试 通过喊出一系列相同的两个动作来解开绳索 上面是舞者执行的。如果这个人完全成功 解开绳索,他/她加冕为当天的国王/王后!

Decimus 仔细记录了由 舞者:

SRSRRSSRSRSSRSSRRSSRSSSSSSRSSRSSRSRS

SRSSRSSSSSSSSRSSRSSSSSSRSSRSSRRSSRSSRSS

SSSRSSRSSRSSSSSSSSSSSSSSSSSSRSSRSSRS

他真的很想成为国王,无论有多少研究 可能需要。什么顺序可以解开绳索?

**2020-09-09更新:**事实证明,哈欠舞者的舞步有限 耐力,并且更喜欢较短的解开顺序 对更长的命令。因此,我们将保持我们的领先地位 求解器排行榜按解决方案中的命令数量排名, 求解器的最短正确解位于顶部。任意 已经提交的求解者可以根据需要重新提交 记录他们最有效的解绳动作!

While on vacation in Terniquaternaria, Decimus got to experience the country’s traditional folkloric dance, which they call the “Yawn-ock”. The people of Terniquaternaria pride themselves on being rational, so they dance the Yawn-ock by the following strict rules. Four dancers hold one end of two long pieces of rope and never let go. They initially take the following positions:

A           D
 \_________/
  _________
 /          \
B            C


During the entire dance, only two types of move are allowed:

  • The entire group rotates 90 degrees counterclockwise (ie the dancer in A moves to B, dancer in B moves to C, etc). This step is called a “Rotate” (R).
  • Dancers in C and D swap places, with D holding the rope up while C is passing under. This step is called a “Swap” (S).

From the initial configuration, a dance master calls out successive R/S steps randomly, that the dancers diligently execute accompanied by music. After this, there is usually quite a tangled mess of rope in the middle!

A participant from the crowd can then step forward and attempt to untangle the ropes by shouting a sequence of the same two moves as above, that the dancers execute. If this person succeeds in fully untangling the ropes, he/she gets crowned King/Queen for the day!

Decimus took careful note of the sequence of moves executed by the dancers:

SRSRRSSRSRSSRSSRRSSRSSSSSRSSRSSRSRS
SRSSRSSSSSSSSRSSRSSSSSRSSRSSRRSSRSS
SSSRSSRSSRSSSSSSSSSSSSSSSSSRSSRSSRS

He would really like to become King, no matter how much research it might take. What sequence would untangle the ropes?

2020-09-09 update: Turns out the Yawn-ock dancers have a limited amount of endurance, and prefer a shorter sequence of untangling commands over a longer one. As such we will keep the top of our leaderboard of solvers ranked by number of commands in the solution, with the solver with the shortest correct solution at the top. Any solvers that have already submitted can re-submit if they’d like to record their most efficient untying maneuver!

解析

我们发现,解开绳索的最快序列是这个由 114 个命令组成的美丽序列:

RSSSSRSSRSSRSSRSSRSSRSSRSSRSSRSSRSSRSSRSSRSS

RSSRSSRSSRSSSSSSRSSRSSRSSSSRSSRSSSSRSSRS

SRSSSSRSSRSSRSSRSSRSSRSSSSRSSRSSRSSRSSRSS

它可以通过使用有理缠结理论来发现, 使用以下命令将这些命令缠结的绳子映射到有理数上 连分数。已故的约翰·H·康威 (John H. Conway) 以数学谜题闻名 为此,我们给舞蹈取了一个愚蠢的名字“Yawn-ock” (“Conway”向后隐藏)。

以下是这个棘手挑战的解决者,其中第一组是 具有最短的解决方案并订购第二组 按时间顺序排列。


Original Explanation

The fastest sequence of untangling the ropes that was found was this 114-command beauty:

RSSSSRSSRSSRSSRSSRSSRSSRSSRSSRSSRSSRSS
RSSRSSRSSRSSSSSRSSRSSRSSSRSSRSSSSRSSRS
SRSSSSRSSRSSRSSRSSRSSRSSSRSSSRSSRSSRSS

It could be discovered by using the theory of rational tangles, which maps ropes tangled by these commands onto rational numbers using continued fractions. The late John H. Conway of puzzle math fame worked on this, hence our silly name for the dance “Yawn-ock” (“Conway” is hidden in there backwards).

Here are the solvers of this tangly challenge, with the first group having the shortest solutions and the second group being ordered chronologically.