October 4th
Today I learned an interesting application of M\"obius inversion. The question extends the classic light bulb problem: in an infinite sequence of numbered light bulbs ($1$-indexed), person $n$ flips the switches corresponding to all light bulbs divisible by $n$ for $n\in\ZZ^+.$ We want to know which light bulbs are on after everyone is done. Well, these are exactly the ones for which\[\sum_{d\mid n}1=d(n)=\prod_{p\mid n}(\nu_p(n)-1)\]is odd. But this requires each individual $\nu_p(n)-1$ to be odd, or each $\nu_p(n)$ to be even, so light bulb $n$ is on if and only if $n$ is square.
There is some interesting structure when we stop using every single person. Of course, given a set of people, we can determine which light bulbs are on at the end by computing the parity of $\#\{d\mid n:d\text{ is used}\}.$ Adding in some notation, we can assign bits to each person in $\{p_k\}$ so that $1$ means the person is used and $0$ means not. Then the sum we want the parity of\[\#\{d\mid n:p_d=1\}=\#\{p_d:d\mid n\}=\sum_{d\mid n}p_d=(1*p)(n),\]which is a bit nicer. A slightly more interesting question is that, given a pattern of light bulbs to be on, can we reverse it to get a sequence of people turning those light bulbs on?
This is not terribly hard; naturally, we can do it by an induction. Suppose we have a sequence of bits $\{b_k\}$ that we want our light bulbs to match, and we want to assign bits $\{p_k\}$ to our sequence of people. We claim that the first $n$ people-bits make the first $n$ light bulbs match up with $\{b_k\},$ in fact uniquely, which provides an affirmative answer to the question. We do this by induction. When $n=0,$ there is nothing to prove.
Then assume we can do this uniquely with $n=N$ bulbs; we show $n=N+1.$ We start off the sequence $\{p_k\}_{k=1}^N$ generating the first $N$ bulbs. Then we claim $p_{N+1}$ is determined uniquely. Indeed, compare the parity of $b_{N+1}$ and\[\sum_{\substack{d\mid N+1\\d \lt N+1}}p_d.\]If they match, then $b_{N+1}$ must be off. This will not affect any previous bits $b_k,$ so we indeed cover all bulbs up to $N+1.$ Else if the parities don't match, then $b_{N+1}$ must be odd to correct. Again, we cover all bulbs to $N+1$ and are forced in our choice. This finishes.
What's weird is that the above inductive process gives me the feeling of a finite Fourier transform. In particular, it feels as if we should be able to read off $p_k$ with some summation not requiring the above inductive argument. Relabel our sequences $b(n)$ and $p(n)$ so that we want\[b(n)\equiv\sum_{d\mid n}p(d)\pmod2.\]I guess this is equivalent to\[(-1)^{b(n)}=\prod_{d\mid n}(-1)^{p(d)}.\]Then M\"obius inversion tells us this is equivalent (!) to\[(-1)^{p(n)}=\prod_{d\mid n}(-1)^{\mu(d)b(d)},\]which is what we wanted. As an aside, I'm used to proving the product form of M\"obius inversion by logarithms, but it should still work in the above by just choosing a branch, probably. In any case, we can always just do the old proof of plugging one equation into the other to show the implications.