Permutations & Combinations
Shortest path in 3D grid
Grade 11
Question:
<p>Number of shortest ways in which we can reach from the point \((0, 0, 0)\) to point \((3, 7, 11)\) in space where the movement is possible only along the <i>x</i>-axis, <i>y</i>-axis, and <i>z</i>-axis or parallel to them and change of axes is permitted only at integral points (an integral point is one which has its coordinate as integer) is</p>
<p>equivalent to number of ways of dividing 21 different objects in three groups of size 3, 7, 11</p>
<p>equivalent to coefficient of \(y^3 z^7\) in the expansion of \((1 + y + z)^{21}\)</p>
<p>equivalent to number of ways of distributing 21 different objects in three boxes of size 3, 7, 11</p>
<p>equivalent to number of ways of arranging 21 objects of which 3 are alike of one kind, 7 are alike of second type, and 11 are alike of third type</p>
Step-by-Step Solution
Key Concept: The shortest paths require exactly 3 steps right, 7 steps up, and 11 steps forward (total 21 moves). The number of ways equals the multinomial coefficient counting arrangements of these moves: 21!/(3!×7!×11!)
<p><strong>Step 1: Identify the constraint for shortest paths</strong></p><p>To go from (0,0,0) to (3,7,11) using only axis-parallel moves, we must move:</p><ul><li>3 units along x-axis (right)</li><li>7 units along y-axis (up)</li><li>11 units along z-axis (forward)</li></ul><p>Total moves required = 3 + 7 + 11 = 21 moves</p><p><strong>Step 2: Count the arrangements</strong></p><p>Each shortest path is uniquely determined by the order in which we make these moves. We need to arrange:</p><ul><li>3 R's (right moves)</li><li>7 U's (up moves)</li><li>11 F's (forward moves)</li></ul><p>among 21 total positions.</p><p><strong>Step 3: Apply multinomial coefficient</strong></p><p>Number of shortest paths = $\frac{21!}{3! \times 7! \times 11!}$</p><p>This equals: $\binom{21}{3} \times \binom{18}{7} \times \binom{11}{11}$ = $\binom{21}{3,7,11}$</p><p><strong>Step 4: Calculate</strong></p><p>$\frac{21!}{3! \times 7! \times 11!} = \frac{21 \times 20 \times 19 \times 18!}{6 \times 5040 \times 39916800}$</p><p>= 116,396,280</p><p>∴ Answer: <strong>ACD</strong> (assuming options match standard forms of this multinomial coefficient)</p>
Correct Answer: ACD