I was catching up with the latest Running Man and in this episode, they were using the Ghost Leg game to determine winners and punishments. Watching them play, I was intrigued by the Bijection relation of the diagram.

Background

What is the Ghost Leg game?

• The game begins with 2 sets of nodes, start and end. A straight line connects the each start node to the corresponding end node directly below them. Horizontal lines are added between the neighbouring vertical lines drawn initially. Afterwards, each node is traced downwards, taking the horizontal path whenever encountered. The goal is to see which end node it leads to. In the context of Running Man, typically the end nodes are predefined prizes or punishments while start nodes represent each member of the cast.

The 1:1 Property (Bijection Relation)

• Regardless of how many lines are drawn on the diagram, there is always a one-to-one correspondence between the start and end nodes. The lines only impact the particular mapping but does not infringe on the 1:1 property.
• In the variety program, this property allows them to assign prizes or punishments with the confidence of not having duplicates.

Proof

Intuitively the incremental nature of the game, that is, adding horizontal lines and changing number of nodes, makes me more inclined to use the inductive method.

1. Induction on number of horizontal lines
2. Generalise to 2+ nodes

Induction on Horizontal Lines

Proposition, for any Ghost Leg Diagram with 2 nodes (on each side) and $l$ horizontal lines, $P(l) =$ diagram with $l$ horizontal lines maintains the bijection relation between the start and end node.

Base Case $P(0)$ — 2 Nodes and 0 Horizontal lines

• In this case the trace is direct, each start node will lead to the end nodes directly under them. Hence, $P(l)$ is true

Base Case $P(1)$ — 2 Nodes and 1 Horizontal line

• When there is a single horizontal line, we expect each node to cross over and never come back. This essentially imply that the start nodes swapped ending positions. Hence, $P(l)$ is true

Induction Step

• for some K that is true, prove k+1

[Induction Hypothesis] Suppose for some $k$, $P(k)$ is true, that is, for any Ghost Leg Diagram with 2 Nodes and $k$ horizontal line there is a bijection relation between start and end nodes.

[Induction Step] Since $P(k)$ is true. We can re-imagine the diagram without the $k$ horizontal lines. Regardless of what $k$ is, the diagram will be equivalent to this new diagram in terms of mapping.

We can see that regardless of the state $P(k)$ is in, adding a line merely swaps the position of the start nodes — maintaining a 1:1 relation between the start and end

$\therefore$ $P(l)$ is true for any $l$ where $l \geq 0$

Generalising to 2+ Nodes

Let’s name the conclusion of the Horizontal Line induction: Lemma GLHL. For this section we will employ induction proof as well, induction over number of nodes in a ghost leg diagram.

Proposition, for any Ghost Leg Diagram with $n$ nodes (on each side), $G(n)$ = diagram with $n$ nodes maintains bijection relation between start and end nodes.

Base Case $G(0), G(1)$ — diagrams with 0 or 1 nodes, these are invalid / true by default

Base Case $G(2)$ — leveraging Lemma GLHL we can also claim this to be true

[Induction Hypothesis] Suppose for some $k$, $G(k)$ is true, that is, for any ghost leg diagram with $k$ nodes the bijection relation is maintained

[Induction Step] Let’s try to add a node to form a $G(k+1)$ diagram. Since $G(k)$ is true we can assume that at any point of the path there is one exact start node when on the $k^{\text{th}}$ node — a $K'$ identity.

• Simplify into Lemma GLHL

$\therefore$ $G(n)$ is true for any $n$ where $n \geq 0$

Conclusion

In essence, the actions in the game are non-destructive to the bijection property. The many nodes and lines obscures the simplistic structure underneath. Although the conclusion that the game has a 1:1 property was never in question, proving it gives us an insight on the basic mechanics of the game. Perhaps it will give you an advantage if it ever comes up.

Side note, while pushing this article I had to setup Math rendering for MDX. I had initially thought it was built into MDX. As a big notion user, I’m used to having latex rendering built-in so I used it a lot while writing this, I didn’t want to rewrite them so it was easier to just install some packages (is this tech debt!?). I do foresee that I’ll be using math expressions again so this is probably for the better.