Quite an interesting problem popped up on my Twitter feed the other day:
Here's a neat puzzle:
— Ramanujan's Dosa (@RamanujansDosa) September 9, 2022
We buy 12 éclairs from a bakery.
Each éclair measures 1 x 2. And they all go into a 12 x 2 box.
In how many ways can the baker arrange the éclairs in the box? Two possible ways are shown in the picture below.
Solution coming tomorrow! pic.twitter.com/1ekGIkUiBD
Take a few minutes and try to devise a solution to this problem.
OK, let’s get down to business and solve this!
I immediately thought about this problem as arranging two types of balls in a row — say, green and red. The green balls would be synonymous with horizontally laid couples of brownies, and the red would be synonymous with the rest, vertically laid, single brownies.
In this case, only these configurations are possible:1
| Green | Red |
|---|---|
| 0 | 12 |
| 1 | 10 |
| 2 | 8 |
| 3 | 6 |
| 4 | 4 |
| 5 | 2 |
| 6 | 0 |
For each configuration, multiple possible arrangements can be made.
- When we have 0 green balls, there’s only 1 possible arrangement.
- When there’s a single green ball, there are 11 possible arrangements.
- When there are 2 green balls, we need to choose 2 locations for them from 10 possible locations, which is \(10 \choose 2\).
This leads us to the general formula for the number of arrangements per a single configuration:
\[\#green+\#red \choose \#green \\\]Of course, we need to sum this over the possible configurations, and so we end up with the following formula for the number of available possible arrangements:
\[\#Arrangements = \sum\limits\_{i=0}^{6} {12-i \choose i} = 233 \\\]This can also be generalized to the case where we have \(n\) éclairs in total:2
\[a*{n+1} = \sum\limits*{i\geq0}^{} {n-i \choose i} \\\]The solution given in the tweet is a bit more elegant, in my opinion. In essence, it decomposes the problem recursively to the number of available arrangements for fewer brownies. It all boils down to the well-known formula for Fibonacci numbers:
\[a*{n+1} = a*{n} + a\_{n-1} \\\]where \(a_{n+1}\) is the number of possible arrangements for \(n+1\) brownies.
Thus, we can actually deduce the following formula for Fibonacci numbers:
\[\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} -\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right] = a*{n} + a*{n-1} = a*{n+1} = \sum\limits*{i\geq0}^{} {n-i \choose i} \\\]I just love it when two different subjects pop into solutions of problems — more so when it gives out a formula that binds them together! 🤩
Comments