Kazakhstan FAIO 2024 · Correction IOAI Training

E. Ray is behaving bad

Cette page donne toute la méthode. Lisez-la une fois que vous avez cherché.

Métrique: exact answer
Évaluée sur: written answers
Notre score: 0.08 = 2/25, verified 3 ways
Niveau attendu: the exact probability (hidden checker)

Niveau attendu atteint

Nous avons résolu l'épreuve nous-mêmes : téléchargé les données, mené les expériences et mesuré le score ci-dessous. L'énoncé et les données appartiennent à leurs organisateurs. Cette correction est rédigée en anglais.

The problem in brief

A space station has four floors. Floor 1 and floor 4 are single points; floors 2 and 3 are pentagons whose neighbouring corners are joined by stairs. The top point is joined to all five corners of floor 2, each corner of floor 3 receives two stairs from floor 2, and every corner of floor 3 is joined to the bottom point. Ray starts at the top and, every minute, walks down (or up, or sideways) one staircase chosen uniformly among those at his current vertex. What is the probability that he reaches floor 4 within 3 minutes? There is no input: the program just prints one number.

How you are scored

A single number, compared with the exact probability. Our answer, obtained three independent ways:

\boxed{0.08 = \tfrac{2}{25}}

First look at the structure

Before computing, count the stairs at each vertex:

the top point $P$ : 5 stairs (one per corner of floor 2);
a corner $A_i$ of floor 2: 1 (to $P$ ) + 2 (pentagon neighbours) + 2 (to floor 3) = 5;
a corner $B_i$ of floor 3: 2 (from floor 2) + 2 (pentagon neighbours) + 1 (to $Q$ ) = 5;
the bottom point $Q$ : 5.

Every vertex has exactly 5 stairs, there are 12 vertices and $12 \times 5 / 2 = 30$ stairs: this is the graph of an icosahedron, with $P$ and $Q$ as opposite poles. For the problem to be consistent, each $B_i$ must sit "between" two adjacent corners of floor 2 ( $B_i$ joined to $A_i$ and $A_{i+1}$ ), which is exactly how an icosahedron is built.

Layered drawing of the station. Every vertex has 5 stairs; the pentagons wrap around (dashed copies). The 10 shortest routes from P to Q are drawn in red.

The key idea

Ray cannot arrive earlier than minute 3, so "within 3 minutes" means "along a shortest route". The distance from $P$ to $Q$ is 3: one step to floor 2, one to floor 3, one to floor 4. Any detour (a sideways step, or a step back up) costs at least one extra minute. So the event is exactly "the first three steps go down, down, down".

Because every vertex has degree 5, every specific 3-step walk has probability $\left(\frac{1}{5}\right)^3 = \frac{1}{125}$ . It remains to count shortest routes:

5 choices of the corner $A_i$ on floor 2;
from $A_i$ , 2 stairs lead down to floor 3;
from that $B_j$ , 1 stair leads to $Q$ .

That is $5 \times 2 \times 1 = 10$ routes, hence

\Pr(\text{reach } Q \text{ within 3 minutes}) = \frac{10}{125} = \frac{2}{25} = 0.08 .

Equivalently, step by step: the first step always reaches floor 2 (probability 1), the second goes down with probability $2/5$ , the third with probability $1/5$ , and $1 \times \frac{2}{5} \times \frac{1}{5} = \frac{2}{25}$ . Multiplying conditional probabilities along the path is the chain rule of probability.

The full solution

solution.py builds the graph explicitly, asserts that every vertex has degree 5 and that there are 30 edges, then checks the answer three ways:

Path counting: enumerate all walks $P \to A_i \to B_j \to Q$ ; there are 10.
Exact Markov chain: propagate the probability distribution one minute at a time with fractions, making $Q$ absorbing so that the curve is the probability of having arrived by minute $t$ . It gives $0, 0, \frac{2}{25}, \frac{18}{125}, \frac{132}{625}, \dots$
Monte Carlo: 200 000 simulated walks give $0.0795 \pm 0.0012$ (95 % interval), which contains $0.08$ .

The core of the exact computation:

for _ in range(T):
    new = {u: F(0) for u in nodes}
    new[Q] = dist[Q]                       # arrived stays arrived
    for u in nodes:
        if u != Q:
            for v in nbr[u]:
                new[v] += dist[u] / 5      # uniform choice among 5 stairs
    dist = new

Exact probability of having reached floor 4 by minute t: zero for t = 1 and 2, then 0.08 at t = 3, rising towards 1 as the walk goes on.

The program to submit is one line: print(0.08).

Results

approach	value	verdict
counting the 10 shortest routes, $10/5^3$	0.08	correct
exact Markov chain with fractions	2/25	correct, agrees
Monte Carlo, 200 000 walks	$0.0795 \pm 0.0012$	agrees
forget that Ray can go up or sideways (only down)	1	wrong: ignores the uniform choice
stairs only go up/sideways, never back up ( $1 \cdot \frac{2}{4} \cdot \frac{1}{3}$ )	1/6	answers a different, directed version
count each $B_j$ once (5 routes instead of 10)	0.04	wrong: each $B_j$ is reached from 2 corners

What to remember

Draw the graph and count degrees first: here the uniform degree 5 makes every walk of length 3 equally likely, and the hidden icosahedron makes the structure obvious.
"Within $t$ steps" on a graph at distance exactly $t$ means "along a shortest path": count shortest paths, multiply by the probability of one path.
Chain rule of probability: multiply conditional probabilities step by step ( $1 \cdot \frac{2}{5} \cdot \frac{1}{5}$ ).
A random walk is a Markov chain: propagating a probability vector with the transition matrix gives exact answers for any horizon, the same mechanism behind PageRank and many sampling algorithms.
Check with a simulation and report its error bar: a Monte Carlo estimate with $N$ samples has standard error $\sqrt{p(1-p)/N}$ .

Code complet (solution.py)

"""FAIO 2024 (Kazakhstan) qualification, problem E "Ray is behaving bad".

Graph: top point P (floor 1), pentagon A0..A4 (floor 2), pentagon B0..B4
(floor 3), bottom point Q (floor 4). P-Ai for all i; Ai-A(i+1); Bi-B(i+1);
each Bi joined to two floor-2 vertices (Ai and A(i+1)); Bi-Q for all i.
Every vertex has degree 5: it is the graph of an icosahedron.
Ray walks uniformly at random along edges, one edge per minute, from P.
Question: probability that he reaches Q within 3 minutes.

Three independent computations: path counting, exact matrix powers with
fractions, Monte Carlo. Run:  python solution.py   (prints 0.08, draws figures)
"""
from fractions import Fraction as F
import random
import math
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

P, Q = "P", "Q"
A = [f"A{i}" for i in range(5)]
B = [f"B{i}" for i in range(5)]
edges = set()
def link(u, v): edges.add(frozenset((u, v)))
for i in range(5):
    link(P, A[i]); link(A[i], A[(i + 1) % 5])           # floor 1-2, pentagon 2
    link(B[i], B[(i + 1) % 5]); link(B[i], Q)           # pentagon 3, floor 3-4
    link(B[i], A[i]); link(B[i], A[(i + 1) % 5])        # each Bi gets two stairs from floor 2
nodes = [P] + A + B + [Q]
nbr = {u: sorted(v for e in edges if u in e for v in e if v != u) for u in nodes}
assert all(len(nbr[u]) == 5 for u in nodes) and len(edges) == 30   # icosahedron: 12 vertices, 30 edges

# ---------------------------------------------- 1. counting shortest paths
paths = [(P, a, b, Q) for a in A for b in nbr[a] if b in B]
p_paths = F(len(paths), 5 ** 3)
print("shortest paths P->Q:", len(paths), " probability", p_paths)

# ------------------------- 2. exact distribution, Q made absorbing (first hit)
def first_hit_curve(T):
    dist = {u: F(0) for u in nodes}; dist[P] = F(1)
    out = []
    for _ in range(T):
        new = {u: F(0) for u in nodes}
        new[Q] = dist[Q]                                   # once at Q, he has arrived
        for u in nodes:
            if u == Q or dist[u] == 0:
                continue
            for v in nbr[u]:
                new[v] += dist[u] / 5
        dist = new
        out.append(dist[Q])
    return out
curve = first_hit_curve(30)
print("P(reached Q by minute t):", [str(x) for x in curve[:5]])
assert curve[0] == curve[1] == 0 and curve[2] == p_paths == F(2, 25)

# ----------------------------------------------------------- 3. Monte Carlo
rng = random.Random(0)
N = 200_000
hits = 0
for _ in range(N):
    u = P
    for _ in range(3):
        u = rng.choice(nbr[u])
        if u == Q:
            hits += 1; break
p_mc = hits / N
se = math.sqrt(p_mc * (1 - p_mc) / N)
print(f"Monte Carlo: {p_mc:.4f} +- {1.96*se:.4f} (95 %)")

# variant: if stairs only went up or sideways (never down)
p_dir = F(1) * F(2, 4) * F(1, 3)
print("variant 'no going down':", p_dir, float(p_dir))
print("ANSWER:", float(p_paths))                         # 0.08

# ------------------------------------------------------------------ figures
plt.rcParams.update({"font.size": 12, "axes.spines.top": False, "axes.spines.right": False})
pos = {P: (0, 3), Q: (0, 0)}
for i in range(5):
    pos[A[i]] = (2.0 * (i - 2), 2)
    pos[B[i]] = (2.0 * (i - 2) + 1.0, 1)
fig, ax = plt.subplots(figsize=(11, 5), dpi=150)
on_path = {frozenset(p[k:k + 2]) for p in paths for k in range(3)}
ghost = {(A[4], A[0]): (6.0, 2), (B[4], A[0]): (6.0, 2), (B[0], B[4]): (-5.0, 1)}
for e in edges:                                            # pentagon wrap edges go to a ghost copy
    u, v = tuple(e)
    style = dict(color="#d1495b", lw=2.4) if e in on_path else dict(color="#c9d1d9", lw=1.3)
    key = next((k for k in ghost if frozenset(k) == e), None)
    if key:
        (x1, y1), (x2, y2) = pos[key[0]], ghost[key]
    else:
        (x1, y1), (x2, y2) = pos[u], pos[v]
    ax.plot([x1, x2], [y1, y2], zorder=1, **style)
for (a, g), (x, y) in ghost.items():
    ax.scatter([x], [y], s=520, color="white", edgecolor="#9aa5b1", lw=1.5, ls="--", zorder=3)
    ax.text(x, y, g, ha="center", va="center", fontsize=10, color="#9aa5b1", zorder=4)
ax.text(6.0, 2.45, "copy of A0", ha="center", fontsize=9, color="#9aa5b1")
ax.text(-5.0, 0.55, "copy of B4", ha="center", fontsize=9, color="#9aa5b1")
for u, (x, y) in pos.items():
    ax.scatter([x], [y], s=520, color="#2e86ab" if u in (P, Q) else "white",
               edgecolor="#2e86ab", lw=2, zorder=3)
    ax.text(x, y, u, ha="center", va="center", fontsize=10,
            color="white" if u in (P, Q) else "#1d3557", zorder=4)
for y, lab in [(3, "floor 1"), (2, "floor 2"), (1, "floor 3"), (0, "floor 4")]:
    ax.text(-6.3, y, lab, va="center", fontsize=11, color="#555")
ax.set_xlim(-6.8, 6.8); ax.set_ylim(-0.5, 3.5); ax.axis("off")
ax.set_title("Every vertex has 5 stairs; the 10 shortest routes P -> Q in red (each has probability 1/125)")
fig.tight_layout(); fig.savefig("figures/graph.png", facecolor="white")

fig, ax = plt.subplots(figsize=(9, 4.2), dpi=150)
ts = list(range(1, 31))
ax.step(ts, [float(c) for c in curve], where="post", color="#2e86ab", lw=2.2)
ax.scatter([3], [float(curve[2])], color="#d1495b", zorder=5, s=60)
ax.annotate("3 minutes: 2/25 = 0.08", (3, 0.08), xytext=(6, 0.25),
            arrowprops=dict(arrowstyle="->"), color="#d1495b")
ax.set_xlabel("minutes t"); ax.set_ylabel("P(Ray has reached floor 4 by t)")
ax.set_title("Exact first-arrival probability (floor 4 made absorbing)")
fig.tight_layout(); fig.savefig("figures/arrival.png", facecolor="white")
print("figures written")