Official xkcd puzzle [solution]

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Erasmus
Posts: 26
Joined: Wed Sep 27, 2006 10:13 am UTC

Official xkcd puzzle [solution]

Postby Erasmus » Fri Jan 19, 2007 8:49 am UTC

So, this solution is more of a "I'm not happy with the requirements for success," than a serious solution.

For 0 <= n <= 35, and for n = 71, define F(n) as in the problem description.
For 35 < n < 71, and for n > 71, let F(n) = smallest positive integer not in { F(0), ..., F(n-1) }.

Using this algorithm, we get

F(36) = 32
F(37) = 33
F(38) = 34
...
F(45) = 41

After a while, F turns into the identity function, and F(31337) = 31337.

The issue here is that there should be infinitely many functions F that satisfy your demands. We can generate them by picking what you think is the right answer, and then just permuting the values you didn't specify.

So basically, I guess you shouldn't accept the first solution -- if you do, then this ridiculous thing is the first solution -- or, you should add stricter criteria for success.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Postby Cosmologicon » Fri Jan 19, 2007 10:13 am UTC

So... here's a pretty general rant about this sort of thing. Some people criticize the sort of pattern-finding problems we see in the integer sequence posts to this forum and some intelligence tests. "There are an infinite number of possible sequences!" they claim, technically correct in a missing-the-whole-point sort of way. But the object is not to find the unique solution; the object is to find the best solution.

Far from being artificial, or something people of rigorous mind would not deal with, this sort of thing comes up all the time in math and science. For instance, the value of a geometric series can be written:

1 + r + r^2 + r^3 + ... = 1 / (1 - r)

What sort of mathematician would you be if you insisted that the left-hand-side is not well defined, that there are an infinite number of series that start thus? Do you think other mathematicians would consider you terribly clever for pointing that out?

The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind inductive reasoning. It's possibly the most important skill in all of science. So when it's obviously a crucial piece of a question that gets asked, don't go ignoring it by saying that "stricter criteria" are needed, huh?

Edit: deductive -> inductive. I always get those mixed up; thanks for pointing it out! :)
Last edited by Cosmologicon on Fri Jan 19, 2007 7:39 pm UTC, edited 1 time in total.

Erasmus
Posts: 26
Joined: Wed Sep 27, 2006 10:13 am UTC

Postby Erasmus » Fri Jan 19, 2007 5:10 pm UTC

Cosmologicon wrote:But the object is not to find the unique solution; the object is to find the best solution.


That's sort of the point of my post? That maybe it's inappropriate to award both the first response and the best response, since the first response is trivial.

Aside from that, I don't think my post is totally useless. It runs in O(n²) time -- if another proposed algorithm isn't asymptotically faster than mine, it's probably not the "best" solution. In that way, my "solution" is a benchmark for others, no?

The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind deductive reasoning.


I would have called that "inductive reasoning" -- obviously such integer-sequence problems, like science, suffer from the problem of induction -- but to each his own.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Postby GreedyAlgorithm » Fri Jan 19, 2007 5:23 pm UTC

Erasmus wrote:I would have called that "inductive reasoning" -- obviously such integer-sequence problems, like science, suffer from the problem of induction -- but to each his own.

I'd say definitely not to each his own. It's inductive reasoning, like pretty much all of science, not deductive.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

e-Gor
Posts: 3
Joined: Tue Jan 16, 2007 10:43 pm UTC

Postby e-Gor » Fri Jan 19, 2007 7:08 pm UTC

ok, despite all that discussion I went ahead and tried it.

[edit] removed - I broke something. I'll try and fix it tomorrow...[/edit]

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby skeptical scientist » Fri Jan 19, 2007 7:28 pm UTC

Erasmus wrote:
Cosmologicon wrote:But the object is not to find the unique solution; the object is to find the best solution.


That's sort of the point of my post? That maybe it's inappropriate to award both the first response and the best response, since the first response is trivial.

Aside from that, I don't think my post is totally useless. It runs in O(n²) time -- if another proposed algorithm isn't asymptotically faster than mine, it's probably not the "best" solution. In that way, my "solution" is a benchmark for others, no?

The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind deductive reasoning.


I would have called that "inductive reasoning" -- obviously such integer-sequence problems, like science, suffer from the problem of induction -- but to each his own.

Actually, your algorithm runs in O(1) time as you need only check that your input is a least 71 (O(1) time) and if it is, you don't need to do anything to output the input. Any similar algorithm will do the same. The judge of how good a solution is should not be it's computing time, but rather how simple it is to describe the algorithm, and you should be able to describe it without breaking it down into cases, unless the cases are all infinite, and not complicated (for example do x if n<100, otherwise do y is not a good solution, but do foo if n is even, and do bar if n is odd might be),
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
BaldAdonis
Posts: 81
Joined: Fri Nov 24, 2006 11:32 pm UTC

Postby BaldAdonis » Sat Jan 20, 2007 12:59 am UTC

Didn't mean to hash this all up again. There is already an extensive solution thread. I just wanted to know which was deemed the most elegant.

User avatar
Framling
Posts: 62
Joined: Sat Dec 02, 2006 6:58 am UTC

Postby Framling » Sat Jan 20, 2007 7:45 am UTC

Cosmologicon wrote:So... here's a pretty general rant about this sort of thing. Some people criticize the sort of pattern-finding problems we see in the integer sequence posts to this forum and some intelligence tests. "There are an infinite number of possible sequences!" they claim, technically correct in a missing-the-whole-point sort of way. But the object is not to find the unique solution; the object is to find the best solution.

Far from being artificial, or something people of rigorous mind would not deal with, this sort of thing comes up all the time in math and science. For instance, the value of a geometric series can be written:

1 + r + r^2 + r^3 + ... = 1 / (1 - r)

What sort of mathematician would you be if you insisted that the left-hand-side is not well defined, that there are an infinite number of series that start thus? Do you think other mathematicians would consider you terribly clever for pointing that out?

The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind inductive reasoning. It's possibly the most important skill in all of science. So when it's obviously a crucial piece of a question that gets asked, don't go ignoring it by saying that "stricter criteria" are needed, huh?

Edit: deductive -> inductive. I always get those mixed up; thanks for pointing it out! :)


So in my final year of college, I took a math elective on Knot Theory. One day we were talking about crossing numbers, particularly the number of distinct prime knots with a given crossing number. Our book had a table giving the counts up through seventeen or something (I really don't remember specifics) and a few of us got on the subject of trying to determine the next in the series.

There was a group of freshmen that decided to try to tackle the exercise by doing some kind of statistical analysis of some sort, I don't really remember. But I was taking a numerical analysis class that semester, so I interpolated all the data points and the next day at class, told everyone about how I had "noticed" that all the data points happened to conform exactly to a simple sixteenth-degree polynomial (with ten- or twenty-digit coefficients, of course).

It was pretty hilarious.
your = belonging to you
you're = you are
their = belonging to them
they're = they are
there = not here

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby skeptical scientist » Sat Jan 20, 2007 9:00 am UTC

Framling wrote:There was a group of freshmen that decided to try to tackle the exercise by doing some kind of statistical analysis of some sort, I don't really remember. But I was taking a numerical analysis class that semester, so I interpolated all the data points and the next day at class, told everyone about how I had "noticed" that all the data points happened to conform exactly to a simple sixteenth-degree polynomial (with ten- or twenty-digit coefficients, of course).

It was pretty hilarious.

Indeed, that is quite an observation you made about that particular sequence. I'm not surprised they were astonished.

On the subject of astonishing mathematical properties, did you know that the French Curve, which is commonly used in drawing, has the interesting property that the tangent at the lowest point, however it is oriented, is horizontal?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Postby jestingrabbit » Sat Jan 20, 2007 9:45 am UTC

skeptical scientist wrote:
Framling wrote:There was a group of freshmen that decided to try to tackle the exercise by doing some kind of statistical analysis of some sort, I don't really remember. But I was taking a numerical analysis class that semester, so I interpolated all the data points and the next day at class, told everyone about how I had "noticed" that all the data points happened to conform exactly to a simple sixteenth-degree polynomial (with ten- or twenty-digit coefficients, of course).

It was pretty hilarious.

Indeed, that is quite an observation you made about that particular sequence. I'm not surprised they were astonished.

On the subject of astonishing mathematical properties, did you know that the French Curve, which is commonly used in drawing, has the interesting property that the tangent at the lowest point, however it is oriented, is horizontal?


Hey! Stop plagiarising Feynman!!

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby skeptical scientist » Sat Jan 20, 2007 9:49 am UTC

jestingrabbit wrote:Hey! Stop plagiarising Feynman!!

That wasn't plagiarism, it was a deliberate reference that I figured about 90% of this forum would get.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Postby jestingrabbit » Sat Jan 20, 2007 10:18 am UTC

skeptical scientist wrote:
jestingrabbit wrote:Hey! Stop plagiarising Feynman!!

That wasn't plagiarism, it was a deliberate reference that I figured about 90% of this forum would get.

And I was just trying to signal that I got the reference, sorry for coming across as a meanie.

Ronfar
Posts: 132
Joined: Mon Dec 04, 2006 6:04 am UTC

Postby Ronfar » Mon Jan 22, 2007 3:11 am UTC

I see the pattern; I don't know if it has a simple formula, though.

Here's a complex formula:

Define ancillary function g(x) as:
If (int(x)) modulo 4 = 0, then g(x) = 0.
If (int(x)) modulo 4 = 1, then g(x) = 1.
If (int(x)) modulo 4 = 2, then g(x) = 3.
If (int(x)) modulo 4 = 3, then g(x) = 2.
Then f(x) = g(x) + 4g(x/4) + (4^2)g(x/4^2) + (4^3)g(x/4^3) + ...

Edit: Never mind, I misread the sequence. Gotta work harder.
Last edited by Ronfar on Mon Jan 22, 2007 6:56 am UTC, edited 1 time in total.
- Doug

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Postby Cosmologicon » Mon Jan 22, 2007 5:53 am UTC

That formula looks pretty simple to me. But it gives f(4) = g(0) + g(1) = 1, doesn't it?

Ronfar
Posts: 132
Joined: Mon Dec 04, 2006 6:04 am UTC

Postby Ronfar » Mon Jan 22, 2007 6:50 am UTC

Cosmologicon wrote:That formula looks pretty simple to me. But it gives f(4) = g(0) + g(1) = 1, doesn't it?


Whoops! I messed up. I gotta fix that. But my idea was wrong anyway.
- Doug


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests