Detailed mathematical approach

Problem Summary

We are given \(n\) people together with two pairing rules: one for beds and one for desks. Each rule is an involution, so every person is either paired with exactly one other person or left fixed by that rule. The task is to count, modulo

$P=999{,}999{,}937,$

how many relabelings of the people preserve both structures simultaneously.

Mathematical Approach

The solution treats the data as a finite colored graph built from two involutions, then counts its structure-preserving permutations by decomposing the graph into connected components and grouping isomorphic components together.

Step 1: Model the Two Pairings as Involutions

Let \(V=\{1,2,\dots,n\}\). Write the bed relation as \(\beta:V\to V\) and the desk relation as \(\delta:V\to V\). Because each relation is an involution, we have

$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{for every } i\in V.$

A relabeling is a permutation \(\pi\) of \(V\). It is valid exactly when it preserves both relations, which means

$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{for every } i\in V.$

So the problem is to count all permutations that commute with both involutions.

Step 2: Turn the Data into a Two-Colored Graph

Connect each vertex \(i\) to \(\beta(i)\) by a bed edge and to \(\delta(i)\) by a desk edge. Fixed points are allowed, so a vertex can carry a loop of one color. Every vertex therefore has exactly one incident bed edge and exactly one incident desk edge, counting loops.

Now split this colored graph into connected components. If a permutation preserves both colored edge relations, it must send each connected component to another connected component with exactly the same colored structure. Therefore the global counting problem breaks into independent pieces indexed by component isomorphism classes.

Step 3: Count Isomorphisms by Choosing One Root Image

Take one component \(C\) of size \(m\) and relabel its vertices locally as \(0,1,\dots,m-1\). Record two local partner tables: one table gives the bed partner of each local index, and the other gives the desk partner. This removes the original labels and keeps only the structure.

If \(f:C\to C'\) is a color-preserving bijection between two components, then it must satisfy

$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x))$

for every local vertex \(x\), where \(p_C\) and \(q_C\) denote the local bed and desk partner tables. Because the component is connected and each vertex has exactly one neighbor of each color, once the image of one starting vertex is chosen, these equations force the image of every reachable vertex. Either the propagation stays consistent and yields one isomorphism, or it produces a contradiction and fails.

A necessary first check is that the chosen starting vertices have the same loop pattern:

$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$

Trying all possible starting images \(s\) therefore counts all isomorphisms from \(C\) to \(C'\).

Step 4: Automorphisms Determine All Isomorphism Counts Inside One Class

For a component \(C\), let

$a(C)=\left|\operatorname{Aut}(C)\right|,$

the number of color-preserving automorphisms of \(C\). This is exactly the number obtained when the implementation compares a component with itself.

If \(C\) and \(C'\) are isomorphic, then the number of isomorphisms \(C\to C'\) is also \(a(C)\). The reason is simple: choose one fixed isomorphism \(\varphi:C\to C'\). Then every other isomorphism \(C\to C'\) is uniquely of the form \(\varphi\circ \sigma\) with \(\sigma\in \operatorname{Aut}(C)\).

Step 5: Multiply the Contributions of Repeated Component Types

Suppose an isomorphism class appears \(m_j\) times, and let \(a_j\) be the automorphism count of one representative component in that class. A valid global permutation can first permute those \(m_j\) copies among themselves in

$m_j!$

ways. After the target copy of each source component is chosen, there are

$a_j$

color-preserving bijections for that source-to-target move. Since this choice is made independently for all \(m_j\) copies, the class contributes

$a_j^{m_j}\cdot m_j!.$

If the graph has isomorphism classes \(\mathcal{C}_1,\dots,\mathcal{C}_t\), the final formula is

$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$

Worked Example

Consider \(n=4\), with bed pairing \(2\leftrightarrow 3\) and desk pairings \(1\leftrightarrow 3\), \(2\leftrightarrow 4\). The bed relation fixes \(1\) and \(4\), so those two vertices carry bed loops. The whole structure is one connected component, and its colored shape is an alternating path

$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4$

with bed loops at the two ends. There are exactly two automorphisms: the identity, and the reversal that swaps the two ends and the two middle vertices while preserving edge colors. Hence the answer is

$2,$

which matches the implementation checkpoint for this small case.

How the Code Works

The C++, Python, and Java implementations begin by storing both involutions as tables on \(1,\dots,n\), with fixed points filled in automatically for any person not listed in a pair. They then traverse the graph with an explicit stack, following both colored relations, to extract every connected component.

Each component is relabeled locally so that it can be compared without referring to the original global labels. To compare two components, the implementation tries every possible image of the first local vertex whose loop pattern matches. For each candidate, it propagates the bed and desk constraints through the entire component. A contradiction rejects that candidate; a complete consistent propagation counts as one isomorphism.

After grouping components into isomorphism classes, the implementation computes the modular product

$a_j^{m_j}\cdot m_j! \pmod{P}$

for every class, using fast modular exponentiation for the power term and ordinary modular multiplication for the factorial term. No search over all \(n!\) permutations is ever attempted.

Complexity Analysis

Building the two involution tables and extracting all connected components costs \(O(n)\) time and \(O(n)\) memory. If two components have size \(s\), then testing isomorphism between them tries up to \(s\) starting images, and each successful or failed propagation touches at most \(s\) local vertices, so one comparison is \(O(s^2)\) in the worst case.

If the component sizes are \(s_1,\dots,s_r\), the grouping stage is therefore bounded by the pairwise same-size comparisons performed by the simple implementation; for the actual \(n=500\) instance this is easily fast enough. The overall memory use remains linear in \(n\).

Footnotes and References

1. Problem page: Project Euler 673 - Beds and Desks
2. Involution: Wikipedia - Involution (mathematics)
3. Connected component: Wikipedia - Connected component
4. Graph automorphism: Wikipedia - Graph automorphism
5. Graph isomorphism: Wikipedia - Graph isomorphism
6. Wreath product: Wikipedia - Wreath product