Official xkcd puzzle, free shirts for solutions

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Prelates, Moderators General

Official xkcd puzzle, free shirts for solutions

Postby xkcd » Sat Dec 09, 2006 6:37 am UTC

N, F(N) in binary, F(N) in decimal
0 000000 0
1 000001 1
2 000011 3
3 000010 2
4 001000 8
5 001010 10
6 001011 11
7 001001 9
8 001100 12
9 001110 14
10 001111 15
11 001101 13
12 000111 7
13 000110 6
14 000100 4
15 000101 5
16 010000 16
17 010010 18
18 010011 19
19 010001 17
20 010100 20
21 010101 21
22 010111 23
23 010110 22
24 011100 28
25 011101 29
26 011111 31
27 011110 30
28 011011 27
29 011001 25
30 011000 24
31 011010 26
32 110000 48
33 110010 50
34 110111 51 (not 55)
35 110101 49 (not 53)

. . .

71 10000110 134

edit: Crap. The last two numbers were indeed wrong. Thanks for catching that, all, and sorry if you were led down the wrong track. I'm not sure how it happened -- I did this on paper/in notepad, but I did the same thing everywhere. Must've hit a key wrong somewhere :/

Come up with an algorithm to generate the Nth number in this sequence. Post the algorithm, along with the next 10 numbers and the 31337th number why not. If multiple algorithms are posted that work, the one that is the most elegant wins.

The free xkcd shirts will be given out for the first and the best solution. They will depend on me having shirts you want in stock, so they may be slightly delayed what with the holidays. (This is a pretty informal thing. We're all friends here?)

Feel free to pass this around. I'd really like to see a simple, iterative solution.

(Technical note -- the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function -- it's a complete one-to-one mapping.)
User avatar
xkcd
Site Ninja
 
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC

Postby java » Wed Dec 13, 2006 8:07 am UTC

Hm... no offense, but I wouldn't use the words one-to-one mapping, since doesn't that imply only an injection? Or am I mixing my terms up again?

-java
java
 
Posts: 33
Joined: Wed Aug 30, 2006 4:57 pm UTC

Postby Token » Wed Dec 13, 2006 11:11 am UTC

"One-to-one" and "one-one" generally mean injective and bijective, but which is which depends entirely upon to whom you are talking, and it makes much more sense to use neither term but to explicitly state whether you mean injective or bijective.
Token
 
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Postby Cosmologicon » Wed Dec 13, 2006 3:19 pm UTC

"One-to-one function" does mean only injection, yes, but "complete one-to-one function" must mean bijection, right? Although I guess the normal term is "onto", what else can "complete" mean?
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Postby BaldAdonis » Fri Jan 19, 2007 5:48 am UTC

So..... who won?
User avatar
BaldAdonis
 
Posts: 81
Joined: Fri Nov 24, 2006 11:32 pm UTC

Re: Official xkcd puzzle, free shirts for solutions

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

xkcd wrote:(Technical note -- the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function -- it's a complete one-to-one mapping.)


Sounds like you've described it to be a surjection, not a bijection. For any function f, for any x in the domain of f, there is only one value of f(x) -- that's what makes it a function. The fact that every integer is generated by F makes F surjective. If F is also injective -- every F(N) has one N -- then it's bijective.
Erasmus
 
Posts: 26
Joined: Wed Sep 27, 2006 10:13 am UTC

Postby Toeofdoom » Fri Jan 19, 2007 9:00 am UTC

So, the idea is we basically make a function F(N) that fits all the criteria and what, uses one general rule? not some thing where it treats different values of N differently?

Also im wondering why theres binary :p hmmm...

K... looking at a bit of a pattern here... or multiple patterns. still dont get it though.

EDIT: k, i think me and my brother have got F(40) and F(42)... (mainly my work of course ... :P)

and we will continue to poke this puzzle alot.

Do you actually have an answer to this btw? I mean it would be cool if we could atleast check those 2 answers... heh :P
User avatar
Toeofdoom
The (Male) Skeleton Guitarist
 
Posts: 3446
Joined: Wed Jan 10, 2007 10:06 am UTC
Location: Melbourne, Australia

Re: Official xkcd puzzle, free shirts for solutions

Postby jestingrabbit » Fri Jan 19, 2007 9:35 am UTC

Erasmus wrote:
xkcd wrote:(Technical note -- the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function -- it's a complete one-to-one mapping.)


Sounds like you've described it to be a surjection, not a bijection. For any function f, for any x in the domain of f, there is only one value of f(x) -- that's what makes it a function. The fact that every integer is generated by F makes F surjective. If F is also injective -- every F(N) has one N -- then it's bijective.


It sounds like a bijection to me, especially given the use of the word 'one'.
User avatar
jestingrabbit
 
Posts: 5585
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Official xkcd puzzle, free shirts for solutions

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

jestingrabbit wrote:It sounds like a bijection to me, especially given the use of the word 'one'.


Consider f(x) = x^2. For every x, there is exactly one f(x); but f is not a bijection.

This isn't just pedantic (even though it is mostly pedantic). Certainly the function is injective in the places it's defined for us, so perhaps it's safe to assume that it's injective on its entire domain... but perhaps not?
Erasmus
 
Posts: 26
Joined: Wed Sep 27, 2006 10:13 am UTC

Postby Cosmologicon » Fri Jan 19, 2007 7:41 pm UTC

Well considering xkcd explicitly said it was injective (one-to-one), I'd say it's safe to assume it's injective.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Re: Official xkcd puzzle, free shirts for solutions

Postby beard0 » Wed Jan 24, 2007 9:13 pm UTC

xkcd wrote:34 110111 51 (not 55)
35 110101 49 (not 53)


I just wanted to check that when you made the correction, you just forgot to change the binary - the discrepancy isn't part of the problem, is it?
Who has been making grilled cheese sandwiches with the defibrillator paddles?
-Delores Herbig
User avatar
beard0
 
Posts: 21
Joined: Wed Jan 17, 2007 5:17 am UTC
Location: Ottawa

Re: Official xkcd puzzle, free shirts for solutions

Postby kmill31415 » Fri Oct 05, 2007 7:23 am UTC

beard0 wrote:
xkcd wrote:34 110111 51 (not 55)
35 110101 49 (not 53)




I just wanted to check that when you made the correction, you just forgot to change the binary - the discrepancy isn't part of the problem, is it?


No, he just made a mistake. The binary should be 110011 and 110001 otherwise the sequence makes no sense.

Toeofdoom wrote:EDIT: k, i think me and my brother have got F(40) and F(42)... (mainly my work of course ... :P)


I believe I found an actual function for evaluating the sequence, and I found that F(40) = 60 and F(42) = 63
kmill31415
 
Posts: 2
Joined: Fri Oct 05, 2007 7:17 am UTC

Re: Official xkcd puzzle, free shirts for solutions

Postby Yakk » Tue Oct 09, 2007 7:26 pm UTC

Spoiler:
Code: Select all
0:   00 00 00:   00 00 00:   0:   B A B A
1:   00 00 01:   00 00 01:   1:   B A B A
2:   00 00 10:   00 00 11:   3:   B A B A
3:   00 00 11:   00 00 10:   2:   B A B A

4:   00 01 00:   00 10 00:   8:   B A B A
5:   00 01 01:   00 10 10:   10:   B A B A
6:   00 01 10:   00 10 11:   11:   B A B A
7:   00 01 11:   00 10 01:   9:   B A B A

8:   00 10 00:   00 11 00:   12:   B A B A
9:   00 10 01:   00 11 10:   14:   B A B A
10:   00 10 10:   00 11 11:   15:   B A B A
11:   00 10 11:   00 11 01:   13:   B A B A

12:   00 11 00:   00 01 11:   7:   B A B C
13:   00 11 01:   00 01 10:   6:   B A B C
14:   00 11 10:   00 01 00:   4:   B A B C
15:   00 11 11:   00 01 01:   5:   B A B C

16:   01 00 00:   01 00 00:   16:   B A A A
17:   01 00 01:   01 00 10:   18:   B A A A
18:   01 00 10:   01 00 11:   19:   B A A A
19:   01 00 11:   01 00 01:   17:   B A A A

20:   01 01 00:   01 01 00:   20:   B A A A
21:   01 01 01:   01 01 01:   21:   B A A A
22:   01 01 10:   01 01 11:   23:   B A A A
23:   01 01 11:   01 01 10:   22:   B A A A

24:   01 10 00:   01 11 00:   28:   B A A A
25:   01 10 01:   01 11 01:   29:   B A A A
26:   01 10 10:   01 11 11:   31:   B A A A
27:   01 10 11:   01 11 10:   30:   B A A A

28:   01 11 00:   01 10 11:   27:   B A A C
29:   01 11 01:   01 10 01:   25:   B A A C
30:   01 11 10:   01 10 00:   24:   B A A C
31:   01 11 11:   01 10 10:   26:   B A A C

32:   10 00 00:   11 00 00:   48:   B A A A
33:   10 00 01:   11 00 10:   50:   B A A A
34:   10 00 10:   11 00 11:   51:   B A A A
35:   10 00 11:   11 00 01:   49:   B A A A

...

71:   01 00 01 11:   10 00 01 10:   134:   B A A A


Binary maps:
MapA:
00 -> 00
01 -> 01
10 -> 11
11 -> 10

MapB:
00 -> 00
01 -> 10
10 -> 11
11 -> 01

MapC:
00 -> 11
01 -> 10
10 -> 00
11 -> 10

Step 1: Convert to base 4. Each digit is a 4^N digit.

Step 2: Pick a map for each digit.
For each 4^N digit:
If N == 0 and the 4^1 digit is 3, use map C.
If there is a 4^{N+1} digit, use map A.
If there isn't a 4^{N+1} digit and N is odd, use map B.
Otherwise, use map A.

Step 3:
Run each map on each digit.

Using the above algorithm, the values of 36 .. 45 are thus:
Code: Select all
36:   10 01 00:   11 01 00:   52
37:   10 01 01:   11 01 01:   53
38:   10 01 10:   11 01 11:   55
39:   10 01 11:   11 01 10:   54
40:   10 10 00:   11 11 00:   60
41:   10 10 01:   11 11 01:   61
42:   10 10 10:   11 11 11:   63
43:   10 10 11:   11 11 10:   62
44:   10 11 00:   11 10 00:   56
45:   10 11 01:   11 10 10:   58


And the value of 31337 is:
Code: Select all
31337:   01 11 10 10 01 10 10 01:   01 10 11 11 01 11 11 01:   28541


Now I have no idea if this is what you where aiming for, but heck, it matches the displayed stuff, and is pretty simple to implement.

It also lines up with kmill's claims about 40 and 42. Interesting.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10439
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Official xkcd puzzle, free shirts for solutions

Postby charonme » Sun May 18, 2008 11:41 am UTC

so was there found a more elegant solution? is it still open?
charonme
 
Posts: 141
Joined: Sun May 18, 2008 11:18 am UTC

Re: Official xkcd puzzle, free shirts for solutions

Postby jestingrabbit » Sun May 18, 2008 11:11 pm UTC

Its closed. The solution was pretty ugly.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5585
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Official xkcd puzzle, free shirts for solutions

Postby Cosmologicon » Mon May 19, 2008 3:20 am UTC

There's a solution thread. I don't know if anybody won per se.... I got a shirt out of it, but I don't know how many other people did.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA


Return to Logic Puzzles

Who is online

Users browsing this forum: No registered users and 2 guests