uniolympiads English

IMC 2018, Ημέρα 2, Θέμα 8

Let Ω={(x,y,z)∈Z3:y+1≥x≥y≥z≥0}\Omega = \{(x, y, z) \in \mathbb{Z}^3 : y + 1 \ge x \ge y \ge z \ge 0\}. A frog moves along the points of Ω\Omega by jumps of length 11. For every positive integer nn, determine the number of paths the frog can take to reach (n,n,n)(n, n, n) starting from (0,0,0)(0, 0, 0) in exactly 3n3n jumps.

Πρωτότυπο από το επίσημο PDFLet Ω = {(x, y, z) ∈ Z 3 : y + 1 ≥ x ≥ y ≥ z ≥ 0} . A frog moves along the points of Ω by jumps of length 1 . For every positive integer n , determine the number of paths the frog can take to reach (n, n, n) starting from (0, 0, 0) in exactly 3n jumps. Problem 8.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(Proposed by Fedor Petrov and Anatoly Vershik, St. Petersburg State University)

Solution. Let Ψ={(u,v)∈Z3:v≥0,u≥2v}\Psi = \{(u,v) \in \mathbb{Z}^3 : v \ge 0, u \ge 2v\}. Notice that the map π:Ω→Ψ\pi : \Omega \to \Psi, π(x,y,z)=(x+y,z)\pi(x,y,z) = (x+y,z) is a bijection between the two sets; moreover π\pi projects all allowed paths of the frogs to paths inside the set Ψ\Psi, using only unit jump vectors. Hence, we are interested in the number of paths from π(0,0,0)=(0,0)\pi(0,0,0) = (0,0) to π(n,n,n)=(2n,n)\pi(n,n,n) = (2n,n) in the set Ψ\Psi, using only jumps (1,0)(1,0) and (0,1)(0,1).

For every lattice point (u,v)∈Ψ(u,v) \in \Psi, let f(u,v)f(u,v) be the number of paths from (0,0)(0,0) to (u,v)(u,v) in Ψ\Psi with u+vu+v jumps. Evidently we have f(0,0)=1f(0,0) = 1. Extend this definition to the points with v=−1v = -1 and 2v=u+12v = u+1 by setting

f(u,−1)=0,f(2v−1,v)=0.(3)f(u,-1) = 0, \quad f(2v-1,v) = 0. \tag{3}
To any point (u,v)(u,v) of Ψ\Psi other than the origin, the path can come either from (u−1,v)(u-1,v) or from (u,v−1)(u,v-1), so
f(u,v)=f(u−1,v)+f(u,v−1)for (u,v)∈Ψ∖{(0,0)}.(4)f(u,v) = f(u-1,v) + f(u,v-1) \quad \text{for } (u,v) \in \Psi \setminus \{(0,0)\}. \tag{4}
If we ignore the boundary condition (3), there is a wide family of functions that satisfy (4); namely, for every integer cc, (u,v)↦(u+vv+c)(u,v) \mapsto \binom{u+v}{v+c} is such a function, with defining this binomial coefficient to be 00 if v+cv+c is negative or greater than u+vu+v.

Along the line 2v=u+12v = u+1 we have (u+vv)=(3v−1v)=2(3v−1v−1)=2(u+vv−1)\binom{u+v}{v} = \binom{3v-1}{v} = 2\binom{3v-1}{v-1} = 2\binom{u+v}{v-1}. Hence, the function

f∗(u,v)=(u+vv)−2(u+vv−1)f^*(u,v) = \binom{u+v}{v} - 2\binom{u+v}{v-1}
satisfies (3), (4) and f(0,0)=1f(0,0) = 1. These properties uniquely define the function ff, so f=f∗f = f^*.

In particular, the number of paths of the frog from (0,0,0)(0,0,0) to (n,n,n)(n,n,n) is

f(π(n,n,n))=f(2n,n)=(3nn)−2(3nn−1)=(3nn)2n+1.f(\pi(n,n,n)) = f(2n,n) = \binom{3n}{n} - 2\binom{3n}{n-1} = \frac{\binom{3n}{n}}{2n+1}.

Remark. There exist direct proofs for the formula (3nn)/(2n+1)\binom{3n}{n}/(2n+1). For instance, we can replicate the well-known proof of the formula for the Catalan numbers using the Cycle Lemma of Dvoretzky and Motzkin (related to the petrol station replenishment problem). See https://en.wikipedia.org/wiki/Catalan_number#Sixth_proof

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;