Don't lose your marbles!

A bag contains 100 marbles, and each marble is one of three different colors. If you were to draw three marbles at random, the probability that you would get one of each color is exactly 20 percent.

How many marbles of each color are in the bag?

Let's say that the number of each color is $A,$ $B$ and $C,$ with $A + B + C = 100.$ The number combinations of one marble of each color would thus be $ABC.$ The total number of possibilities for pulling three marbles out is $\binom{100}{3}.$ So if the probability is exactly $20\%$ then we would have $$\frac{ABC}{\binom{100}{3}} = 20\%$$ that is $$ABC = 0.2 \cdot \frac{100 \cdot 99 \cdot 98}{6} = 32,340.$$

Even after decomposing into prime factors, there are a lot of ways to possible come up with $A$, $B$ and $C$ such that $ABC = 32,340 = 2^2 \cdot 3 \cdot 5 \cdot 7^2 \cdot 11.$ However, there are not so many possible combinations that it makes sense to do something more rigorous than the all-important "guess and check" method, which eventually ends you up with $A = 21,$ $B = 35,$ and $C = 44.$

Crash .... Into Me?

Eight two-way roads all converge at a single intersection, as shown in the diagram below.

Two cars are heading toward the single intersection from different directions chosen at random. Upon reaching the intersection, they both turn in a random direction (where proceeding straight is a possible “turn”) — however, neither car pulls a U-turn (i.e., heads back the way it came).

In some cases, the paths of the cars can be drawn so that they do not cross. In this case, all is well. However, in other cases, the paths must cross. In this event, the cars will crash.

What is the probability the cars will crash? (If both cars head off in the same direction, that also counts as a crash.)

Let's deal instead with the general case of $N$ roads converging. We can label them $0$ through $N-1$ and without loss of generality assume that one of the cars always starts on the road labeled $0.$

Let's say that this first car starts on road $0$ ends up turning onto some road $k \in \{1, \dots, N-1\}.$ Then there will be a crash whenever (a) the second car starts on a road in $\{1, \dots, k-1\}$ and ends on a road in $\{k, \dots, N-1\}$ or (b) the second car starts on road a road in $\{k+1, \dots, N-1\}$ and ends on a road in $\{1, \dots, k\}.$ (Note explicitly that the car going from road $0$ to road $k$ will never crash with a car that starts on road $k.$)

The diagram below shows the $5$ case (a) crashes for $N=8$ and $k=3$ where the second car starts on road $1$.

Similarly, the diagram below shows the $3$ case (b) crashes for $N=8$ and $k=3$ where the second car starts on road $5.$

Since there are $(N-k)(k-1)$ combinations in case (a) and $(N-k-1)k$ combinations in case (b), if the first car starts on road $0$ and ends up turning onto road $k$, then there are $$(N-k)(k-1) + (N-k-1)k = (2k-1)N -2k^2$$ possible crashes.

Summing over all possible $k$ gives us a total of $$C_N = \sum_{k=1}^{N-1} (2k-1)N -2k^2 = N(N-1)^2 -\frac{1}{3}(N-1)N(2N-1) = \frac{N(N-1)(N-2)}{3}$$ crashes with $N$ converging paths. Since there are $(N-1)$ possible choices for the first car and $(N-1)^2$ possible choices for the second car, we get a crash probability with $N$ paths of $$p_N = \frac{C_N}{(N-1)^3} = \frac{N(N-1)(N-2)}{3(N-1)^3} = \frac{N(N-2)}{3(N-1)^2}.$$

In particular, when $N=8,$ we get $$p_8 = \frac{16}{49} \approx 32.65\%.$$ Also, as the number of paths increases, we get $$p_\infty = \lim_{N\to \infty} p_N = \frac{1}{3}.$$

Mathemagical Mastery

Max the Mathemagician is calling for volunteers. He has a magic wand of length $10$ that can be broken anywhere along its length (fractional and decimal lengths are allowed). After the volunteer chooses these breakpoints, Max will multiply the lengths of the resulting pieces. For example, if they break the wand near its midpoint and nowhere else, the resulting product is $5\times 5$, or $25$. If the product is the largest possible, they will win a free backstage pass to his next show. (Amazing, right?)

You raise your hand to volunteer, and you and Max briefly make eye contact. As he calls you up to the stage, you know you have this in the bag. What is the maximum product you can achieve?

In order to get backstage with Max or Zax or ?ax the Mathemagician, let's solve the general problem of Generic the Mathemagician whose magic wand has length $L.$ Here we will also solve the general problem by assuming that we want to maximize the product using exactly $n-1$ cuts for some as yet undetermined $n \in \mathbb{N}.$ In fact, define $P(n,L)$ to be the maximum product one can get from multiplying the lengths of the pieces after making $n-1$ cuts in a wand of length $L.$ In particular, $$P(n,L) := \max \left\{ \prod_{i=1}^n x_i \biggr\vert \sum_{i=1}^n x_i = L, \, 0 \leq x_i \leq L, i = 1,\dots, n \right\}.$$ Since the natural logarithm is monotonically increasing, the problem is equivalent to solving the following \begin{align*}\ln P(n,L) = \max \, & \, \sum_{i=1}^n \ln x_i \\ \text{s.t.} \, & \, \sum_{i=1}^n x_i = L \\ & \, 0 \leq x_i \leq L, \, i = 1, \dots, n.\end{align*}

The Lagrangian on this later formulation is $$\mathcal{L}(x, \lambda) = \sum_{i=1}^n \ln x_i + \mu \left( \sum_{i=1}^n x_i - L \right)$$ which has gradient $$\nabla_x \mathcal{L}(x,\lambda) = \begin{pmatrix} 1/x_1 + \mu \\ 1/x_2 + \mu \\ \dots \\ 1/x_n + \mu \end{pmatrix},$$ so for any $\mu \in \mathbb{R},$ the only stationary point is $\hat{x}(\mu) = (-1/\mu, \dots, -1/\mu) \in \mathbb{R}^n.$ So, in order to satisfy the condition that $\sum_{i=1}^n x_i = -n/\mu = L,$ we need $\hat{\mu} = -n/L,$ in which case $\hat{x} = (L/n, \dots, L/n)$ is the optimal solution and $$P(n,L) = \left(\frac{L}{n}\right)^n.$$

For the moment, let's extend this problem to allow for a non-integral number of cuts. That is, define $$\tilde{P}(x,L) = \left( \frac{L}{x} \right)^x = \exp ( x \ln L - x \ln x ),$$ such that for $x \in \mathbb{N},$ $\tilde{P}(x,L) = P(x,L).$ In this case, $$\frac{\partial}{\partial x} \tilde{P}(x,L) = (\ln L - 1 - \ln x) \tilde{P}(x,L)$$ such that for any $L$ the maximal value of $$\hat{x}_L = \arg\!\max \{ \tilde{P}(x,L) \mid x \geq 0 \} = \frac{L}{e}.$$ Therefore, we have for any $L,$ that the $$\max_{n \in \mathbb{N}} P(n,L) = \max \left\{ P\left( \left\lfloor \frac{L}{e} \right\rfloor, L \right), P\left( \left\lceil \frac{L}{e} \right\rceil, L \right) \right\} \sim e^{L/e}.$$ In particular, for Max (where $L=10$) we have $\hat{n} = \lceil 10 /e \rceil = 4$ equal cuts for a maximal product of $(2.5)^4 = 39.0625.$ For Zax (where $L=100$), we have $\hat{n} = \lceil 100 / e \rceil = 37$ equal cuts with maximal product of $(100/37)^{37} = 9.474 \times 10^{15}.$