Dividing a rod

Probability Level 4

A rod is marked at random in 4 points and divided at those points.

If the chance that none of the parts shall be greater than 1 4 \frac{1}{4} of the rod can be expressed as a b \frac ab where a a and b b are coprime positive integers, then find the value of b 4 a \frac{b}{4a} .

Bonus : Generalize this for n n points.

Try my set .


The answer is 64.000.

Vishwak Srinivasan by Vishwak Srinivasan , 24, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Aug 12, 2016

Assume that the rod has length 1 1 . If the rod is divided at n n points, the lengths of the n + 1 n+1 sections so formed belong to the n n -dimensional simplex Δ n + 1 = { x = ( x 1 , x 2 , … , x n + 1 ) ∣ x 1 , x 2 , … , x n + 1 ≥ 0 , x 1 + x 2 + ⋯ + x n + 1 = 1 } \Delta_{n+1} \; = \; \big\{ \mathbf{x} = (x_1,x_2,\ldots,x_{n+1}) \; \big| \; x_1,x_2,\ldots,x_{n+1} \ge 0\,,\,x_1 + x_2 + \cdots + x_{n+1} = 1\big\} If we define D j = { x ∈ Δ n + 1 ∣ x j ≥ 1 4 } 1 ≤ j ≤ n + 1 D_j \; = \; \big\{ \mathbf{x} \in \Delta_{n+1} \, \big| x_j \ge \tfrac14\big\} \qquad \qquad 1 \le j \le n+1 then the probability that no piece has length 1 4 \tfrac14 or more is p n = P [ x ∈ ( D 1 ∪ D 2 ∪ ⋯ ∪ D n + 1 ) ′ ] = 1 − μ ( D 1 ∪ D 2 ∪ ⋯ ∪ D n + 1 ) μ ( Δ n + 1 ) p_n \; = \; P[\mathbf{x} \in (D_1 \cup D_2 \cup \cdots \cup D_{n+1})'] \; = \; 1 - \frac{\mu(D_1 \cup D_2 \cup \cdots \cup D_{n+1})}{\mu(\Delta_{n+1})} where μ \mu is the Euclidean measure.

For 1 ≤ j ≤ n + 1 1 \le j \le n+1 , let e j ∈ Δ n + 1 \mathbf{e}_j \in \Delta_{n+1} be the point with j j th coordinate equal to 1 1 , and all others equal to 0 0 .

For any 1 ≤ j ≤ n + 1 1 \le j \le n+1 , the scaling map x ↦ e j + 3 4 ( x − e j ) = 1 4 e j + 3 4 x x ∈ Δ n + 1 \mathbf{x} \; \mapsto \; \mathbf{e}_j + \tfrac34\big(\mathbf{x} - \mathbf{e}_j\big) \; = \; \tfrac14\mathbf{e}_j + \tfrac34\mathbf{x} \qquad \qquad \mathbf{x} \in \Delta_{n+1} maps Δ n + 1 \Delta_{n+1} onto D j D_j . Thus it follows that μ ( D j ) = ( 3 4 ) n μ ( Δ n + 1 ) \mu(D_j) = \big(\tfrac34\big)^n \mu(\Delta_{n+1}) .

For any 1 ≤ j < k ≤ n + 1 1 \le j < k \le n+1 , the scaling map x ↦ 1 2 ( e j + e k ) + 1 2 ( x − 1 2 ( e j + e k ) ) = 1 4 ( e j + e k ) + 1 2 x x ∈ Δ n + 1 \mathbf{x} \; \mapsto \; \tfrac12(\mathbf{e}_j+\mathbf{e}_k) + \tfrac12(\mathbf{x} - \tfrac12\big(\mathbf{e}_j+\mathbf{e}_k\big)) \; = \; \tfrac14(\mathbf{e}_j+\mathbf{e}_k) + \tfrac12\mathbf{x} \qquad \qquad \mathbf{x} \in \Delta_{n+1} maps Δ n + 1 \Delta_{n+1} onto D j ∩ D k D_j \cap D_k . Thus it follows that μ ( D j ∩ D k ) = ( 1 2 ) n μ ( Δ n + 1 ) \mu(D_j \cap D_k) = \big(\tfrac12\big)^n \mu(\Delta_{n+1}) .

For any 1 ≤ j < k < m ≤ n + 1 1 \le j < k < m \le n+1 , the scaling map x ↦ 1 3 ( e j + e k + e m ) + 1 4 ( x − 1 3 ( e j + e k + e m ) ) = 1 4 ( e j + e k + e m ) + 1 4 x x ∈ Δ n + 1 \mathbf{x} \; \mapsto \; \tfrac13(\mathbf{e}_j+\mathbf{e}_k + \mathbf{e}_m) + \tfrac14\big(\mathbf{x} - \tfrac13(\mathbf{e}_j+\mathbf{e}_k+\mathbf{e}_m)\big) \; = \; \tfrac14(\mathbf{e}_j+\mathbf{e}_k+\mathbf{e}_m) + \tfrac14\mathbf{x} \qquad \qquad \mathbf{x} \in \Delta_{n+1} maps Δ n + 1 \Delta_{n+1} onto D j ∩ D k ∩ D m D_j \cap D_k \cap D_m . Thus it follows that μ ( D j ∩ D k ∩ D m ) = ( 1 4 ) n μ ( Δ n + 1 ) \mu(D_j \cap D_k \cap D_m) = \big(\tfrac14\big)^n \mu(\Delta_{n+1}) .

Using the Inclusion-Exlcusion Principle, and the fact that all 4 4 -fold intersections of the D j D_j s have measure 0 0 , we deduce that ∣ D 1 ∪ D 2 ∪ ⋯ ∪ D n + 1 ∣ = [ ( n + 1 1 ) ( 3 4 ) n − ( n + 1 2 ) ( 1 2 ) n + ( n + 1 3 ) ( 1 4 ) n ] μ ( Δ n + 1 ) \big|D_1 \cup D_2 \cup \cdots \cup D_{n+1}\big| \; = \; \Big[\binom{n+1}{1}\big(\tfrac34\big)^n - \binom{n+1}{2}\big(\tfrac12\big)^n + \binom{n+1}{3}\big(\tfrac14\big)^n\Big]\mu(\Delta_{n+1}) and hence that p n = 1 − ( n + 1 1 ) ( 3 4 ) n + ( n + 1 2 ) ( 1 2 ) n − ( n + 1 3 ) ( 1 4 ) n p_n \; = \; 1 - \binom{n+1}{1}\big(\tfrac34\big)^n + \binom{n+1}{2}\big(\tfrac12\big)^n - \binom{n+1}{3}\big(\tfrac14\big)^n For this question, p 4 = 1 256 p_4 = \tfrac{1}{256} , making the answer 64 \boxed{64} .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

If we further generalise the problem to investigate the probability q n q_n that, if the rod is broken at n n points, none of the n + 1 n+1 sections have length greater than 1 n \tfrac{1}{n} , then a more complicated use of the IEP shows that q n = ∑ k = 0 n ( − 1 ) k ( n + 1 k ) ( n − k n ) n n n q n = ∑ k = 0 n ( − 1 ) k ( n + 1 k ) ( n + 1 − k − 1 ) n = ∑ k = 0 n ( − 1 ) k ( n + 1 k ) ∑ j = 0 n ( − 1 ) n − j ( n j ) ( n + 1 − k ) j = ∑ j = 0 n ( − 1 ) n − j ( n j ) ∑ k = 0 n ( − 1 ) k ( n + 1 k ) ( n + 1 − k ) j \begin{array}{rcl} q_n & = & \displaystyle \sum_{k=0}^n (-1)^k {n+1 \choose k}\big(\tfrac{n-k}{n}\big)^n \\ n^nq_n & = & \displaystyle \sum_{k=0}^n (-1)^k {n+1 \choose k}(n+1-k - 1)^n \\ & = & \displaystyle \sum_{k=0}^n (-1)^k {n+1 \choose k}\sum_{j=0}^n (-1)^{n-j} {n \choose j}(n+1-k)^j \\ & = & \displaystyle \sum_{j=0}^n (-1)^{n-j} {n \choose j} \sum_{k=0}^n (-1)^k {n+1 \choose k} (n+1-k)^j \end{array} Now ∑ k = 0 N − 1 ( − 1 ) k ( N k ) ( N − k ) j = ∑ k = 0 N ( − 1 ) k ( N k ) ( N − k ) j = 0 1 ≤ j < N \sum_{k=0}^{N-1} (-1)^k {N \choose k} (N-k)^j \; = \; \sum_{k=0}^N (-1)^k {N \choose k} (N-k)^j \; = \; 0 \qquad \qquad 1 \le j < N since the sum is equal to the number of surjective functions from a set of size j j to a set of size N N , and hence all of the terms in the above expression for n n q n n^n q_n vanish except for the j = 0 j=0 terms, and so n n q n = ( − 1 ) n ∑ k = 0 n ( − 1 ) k ( n + 1 k ) = ( − 1 ) n [ ( 1 − 1 ) n + 1 − ( − 1 ) n + 1 ] = 1 n^n q_n \; = \; \displaystyle (-1)^n \sum_{k=0}^n (-1)^k {n+1 \choose k} \; = \; (-1)^n \left[ (1 - 1)^{n+1} - (-1)^{n+1}\right] \; = \; 1 so that the general result is q n = 1 n n . q_n \; = \; \frac{1}{n^n} \;. We note (reassuringly) that p 4 = q 4 = 1 256 p_4 = q_4 = \tfrac{1}{256} .

Seriously though; Level 4 ????????

Mark Hennings - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...