Monday, March 17, 2008

The Broken Remote Problem

This year I wrote one of the problems on the Univ of MD High School Programming Contest. The following conversation did not take place but could have.

BEGIN

BILL: Here is my problem. Imagine that you have a remote control for a TV set but that only a few of the numbers work. Also the UP-ONE and DOWN-ONE buttons work. Write a program that, given which numbers are available, and given x and y, return the sequence of botton pushes that get you from x to y in the least number of pushes. (NOTE- this description is incomplete- see problem 7 for a formal description.)

PROGRAM COORDINATOR: Is this some sort of Ramsey Thing in disguise?

BILL: No.

PROGRAM COORDINATOR: Then how did you think of it?

BILL: The remote at my in-laws only had 4 and 5 and UP and DOWN working.

END

The Broken Remote problem is not hard in that it does not need cleverness. But there alot of details to get right. Only 2 schools got the problem; however, the reason might be because problem 3 was harder than anticipated, hence some did not get to problem 7.

The point of all this?- similar to this post- everyday situations can inspire a math or comps sci problem.

Is the problem original? Hard to define what ``original'' means; however, I would not be surprised if it a similar problem appeared in some other contest.

No comments:

Post a Comment