Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Car Talk puzzler analysis - palindromic odometers

    • 3 Comments

    Last week's Car Talk question was again of mathematical interest - it dealt with palindromic numbers on a car's odometer. (This is not the first palindromic odometer question they've done.)

    Read Car Talk's "Tommy's Drive to Work" puzzler question

    Short version:

    Tommy goes for a short drive (under an hour; possibly well under an hour) in his 19-year old new car. He notices that the odometer reading at the beginning and the end of the drive are both palindromes (we're given that his odometer shows six digits.) The question is, how many miles did he drive?

    You're supposed to do a bunch of math, and then experience an epiphany when you realize that, against all odds, there's a single unique answer, even though the odometer readings themselves cannot be uniquely determined.

    Alas, the problem is flawed. There are two perfectly good (and different) answers.

    The intended answer

    The first reading is given as a palindrome - the first three digits (let's call them a, b, c) are the same as the last three digits in reverse (c, b, a). So we can write the first number as abccba.

    The second reading is also given as a palindrome, and we're given that it's a different palindrome (we infer that the odometer is not broken, and he drove at least a mile.) So we can write the second number as xyzzyx.

    We want to find whether it's possible to get these two readings while driving a reasonably small distance. The distance driven is the difference between the odometer readings: xyzzyxabccba.

    xyzzyxabccba
         = (100001 x + 10010 y + 1100 z) – (100001 a + 10010 b + 1100 c)
         = 100001 (xa) + 10010 (yb) + 1100 (zc)

    Because xyzzyx > abccba, we know that xa. Also, if x = a, we know that yb. Finally, if x = a and y = b, we know that z > c (z cannot equal c in this case.) Let's look at these three cases separately.

    Case 1: x = a, y = b, z > c
    xyzzyxabccba
         = 100001 (xa) + 10010 (yb) + 1100 (zc)
         = 100001 (0) + 10010 (0) + 1100 (zc)
         = 1100 (zc)

    z and c can range from 0 to 9, and z > c, so (zc) can range from 1 to 9. So the smallest the distance can be is 1100 miles - for example, 250052 → 259952 (1100 miles.) This is a bit far for an hour's drive.

    Case 2: x = a, y > b, no conditions imposed on z vs. c
    xyzzyxabccba
         = 100001 (xa) + 10010 (yb) + 1100 (zc)
         = 100001 (0) + 10010 (yb) + 1100 (zc)
         = 10010 (yb) + 1100 (zc)

    y, b, z, and c can range from 0 to 9; y > b; and no conditions are imposed on z vs. c. (yb) can range from 1 to 9, (zc) can range from -9 to 9. So the smallest the distance can be is 100101 + 1100 (-9) = 110 miles - for example, 379973 → 380083 (110 miles.) It's certainly possible to drive 110 miles in an hour but not without attracting the attention of the local police!

    Case 3: x > a, no conditions imposed on y vs. b or z vs. c
    xyzzyxabccba
         = 100001 (xa) + 10010 (yb) + 1100 (zc)

    x, a, y, b, z, and c can range from 0 to 9; x > a; and no conditions are imposed on y vs. b, or z vs. c. (xa) can range from 1 to 9, (yb) and (zc) can range from -9 to 9. So the smallest the distance can be is 100001 (1) + 10010 (-9) + 1100 (-9) = 11 miles - for example, 499994 → 500005 (11 miles.) This is much more reasonable.

    The intended answer, then, is 11 miles. There are 9 possible ways to get this distance with palindromic starting and ending readings:

    099990 → 100001 (11 miles)
    199991 → 200002 (11 miles)
    299992 → 300003 (11 miles)
    399993 → 400004 (11 miles)
    499994 → 500005 (11 miles)
    599995 → 600006 (11 miles)
    699996 → 700007 (11 miles)
    799997 → 800008 (11 miles)
    899998 → 900009 (11 miles)

    Not a flaw

    Do we consider numbers with unmatched leading zeros (like 001221) to be palindromes? I would say no. If we did this, it would open up a whole new field of answers such as 77 → 101 (24 miles.) The problem statement seems to imply that all six digits of the number, including leading zeros, need to participate in the palindrome. We can probably infer that Tommy's odometer is an analog odometer that actually shows leading zeros, rather than a digital odometer which hides them; this is consistent with the car being 19 years old.

    The flaw

    All well and good. Alas, there's a flaw in this beautiful analysis - namely, odometers wrap. It's entirely possible for the assumption that xyzzyx > abccba to break down if Tommy started his drive with a number close to 999999, and his odometer wrapped around to 000000 during the drive.

    In fact, this leads to the second reasonable answer:
    999999 → 000000 (1 mile.)

    There are other "wrapped" palindromes, but the next smallest are 998899 → 000000 (1101 miles) and 999999 → 001100 (1101 miles) which are even worse than case 1.

    Could a 19-year-old car have a million miles on it?

    That comes out to an average of 144.1 miles a day, which is high, but achievable (it's only 6 mph.) It's true that Tommy is unlikely to have put this many miles on a car if he lives only a mile from work, but remember that this is his new car (that is, it only recently came into his possession.)

  • Matthew van Eerde's web log

    Translating Ada Lovelace - mathematical science is an instrument

    • 1 Comments

    Lady Augusta Ada, Countess of Lovelace is credited with being the first computer programmer.

    The short version: her associate Charles Babbage gave a lecture on his Analytical Engine in Italy; an Italian engineer wrote up a report on his lecture, in French; Lady Ada then translated the report into English, and added her own notes. Her own notes include a procedure for calculating Bernoulli numbers using the Analytical Engine; it is this procedure which is regarded as being the first computer program, making her the first computer programmer.

    Her translation and notes, in full

    The program (very large image)

    I was skimming through this and stumbled on this sentence which immediately struck me.

    Those who view mathematical science, not merely as a vast body of abstract and immutable truths, whose intrinsic beauty, symmetry and logical completeness, when regarded in their connexion together as a whole, entitle them to a prominent place in the interest of all profound and logical minds, but as possessing a yet deeper interest for the human race, when it is remembered that this science constitutes the language through which alone we can adequately express the great facts of the natural world, and those unceasing changes of mutual relationship which, visibly or invisibly, consciously or unconsciously to our immediate physical perceptions, are interminably going on in the agencies of the creation we live amidst: those who thus think on mathematical truth as the instrument through which the weak mind of man can most effectually read his Creator's works, will regard with especial interest all that can tend to facilitate the translation of its principles into explicit practical forms.
        -- Augusta Ada Lovelace

    Wow, I thought.

    That's a heckuva sentence.

    (I'm a sucker for the "connexion" spelling.)

    ... I have no idea what it means, though.

    I reread it a couple of times until I thought I knew what it meant. (Go ahead. I'll wait.)

    I looked at the last few words: "the translation of its principles into explicit practical forms." As a test I asked myself: "What does 'it' refer to?"

    I didn't immediately know, which revealed that I still didn't really understand the sentence.

    Gosh darn it, I said to myself, I'm going to lick this sentence. I didn't resort to a sentence diagram, but I did a much more forceful attempt at parsing it. Here's how I rewrote it:

    There are two ways to view mathematical science.

    Most people are "normal". Normal people view mathematical science as merely a vast body of truths. These truths are abstract and immutable. They have intrinsic beauty, symmetry, and logical completeness. They connect together to form a whole. Normal people think that all profound and logical minds give a prominent place to these truths.

    But mathematical science possess a deeper interest for the human race. The natural world has great facts. Also, the creation we live amidst has agencies. These agencies have mutual relationships which are unceasingly changing. Sometimes these changes are visible, or otherwise conscious to our immediate physical perceptions. Sometimes they are not. Only the language of mathematical science can adequately express these facts, and these changes.

    Some people are "geeks". Geeks think that mathematical truth is an instrument. They think the weak mind of man can most effectually read his Creator's works through this instrument.

    Sometimes a special kind of technique is discovered. These techniques tend to translate the principles of mathematical science into explicit practical forms.

    Geeks are specially interested in all such techniques.

        -- Augusta Ada Lovelace, paraphrased
  • Matthew van Eerde's web log

    Car Talk puzzler analysis - Limerick equation

    • 2 Comments

    Car Talk's puzzler of the week has some mathematical interest. See Car Talk's transcript of the question.

    In brief, we are given the equation...

    (12 + 144 + 20 + 3√4) / 7 + 5(11) = 92 + 0

    (which holds true, by the way)
    ... and asked to transcribe it as a limerick.

    The last line of the limeric is given: "Is nine squared, and not a bit more."

    The answer, ROT13'd for your convenience until the Car Talk folks reveal it:

    N qbmra, n tebff, naq n fpber
    Cyhf guerr gvzrf gur fdhner ebbg bs sbhe
    Qvivqrq ol frira
    Cyhf svir gvzrf ryrira
    Is nine squared, and not a bit more.

    This is not the only equation to be immortalized in a limerick. There's also this old chestnut. It relies on pronouncing the letter z as "zee" (rather than "zed",) as well as reading "log base e" (usually spelled "ln") for "log".

    The integral z2 dz
    From one to the cube root of three
    All times the cosine
    Of three pi over nine
    Equals log of the cube root of e.

    This equation also holds true.

    There's also this classic from Lewis Carroll which waxes a bit philosophical:

    Yet what mean all such gaieties to me
    Whose life is full of indices and surds
    x2 + 7x + 53
    = 11/3.

    Perhaps fittingly, this last equation has only imaginary solutions.

  • Matthew van Eerde's web log

    Linearity of Windows volume APIs - IAudioMeterInformation and full-scale signals

    • 6 Comments

    We have talked about some of the volume APIs Windows exposes. We have also talked about what it means for a volume control to be linear in magnitude, linear in power, or linear in dB.

    The attachment to this blog post contains:

    • An app I wrote to exercise the IAudioStreamVolume, ISimpleAudioVolume, IChannelAudioVolume, and IAudioEndpointVolume APIs
    • An Excel spreadsheet with the analysis of the output of the app

    Let's start by looking at what the app does.

    >volume-linearity.exe
    volume-linearity.exe --signal | --stream | --session | --channel |
        --endpoint-db | --capture
    --signal varies the amplitude of the generated signal from 0 to 1
    --stream varies the IAudioStreamVolume from 0 to 1
    --session varies the ISimpleAudioVolume from 0 to 1
    --channel varies the IChannelAudioVolume from 0 to 1
    --endpoint-db varies the IAudioEndpointVolume from X dB to Y dB
        where X and Y are the min and max values supported
    --capture varies session, channel, and endpoint-db volumes
        on the default capture device

    Let's look at --signal mode first. The app plays a square wave at amplitudes from 0 (silence) to 1 (full-scale), varying in a linearly in magnitude. It takes periodic readings using IAudioMeterInformation to see what the peak values on the other side of the audio engine are. The IAudioMeterInformation API returns readings that are also linear in magnitude, so the response graph looks nice and linear:

    Well... wait a second. What happened at full scale? Let's get a closer look:

    When we attempt to play a square wave of amplitude greater than about 0.985, the meter reveals that what we get out of the audio engine is not quite what we put in. The volume has been capped. What's going on?

    If we look at the list of WASAPI Audio Processing objects, notice that one of them is called CAudioLimiter. The job of this APO is to take its input and produce output that is limited to the range (-1, 1). When it sees that signals are getting too close to the edge, it steps in and pulls the signal closer to the center.

    For this reason, the other modes of volume-linearity.exe use a half-scale (-1/2, 1/2) square wave rather than a full-scale square wave.

    UPDATE June 1 2011: added --capture mode

  • Matthew van Eerde's web log

    Basic audio volume theory

    • 2 Comments

    Last time we talked about the different Windows Audio Session APIs for setting volume. Let's talk a little about what volume means.

    For purposes of illustration, let's take our signal to be a full-scale square wave:

    Incidentally, the answer to the exercise

    completely characterize the set of digital signals that achieve 0 dB FS intensity. If you have, say, 1000 samples of mono 16-bit integer audio to play with, how many distinct signals achieve 0 dB FS intensity?

    is "all signals with N/2 samples having value 1 and N/2 samples having value -1". There are

    such signals. For N = 1000 this is comes out to about 2.7e299.

     

    Linear in amplitude

    If we multiply the signal by a number between 0 and 1, we reduce the volume. That's the first natural volume scale - the "linear in amplitude" scale. 0 is silence, 1 is an unchanged signal, and 1/2 is a signal with all the amplitudes divided by 2.

    Linear in power

    Recalling the formula for the intensity of a signal, we realize that the power (intensity squared) of a signal depends on the square of the magnitude. This leads us to the second natural volume scale - the "linear in power" scale. 0 is still silence, and 1 is still an unchanged signal, but now 1/2 maps to a signal with half of the power of the original signal. In particular, a full-scale square wave with power 1 would drop to a square wave with power 1/2 - this has amplitude sqrt(1/2) which is significantly more than 1/2.

    Linear in dB

    So far so good. However, sound is perceived in a relative fashion. Humans are not very good at determining absolute volume, but are very good at determining relative volume. If I play a sound and ask you "what is the dB SPL of the sound I just played", you would have trouble answering; but if I played two sounds and asked "which sound was louder", you would be able to tell me. You would even be able to give me an estimate such as "it's about twice as loud".

    So a natural scale for volume is based on relative power - that is, a logarithmic scale dB = 10 * log10( PA / P0 ) where PA is the attenuated signal and P0 is the original. That looks something like this:

    Note that the relative power scale has no bottom! It's turtles all the way down.

    So how do you map an infinite volume scale onto a finite slider, while preserving the nice property that equal distances map to equal power ratios?

Page 1 of 1 (5 items)

May, 2011