I suppose this is what they call a blog. Except that blogs are supposed to be updated more often than this is.
Feeds: Atom 1.0 (preferred), RSS 0.91. Front page: link.
|
||||||||||||||||||||||||||||||||||||||||||||||||||
I discovered recently that a fruit with the same sort of structure as, e.g., an orange is called a hesperidium.
Why that curiously beautiful word? Well, you see, Greek mythology features the golden apples of the Hesperides, and oranges look kinda like apples but are kinda-sorta golden in colour.
(The Hesperides are the nymphs of the West, the land of the evening (hesperos); presumably the similarity to the Latin equivalent Vesper is no coincidence, but I know no more.)
Child: Daddy, better than nothing would be the worst thing in the world.
Daddy: ...
After a moment’s thought, though, I realised that she was exactly right. “x is better than nothing” = “x is not better than anything” = “x is at least as bad as anything else” = “x is the worst thing in the world”.
It’s the same idea as the old joke: A ham sandwich is better than eternal happiness, because nothing is better than eternal happiness and a ham sandwich is better than nothing.
After we had an appliance serviced, we were sent a survey with a prize draw as incentive. The conditions include the following (emphasis mine).
6. There shall be five winners per draw of this Promotion. The winners will receive Samsung digital still cameras. The model of digital still camera is subject to change and the decision will be made by the Promoter. A total of three prizes per draw.
I wonder what happens to the other two winners. (Maybe each winner gets 3/5 of a camera.)
The binomial coefficient
![\[\tbinom{n}{r}\]](/g/tex-images/be901d7e0657346931ab67fd47d7814b.png){kind=small}
is the number of ways, if you have n things,
of choosing r of them; equivalently, the number
of n-digit strings, all digits 0 or 1, with
r 1s and the rest 0s; equivalently, the
coefficient of xr when you
expand out (1+x)n.
There’s a nice (and well known) theorem that says: this is odd precisely when subtracting r from n in binary requires no borrowing. (So, e.g., if n is a power of 2, then this happens only when r=0 or r=n.) There’s a very pretty generalization of this which isn’t so well known. (So far as I can remember, I found it myself, but others got there long before me.) Here it is:
Theorem: Suppose you are interested in
modulo p, a prime number. (That is, you don’t care
if your answer is wrong by a multiple of p.) Then
you can compute it as follows. Write down n and r
in base p. If r’s base-p representation
is shorter than n’s, pad it on the left with zeros
to make it the same length. Then
![\[\binom{n}{r}=\binom{n_k}{r_k}\binom{n_{k-1}}{r_{k-1}}\cdots\binom{n_0}{r_0} \pmod{p}.\]](/g/tex-images/345844d0dfd830d5df023fa9f4a17b67.png){kind=small}
In other words: compute one binomial coefficient for each corresponding pair of digits, and multiply them all together.
You’ll get 0 – i.e., a multiple of p – if and only if one of the factors is a multiple of p, which (it turns out to be easy to prove) happens if and only if for some j, rj>nj. In the case p=2 this (it turns out to be easy to prove) is the same as the condition I mentioned earlier about subtracting r from n.
Proof:
it’s enough to show that (mod p)
![\[\tbinom{mp+n}{rp+s}=\tbinom{m}{r}\tbinom{n}{s}\]](/g/tex-images/5f4d98b2c85b2275097a44322d288cf6.png){kind=small}
since that lets us split off the last base-p digit,
and we can then repeat until we’ve done all the digits.
So, consider
(1+x)mp+n.
This equals
((1+x)p)m(1+x)n.
and modulo p this equals (for reasons I’ll explain
in a moment)
(1+xp)m(1+x)n.
Now to get a term containing xrp+s
we need the xs term from the second factor,
and therefore the
xrp=(xp)r
term from the first. These come with factors of
![\[\tbinom{n}{s}\]](/g/tex-images/dc660a5a7d9498be38a6875781753faa.png){kind=small}
and
![\[\tbinom{m}{r}\]](/g/tex-images/67ad8974e3498a07baa6229d8ee4c2b1.png){kind=small}
,
respectively, attached. And we’re done ...
... except that I promised to explain why
((1+x)p)m
and
(1+xp)m
are equal modulo p.
Clearly it’s enough if
(1+x)p
and
1+xp
are equal modulo p.
Well, when you expand out
the former, the coefficient in front of each
xr is (by definition)
![\[\tbinom{p}{r}\]](/g/tex-images/c9e498087137e25e5f8b8a1517aed140.png){kind=small}
. The coefficients
of x0 and xp
are both 1, obviously. What about the others? We need
to prove that they’re all multiples of p.
Well, remember another definition of
: the number of
p-bit strings of 0s and 1s containing r 1s.
If 0<r<p then a “rotation”
of such a string (e.g., 01100 gives 00110, 00011, 10001, 11000)
still contains exactly r 1s,
and all the p different rotations are different
(why?). Hence the number of such strings is a multiple
of p, as I claimed.
(You can also prove the theorem more “directly” via a combinatorial argument involving counting the ways of selecting rp+s things from mp+n, and actually that’s how I first proved it. It’s also the proof sketched on the theorem’s Wikipedia page. Maybe there’s an even simpler proof?)