Another scale problem

by Tom Temple

22 June 2009, 09:05

Somebody at work asked about the chicken scratchings I used in the snack room and in response to my solution said something fawning about how neat it was that I could just change my number representation however it suited me.

As Jon would guess, that led to a conversation about balanced tertiary, and the following problem arose.

You have a balance with two pans and an object with integer mass, N, that you would like to determine. You have the following known masses:
let k be an odd, positive integer. You have (_k_ – 1)/2 of each mass of weight kn for n in the non-negative integers. With this set of masses, each integer will have a unique representation.

You would like to determine N in a minimum number of weighings. Any time you add or remove a single mass from the scale counts as a weighing.

For instance let k=3, and I wanted to put 128g (=243-81-27-9+3-1) on the scale when 256g (=243+9+3+1) was on their previously. To do so counts as 6 weighings.

I’m looking for the big-Oh (in terms of N,k) of your strategy. From the above example I think it would be easy to argue that binary search is O(log 2 (N)). Can anyone do better?

Keeping Tabs

by Tom Temple

17 June 2009, 14:12

At work we’ve got a snack room and there is a tab on the wall. Attached to it is a pen rather than a pencil as you would expect in a perfect world… Anyway, I’m struck by how inefficiently most people use the space in it, forcing it to be pages and pages long.

All the prices are divisible by five and go from 5c up to $1 with 45, 55, 65, and 95cents all absent. Come up with a scheme for keeping track of the cumulative sum of transactions that doesn’t use a lot of space.

Benchmark: You’ve got enough room for about 80 characters, so you should be able to get at least 160 items before starting another page.

Hard version: You maintain a fixed number strings of {0,1}*. After each transaction (containing potentially multiple items) you may add as many characters to whatever strings you’d like. From these strings you need to be able to construct the sum of the transactions.

You can assume each transaction comes from a finite set with a known probability distribution. Come up with a scheme that minimizes the expected bits per transaction. You’re welcome to make limiting case arguments, but winners are going to be picked at 640 bits.

Talking Tough

by Tom Temple

17 June 2009, 10:55

Generally, I think “talking tough” is bad foreign policy. Keep in mind that in every country you’ll find people who agree with you and people who don’t. Our “tough talk” tends to buttress the people who disagree with you. Apropos of Iranian elections, John Dickerson basically agrees.

Fred Kaplan makes the argument that now is a moment when talking tough to the Iranian government wouldn’t be construed as talking tough to the Iranian people. As a result, it wouldn’t necessarily be counterproductive.

If you were the President, what would you say?

Continue...

Edutainment

by Tom Temple

27 May 2009, 21:25

I’m getting the impression that the standard for educational TV show has really dropped since we were young. I regularly watch National Geographic specials, but they are dominated by “dramatic re-enactments” with really minimal and meaningless narration. I was thinking that the difference is that I’m pickier now—that Nova wasn’t that much better. On the other hand, I’ve always been suspicious that Nova couldn’t have done that kind of thing, even if it wanted to.

I’m in the middle of watching Scientific American Frontiers after watching Nova, and I can assure you, they are much better than anything else on the TV currently.

What I don’t understand is why isn’t (e.g.) the National Geographic Channel comparable? It isn’t like Nova is very expensive to produce. Is it that it is impossible to sell commercials during shows this?

Honest Geekiness?

by Tom Temple

21 May 2009, 18:50

This ad really resonates with me—it makes me want to work for intel. I’m not sure why. Probably because it is a spot-on potrayal about what geeky really means. Maybe its because the usual portrayal of geeky is so grating (e.g. hire geeks to set up your DVR!).

If Bertsimas walked into my lab, I swear to God, it would be just like that. I bet I could make money selling the t-shirt.

Humans vs Machines in Rock Paper Scissors

by Tom Temple

12 May 2009, 11:40

Here’s an applet that lets you play rock/paper/scissors against the computer. Some of you might find the following two experiments interesting. You should do the experiments before reading how the algorithms work.

  1. Play with the window scaled such that you can’t see the results. In other words, do your best to create a random sequence. Check in every 25 clicks or so.
  2. Watch the computer and see how well you can “fake it out.”
Continue...

Boy vs wild

by Tom Temple

29 April 2009, 11:53

A 17yr old eagle scout was lost for three days in the Presidentials. I’d assumed that he was dead a day before they reported that he had been found okay.

Continue...

Gender Differences

by Tom Temple

28 April 2009, 08:47

Reading through the PISA results for this post, I noticed that they demonstrate a cross-culture difference in the way that boys and girls understand science.

Continue...

Standardized Failure

by Tom Temple

27 April 2009, 19:47

Standardized Testing in General and No-Child-Left-Behind in Particular are Destroying our Schools

You are doubtlessly aware that there has been some controversy regarding the effects of the historic “No Child Left Behind” law, created in 2002. In fact, the “controversy” is the political kind. Amongst teachers there is a robust consensus: It’s hamstringing them.

Continue...

Sci Fi observations

by Tom Temple

22 April 2009, 18:47

Between the inexorable improvements in Netflix and my mounting dread over my thesis proposal, I have been giving myself a much deeper understanding of the science fiction genre historically. From this, I would like to make the following observations so that the creators of future science fiction can make more lasting and historically significant contributions.

First up, Styles. This one is easy, the crazier the better. If anybody looks even remotely “hip” or “cool” or anything stylistically recognizable in your era, it will look painfully dated in the future. As I said, the crazier the better.

Second, tech. This is where the smart kids like to make predictions. Getting stuff right makes the work look sagely, getting it wrong makes you look stupid. Unless you’ve got someone like Kim Stanley Robinson on staff, you’re mostly going to want to keep this stuff as dialed back as necessary for the story line. But if you do have some predictions, I won’t fault you for going out on that limb.

Third, interfaces, controls. To the untrained, this might seem like “tech” and people with vision might be able to do something. While that’s somewhat true, this is dramatically harder than tech. Even if you do have Kim Stanley Robinson writing for you, best way to handle this is by minimization. While The Matrix Trilogy, or Final Fantasy, The Spirits Within, or even James Bond and his Quantum of Solace, make somewhat inspired attempts, despite how sweet they look now, I feel pretty confident saying that most of those things are going to end up looking stupid in the future. I think the right way to do it is more like Doctor Who’s “sonic screwdriver” or Star Trek’s “tricorder” where it’s operation is left to the imagination.

Which brings up the overarching principle: If something can be left to the imagination, leave it to the imagination. For example, using somebody’s console with a “code red” pop-up as a cut device is only going to make your movie look stupid, regardless of how much you spend on graphic design. How much harder is it to tell the actor to “give me a ‘code red’ expression” and shoot it from an angle where you can’t see the controls?

Information Asymmetry

by Tom Temple

3 April 2009, 11:52

Can any of the anti-regulation economists who come here respond to this quote from vanity fair ?

One of the hidden causes of the current global financial crisis is that the people who saw it coming had more to gain from it by taking short positions than they did by trying to publicize the problem.

BTW: I found that article from here

Browser Selection

by Tom Temple

29 March 2009, 11:55

Before I start talking about myself, let’s lay down the interesting material. I’ve been testing and profiling my web application (Digiyou) and to do that, I use a number of different browsers. I’ve tested Firefox 3, Internet Explorer 6, 7 and 8, Safari 3 and 4, and Google Chrome. I tested what ran in Windows and Mac.

Continue...

The "new" Tom Temple.net

by Tom Temple

16 March 2009, 15:44

At first I had just a plain HTML page. I was trying to be retro and all that. But that just wasn’t useful.

Switching to the other extreme, now I’ve got a full installation of Digiyou. The main thing that Digiyou does better than anything else is manage permissions. There is a fair bit of stuff that I want to share with you guys that is not appropriate for the web at large, and definitely not for places like Facebook that own your content even after you delete it.

So if any of you guys want to talk about, or upload content (e.g. pictures) that you don’t want everybody in the world to be able to see, you’re welcome to use it too.

Furthermore, if you want to be able to see stuff like my text and video application to be on CBS’s Amazing Race, drop me an email to request a username.

Before you move all of your research onto there though, I should point out that I’m using my development branch (Brayt: that means tom-01-013) and so I’m not making any promises about stability or uptime.

Coin Denominations

by Tom Temple

2 February 2009, 17:56

In a desperate effort to stem inflation President Imajarhead of Iran is issuing a new currency. For whatever reason, it is very important to him that he can make all possible change denomitations, from one centiroentgen up to ninety-nine, using at most two coins. His first idea was to have a one cR coin and then all of the evens. Although the person who told him that this was sub-optimal has been imprisoned, he had the sense to contact you, the well known Mathematician, to determine a set of denominations that requires the fewest distinct coins. What are they?

Bonus. Impressed by your quick success on the Iran job, the government of Japan contacts you to determine a minimum set for 1 to 999 rin.

Also, I’ve posted the solution to last weeks puzzle. Congrats to Liz for solving it and retaining a shred of her previous sanity.

David Bowie

by Tom Temple

20 January 2009, 15:20

Either you guys took THC off your RSS readers or last week was too abstract for the first time back. This should be more concrete1, which is not to say easier. If nobody answers this one, we’ll try easier.

Remember Labyrinth the tour de force by Jim Henson, George Lucas and David Bowie? At one point, the heroine was faced with two guards, one who always lied and another who always told the truth.

Imagine that you find yourself in the following, similar situation. Three guards block your path and will bar your way unless you can name them. You know that their names are Godel, Escher and Quine and that Godel always answers correctly, Escher always lies and Quine answers randomly. However, you do not know which is which. You may ask three yes/no questions, sequentially, to guards of your choice.

What do you do?

1 Ironically, while working on this problem, my advisor asked what I was working on and I had to come up with an equivalent abstract problem off the top of my head. I said something about model-diagnosis and finding a faulty device in a logic circuit.

Bonus: There is an even better version of this on Wikipedia with the title the hardest logic puzzle ever. In that problem, the guards answer in an unknown language with “da” or “ja” and you don’t know which is “yes” and which is “no”.

Solution:


No Title

  • Let Tn be the statement, “Person n always tells the truth.”

  • Let Fn be the statement, “Person n always lies.”

  • Let Xn be the statement, “Person n answers randomly.”


  • Let 4 be a universally true statment, e.g., “2 + 2 = 4”.

  • Let D be the statement, “ `Da’ means `True.’ “

  • For any statement S, S? denotes the question, “Is S true?”


Consider the question = “4 if and only if D?.” If “da” means “false”, then the statement is false and therefore the answer (if put to the honest person) would be “da.” If, on the other hand, “da” means “true,” then the statement is true and the answer will still be “da.”


Now consider the question “ 4 if and only if D?” If “da” means “true”, then the statement is false and the honest answer would be “ja.” If, on the other hand, “da” means “false”, then the statment is true and the answer would still be “ja.”


You can see that if we ask “S? if and only if D?”, we can pretend that we simply asked S? and interpret “da” to be “true” and “ja” to be “false.” Hitherto, I will strip this and assume that the people answer in English.


What makes the problem tricky is that you might ask your first question to the random guy. So it would be logical to assume that our second question will be to somebody different than the first question. It would be nice if the second question were surely put to someone other than the random guy. That would be some question, the answer to which has the following truth table. Assume that we ask the first person.






123
TFXT
TXFF
FTXT
FXTF
XTFT/F
XFTF/T


If the answer is “True,” then we know that the second person is not random and if it is “False,” we know that the third is not random. Now let’s try to come up with such a question.


Consider the statement “F2 and X3.” hitherto abrevieated F2X3.
Consider also the statement X2T3. Finally consider “F2X3 or X2T3“ hitherto abreviated F2X3+X2T3.




123F2X3 X2T3 F2X3+X2T3
TFXTFT
TXFFFF
FTXTTT
FXTTFF


Which is that for which we were looking.


So now we’ve identified a person who is surely not random and we still have two questions left. It should be pretty easy from here. We can simply ask the non-random person X1? and 4? and that will unambiguously identify the case.


For completeness, let’s write out what I would actually say for the first question.

Is it the case that,


  • person two is the liar and,

  • person three is random



           or,

  • person two is random and,

  • person three is always truthful



if and only if

  • “da” means “true?”


Liz came up with a terse and elegant version of the same question, “If asked [4], would person three be more likely to say `da’ than person two?” As a result, she is now tied for second place with 4 points.




File translated from
TEX
by
TTH
,
version 3.85.
On 2 Feb 2009, 15:30.