Search This Blog

25 December 2006

PizzaQ: Find Santa's shortest path on Christmas Eve!

click 2x is advised

Okay, here's the Christmas PizzaQ. 1/2 pepperoni.

Santa Claus must fly his sleigh of toys from the North Pole to 7 houses, visit each house only once, and then fly back to the North Pole.

On Santa's map, the Earth is Flat, and laid out in standard x,y coordinates, in kilometers.

The North Pole is at the center, at

x = 0
y = 0

Each house has a pair of x,y coordinates relative to the North Pole.

Because the Earth is flat, Santa always flies in a straight line between two points on the map.

Santa is in a hurry and doesn't want to fly around the Earth all week.

What's his shortest path on Christmas Eve?

An Answer should look like this:

nABCDEFGn
North Pole - Anna - Benjamin - Chloe - David - Eloise - Freddy - Gemma - North Pole

or

nCEAGBFDn
North Pole - Chloe - Eloise - Anna - Gemma - Benjamin - Freddy - David - North Pole

and the total length of the Route you think is the shortest:

21345.18 kilometers

Santa Claus / St. Nicholas / Father Christmas / Kris Kringle / Pere Noel / Sinterklaas / Der Weihnachtsmann
toy List / 24-25 December 2006

map coordinates
kilometers from 0,0 = North Pole

child ...... x ..... y . toy
========================================
....Anna -382.69 0104.47 Delft doll
Benjamin -922.59 -269.72 Space Ray Gun
...Chloe 0431.68 0222.36 iPod
...David -459.36 0389.88 Wii
..Eloise 0804.91 0546.52 Pony
..Freddy 0736.61 0796.63 Drums
...Gemma 0100.87 -389.71 Geiger Counter
========================================

5 comments:

Bob Merkin said...

Is it possible that this mathematical problem is beyond the skills of all readers of Vleeptron?

That's scary.

It's going to be early April before Anna, Benjamin, Chloe, David, Eloise, Freddy and Gemma get their presents.

RamanuJohn said...

nCEFDABGn
4887.891293962863 kilometers

Bob Merkin said...

wow.

Vleeptron confesses that, failing any answers from anybody on Planet Earth, I went into Undernet #math and bothered and harrassed that bunch and tried to shame somebody into trying to answer it.

Lo.

And it's The Right Answer!

Santa left the North Pole and flew to Chloe's house, then to Eloise's, then to Freddy's, David's, Anna's, Benjamin's and Gemma's, and then back to the North Pole, and the Trip Meter read 4887.89+ km, and there ain't no shorter way to do Christmas Eve 2006.

Of course Santa could do the same path backwards and that would also be the shortest path.

Uhh, Thanks ramanuhohn! you kick ass!

Shoulda said, but I was trying to design the problem so nobody had to mess with more than 2 decimal digits, but if u say the whole thang is 4887.891293962863 , that's fine with moi. You can place each child's toy to less than the width of 1 human hair with that kinda precision.

Vleeptron is deeply grateful and honored that ramanujohn has done this humble problem this honor.

so like rama ... where u from, who r u, nosy crap like that. no goddam robot solved this proble. you r a HUMAN BEING!

Also you have earned 1/2 of a pepperoni pizza to your account. shipping not included, but e-mail me if you're ever anywhere near Northampton or Amherst Massachusetts USA, you will get your well-won pizza! (And I know the best pizzerias in the Five College Area.)

Bob Merkin said...

rama -- share.

what lingo did you write your proggie in?

(or did you do it in your head, or just use a 4-banger calculator?)

have you taken a combinatorics course?

(do you teach a combinatorics course?)

write a brief bit about what the Travelling Santa Problem means to you. Was this your first TSP? Tell us some Advanced Stuph about the importance of TSP.

Are we not Men? Or Are we not Women?

Bob Merkin said...

now go here:

http://vleeptronz.blogspot.com/2006/12/ramanujohn-solves-santa-pizzaq.html