Let's solve a cool problem.
Suppose there is an \(n\) person committee. Let an arrangement of this committee be a derangement if none of the committee members are sitting where they are supposed to be sitting. Let \(P(n)\) be the probability that a randomly chosen arrangement of the \(n\) person committee is a derangement. What is \(\lim_{n\rightarrow\infty}{P(n)}\)? That is, what does this probability approach as the number of members grows arbitrarily large? First, let us define some notation. Let \(D_n\) be the number of derangements of an \(n\) person committee. How can we count \(D_n\)? There are \(n!\) possible arrangements. Perhaps we can use complementary counting by finding the total number of arrangements where at least one member is sitting in his or her assigned seat, and then subtract that number from \(n!\). It turns out that it is pretty much impossible to count how many different ways we can have an arrangement with exactly \(1\leq k\leq n\) members in their correct seat. Try it for yourself and see what problems you run into. There is no simple algorithm to derange a set. Note that I say simple. It is certainly possible to construct an algorithm based on swapping elements that are in the correct spots. Good luck keeping track of that for counting purposes. Instead, we take a step back and think. We only need the sum of the number of arrangements with exactly \(k\) members in their correct seat from \(k=1\) to \(k=n\). Observe that while it is difficult to count the number of arrangements with exactly \(k\) correct seatings, it is much easier to count the number of arrangements with at least \(k\) correct seatings. We can then use the principle of inclusion-exclusion to deduce the sum of the number of arrangements with exactly \(k\) correctly seated members without counting a single such case! So we calculate the number of possible arrangements where at least \(k\) people are sitting in his or her own assigned seat. There are \(\binom{n}{k}\) ways of choosing the number of ways to choose which people are guaranteed to sit in their correct seats. This leaves \((n-k)!\) ways to arrange the remaining people however we wish. It is totally possible that while arranging the these remaining people, someone gets seated where they are supposed to, hence why \(\binom{n}{k}(n-k)!=\frac{n!}{k!}\) is only the number of arrangements where at least \(k\) people are seated correctly. By the principle of inclusion-exclusion, the alternating sum of these must be the desired value. Hence, \[\begin{split} D_n&=n!-\left[\frac{n!}{1!}-\frac{n!}{2!}+...+(-1)^{n+1}\frac{n!}{n!}\right]\\ &=n!\sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}}. \end{split}\] Since the total number of arrangements is \(n!\), we can easily calculate the probability: \[P(n)=\frac{D_n}{n!}=\sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}}.\] Taking the limit, \[\lim_{n\rightarrow\infty}{P(n)}=\sum_{k=0}^{\infty}{\frac{(-1)^{k}}{k!}}.\] But now the RHS is the Taylor series of \(e^x\) evaluated at \(x=-1\)! Hence our requested limit is simply \(\boxed{\frac{1}{e}}\). This is approximately 36.8%. The function \(D_n\) enjoys a number of cool properties. One of them is: \[\sum_{k=0}^{n}{\binom{n}{k}D_{n-k}}=n!.\] See if you can find a combinatorial proof of this. Hint: The construction is similar in spirit to the one we used to find the sum of the number of arrangements with exactly \(k\) correctly seated members.
0 Comments
Here is a cute problem from Sweden. It is simply stated. Solve
\[(\sqrt{2}-1)^x+(\sqrt{2}+1)^x=6.\] Before reading on, I strongly encourage you to give this a shot yourself. This is one of those problems that make you slap your forehead in disgust when you see the solution because it's so dumb simple. Ok. Here's my solution. We multiply through with, say, \((\sqrt{2}+1)^x\). This gives us \[1^x+(\sqrt{2}+1)^{2x}=6(\sqrt{2}+1)^x.\] But \(1^x=x\forall x\in\mathbb{R}\) so \[1+(\sqrt{2}+1)^{2x}=6(\sqrt{2}+1)^x.\] Aha! Now this is quadratic in \((\sqrt{2}+1)^x\). Letting \(y=(\sqrt{2}+1)^x\), we have \[y^2-6y+1=0,\] from which we find the roots to be \[y=3\pm2\sqrt{2}.\] Hence, \[(1+\sqrt{2})^x=3\pm2\sqrt{2}\] and we have our two solutions \[\boxed{x=\log_{1+\sqrt{2}}{(3\pm2\sqrt{2})}=\pm2}\] Haha... Back in my (early) wannabe days, in the summer between sophomore and junior year, I was studying single-variable calculus. From the AoPS book, I found this extra sidenote.
Consider a positively oriented closed simple curve (a curve that is closed, non-self intersecting, and traced such that region enclosed by the curve is always on the left) parameterized by \((x(t),y(t))\) from \(t_0\) to \(t_1\). Then, the area of the enclosed region is given by: \[\frac{1}{2}\int_{t_0}^{t_1}{x(t)y'(t)-x'(t)y(t)\textrm{ d}t}.\] Back then, I could barely understand the statement, and once I did, I had no clue as to how it would be true. The sidenote said that it was a special case of Green's Theorem from vector calculus. Two years later, I can finally say that I know where this comes from. Green's theorem states that for a positively oriented closed simple curve \(C\) enclosing a region \(R\), and a vector field \(\mathbf{F}\), \[\oint_{C}{\mathbf{F}\cdot\textrm{d}\mathbf{r}}=\iint_{R}{\nabla\times\mathbf{F}\textrm{ d}A},\] where \(\nabla\times\mathbf{F}\) is the 2D curl (I know, it's a 3D thing so I'm abusing the notation a little). This is a cool result. For instance, it immediately establishes all the stuff about path-independence of line integrals over conservative fields which have to be curl-free and blah, blah, blah. If \(\nabla\times\mathbf{F}=1\), then the RHS evaluates to the area of \(R\). So we want a vector field, \(\mathbf{F}=\langle M,N\rangle\), such that \(\frac{\partial N}{\partial x}-\frac{\partial M}{\partial y}=1\). Perhaps the simplest \(\mathbf{F}\) satisfying this is \(\mathbf{F}=\left\langle -\frac{y}{2},\frac{x}{2}\right\rangle\). Then by Green's theorem, we have \[\begin{split} A&=\oint_{C}{-\frac{y}{2}\textrm{ d}x+\frac{x}{2}\textrm{ d}y}\\ &=\frac{1}{2}\oint_{C}{\left(x\frac{\textrm{d}y}{\textrm{d}t}-y\frac{\textrm{d}x}{\textrm{d}t}\right)\textrm{d}t}\\ &=\frac{1}{2}\int_{t_0}^{t_1}{x(t)y'(t)-x'(t)y(t)\textrm{ d}t}, \end{split}\] as desired. \(\square\) Cool beans. |
Categories
All
Archives
July 2023
|