Thursday, October 14, 2010

How hard is this problem?- I ask this non-rhetorically

I recently saw the following puzzle:

Which two numbers come at the end of this sequence? (That is, what are x and y?)
2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,x,y
(NOTE ADDED LATER- I had a typo in this post, the worst kind of typo one could have- I had a 5 instead of a 6. I looked up the original source and they had the same typo. SORRY!)

I could not figure it out. I went to the sequence-website which gave me the answer. Before the web I would not have been able to do this and I may have had to wait until there was a web to look it up on in order to solve it. Or maybe I could have solved it, though seeing the solution I doubt that.

How hard is this problem? How to tell how hard it is? How well known is this puzzle? YOU can help me!
  1. Try to solve it without using any other resources.
  2. Leave a comment either saying either I solved it without any help OR I was unable to solve it OR I knew how to solve it since I already saw it.
  3. Please do not include the solution. I will not post a solution--- if you are curious just type it into the sequence website.
  4. Please do not lie. I want to use this to judge how hard this problem is.

68 comments:

  1. Shouldn't the 5 be a six? I was not able to solve it, but I only spend about 20 sec. on it, before looking up the solution.

    ReplyDelete
  2. These kind of problems are not hard, they are stupid.You can give a reasonable explanation for all values of x,y.

    My favourite example is 1,2,4,8,16,x, where x=31 (A000127 in sloane's encyclopedia) is as good as x=32.

    ReplyDelete
  3. I solved it.

    I disagree with Anonymous 2: recognising patterns is an important part of being human, even if you can come up with alternative suggestions.

    There is something called science: you come up with a hypothesis for the next term and test whether it works. If not, you know you're wrong.

    ReplyDelete
  4. Groan. I hate puzzles that lie about their own rules.

    ReplyDelete
  5. I don't know but it reminds of another difficult one:

    10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, ?, 100, 121, 10000

    ReplyDelete
  6. Here is a good one:
    125, 116, 110, 103, 96, 86, 79, 72, x, y.


    What are x and y?









    x = Lincoln Center
    y = Columbus Circle

    ReplyDelete
  7. I agree with anon 2. Look, there are infinitely many functions which go through these points. What are we trying to do? Are we trying to come up with the function which has the smallest or simplest description and run it to see what are the next points?

    What does a pattern mean here? Do you want me to train a numeral network based on so little data? These kind of questions are just not questions, and there is not much fun in trying to guess what another person has in her mind.

    ps: Bill, it would be nice if you include a link to this "the sequence website". It seems that Google has a different opinion about what is *the* sequence website.

    ReplyDelete
  8. Um, dude? Before the web? There were sequence *books*. They were in lexicographic order and you could find hundreds of sequences.

    ReplyDelete
  9. i'm finding harder to find THE sequence website.

    ReplyDelete
  10. Agree with Anon 2 -- you can find formulas to justify any number as the solution to x and y. In which case, these kinds of sequence-completion problems should say, "Find the next number in the sequence with the easiest explanation", Which is itself fraught with all kinds of problems. For one thing, if the problem is too "hard", then you're perfectly justified to simply give up and say your favorite number as the next value.

    See also "The strong law of small numbers".

    ReplyDelete
  11. "The Sequence Website" is the next blockbuster movie to cash in on the success of "The Social Network". It shows the true origins and motivations behind the web phenomenon that we all use every day. Apparently Neil Sloan is really not happy with John Malkovich's portrayal of him.

    ReplyDelete
  12. sequence website link?

    ReplyDelete
  13. I couldn't "solve" it (only tried for 10s) OR find "THE sequence website"

    OEIS does not recognize this sequence.

    Someone post a link please?

    ReplyDelete
  14. The sequence website is "The On-Line Encyclopedia of Integer Sequences™". If you haven't seen it before, you are about to waste some time there.

    ReplyDelete
  15. Yes, I'm pretty sure the 5 should be a 6.

    ReplyDelete
  16. YES- the 5 should be a 6.

    MUCH apologies about that- this is the worst typo I have ever made.

    ReplyDelete
  17. I couldn't think of it in sixty clock-ticks, so I found it via yahoo. Contrary to anonymous 2, (who said it's "stupid") and 3 ("not much fun"), it was fun for this math guy to find out about.

    P.S. This post fits with that run of digits in a particular way... What is it?

    ReplyDelete
  18. The pattern was super easy.
    I had the next two numbers in less
    than a minute.

    Then I looked up the solution just to verify and of course I was completely wrong and there's nobody around here to argue with so that's that.

    ReplyDelete
  19. I couldn't find it, which did not surprise me when I saw the solution.

    In the other had, Euclid would never be able to solve it, therefore...

    ReplyDelete
  20. Micki- I would be curious what you
    THOUGHT it was- please email me
    so as to not give the answer away
    to anyone else (your wrong answer
    may still give things away).

    GASARCH

    ReplyDelete
  21. I could not solve it and looked for the solution. I do love to solve sequence, but these types of sequence frankly I dont like, where the rule is not "entirely" mathematical. In short I prefer if the terms comes out of some mathematical operations.

    ReplyDelete
  22. x = sqrt{2} i, y is the tuple (matrix,graph): ((0,1),(12,3i)), K_15

    Sorry, but this is one of my favorite sequences. I couldn't help posting the answer!

    ReplyDelete
  23. any finite prefix of an infinite sequence is irrelevant so x and y can be anything

    ReplyDelete
  24. Recognizing patterns is one thing, but saying that one of them is right and others wrong seems absolutely inappropriate.

    ReplyDelete
  25. For an analytic solution: http://www.wolframalpha.com/input/?i=2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62

    ReplyDelete
  26. Re Anonymous #6:

    I liked your puzzle, but I think it's a bit wrong. It could easily continue 66 and then 59. If you take every station that has a "name", then 116 would be "Columbia University". If you take every station where the name is more prominent than the street number, then 110 would be "Cathedral Parkway" and every other station would be the number.

    There's surely a good, valid sequence along these (subway) lines.

    ReplyDelete
  27. These sequence puzzles are about Kolmogorov complexities, i.e. what would x & y have to be so that the whole string is compressible.

    (Of course there's an additive constant depending on the chosen TM, and when you require knowledge of radiology or street numbers in Manhattan, people do get mad.)

    I also hate these puzzles.

    ReplyDelete
  28. x%2=0,030(base 8).

    I think it's just as good an answer as the official one.

    ReplyDelete
  29. Think the comments mistook the symbols for tags. In text:

    x%2=0, x between (0,7) or greater than 20 (in base 8)

    ReplyDelete
  30. Glad to see my eban number sequence getting some press. This is A006933 in the OEIS, and the best URL is http://oeis.org/classic/
    Neil Sloane

    ReplyDelete
  31. Thought about it for 10 minutes and generate lots of wrong ideas that weren't even close. Looked it up. Never would've thought of that; brain was in a different zone.

    ReplyDelete
  32. I've seen similar things before, and was on the right track, but got annoyed and gave up before I actually solved it because I don't like word problems.

    ReplyDelete
  33. Shouldn't math transcend the limitations of the English language (or any other arbitrary language?)

    ReplyDelete
  34. As a non-native English speaker this was impossible to have guessed. I spent about 10 minutes on it before falling to my knees.

    ReplyDelete
  35. I got x, but was very wrong with y. Looking at the answer, I was no where on the right track.

    However, I spent the most time on trying to find the so-called Sequence site.

    ReplyDelete
  36. I couldn't solve it, but after looking at the solution I think it's a fair and interesting problem.

    ReplyDelete
  37. 66, 70

    without looking anything up.
    I'm seeing the first group as 0,2 4 6, then jumps to 30, 32, 34,36, but then goes 40... 50...60... so i'm not sure for the jump from 0x to 3x
    so now that I post this i'll look at comments

    ReplyDelete
  38. My experience was similar to other posters: I had a guess that worked in about 30 seconds, but it was not the 'correct' one.

    I don't think I ever would have come to the 'correct' answer. I automatically assume the pattern sought in an integer sequence is based on the numbers' numerical properties. As such I would wager the 'problem' is impossible.

    Personally, I abhor these kind of 'math' riddles. They are about as clever as Joy Buzzers.

    2,3,10,12,13,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,200,201,202...

    7,13,14,15,16,18,19,20,30,40,50...

    11,17,21,22,23,24,25,26,28,29,31,32,33,34,35,36,38,39,41...

    1,2,4,5,8,40,1000,1001,1002,1004...

    ReplyDelete
  39. Solved it without any help.

    ReplyDelete
  40. I am a non-native speaker and I could solve it immediately - although I have seen similar puzzles.

    ReplyDelete
  41. I could not figure out it out.

    ReplyDelete
  42. I could only solve it the way wolfram alpha did (without looking it up there).

    ReplyDelete
  43. wait so why shouldn't we invest into china and why should be avoid itcs tsinghua for postdocs again ?

    coz of bad management ?
    coz it violates every definition of human rights ?
    coz ppl there are hippo-crits

    ReplyDelete
  44. My name is Vinay and I could istantly solve it. Trust me, I work for HP! I am a honourable, trustworthy man.

    ReplyDelete
  45. Are these all numbers that don't have an "e" in English spelling?

    ReplyDelete
  46. I was unable to solve it.

    ReplyDelete
  47. I was unable to solve it.
    I know an interesting anecdote related to the problem. Warning:
    It contains MAJOR SPOILERS about the problem. I posted it as a comment here:

    http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html

    ReplyDelete
  48. I solved it without any help

    ReplyDelete
  49. Could not figure it out in five minutes ... was annoyed when I looked up the "algorithm" ... (because it was unlikely to be of further utility in the enterprises that I care about).

    On the other hand, certainly there are some mathematical jobs where this problem (or a similar one) might legitimately be posed on a job interview or aptitude test.

    Within the context of such an aptitude examination, pretty much any mathematician's chances of solving this particular problem would be enhanced ...

    ... and so perhaps this is one of the (many) mathematical questions regarding which a diversity of opinion is to be expected and welcomed.

    ReplyDelete
  50. Laslo Lovasz wins the Kyoto prize!

    ReplyDelete
  51. I couldn't solve it.
    Never seen this type of puzzle! Was on a completely wrong track!

    ReplyDelete
  52. 66,70.

    look at the last digts always. 0 2 4 6
    the first digits increase from one to one.

    60,62,64,66,70

    if this is really the answer, I saw it in 10 sec :)

    ReplyDelete
  53. "if this is really the answer, I saw it in 10 sec :)"

    it isn't the answer

    ReplyDelete
  54. I have a general question.

    Why does the overall quality of a blog decline as time progresses ? I mean, look at this block, some of the comments are funny while others are clearly meant to instigate chaos in my home country china. WE CHINESE DO NOT ALLOW FOREIGNERS TO INTERVENE IN OUR INTERNAL AFFAIRS, DONT U UNDERSTAND ? IT IS OUR COUNTRY AND FOREIGNERS DONT UNDERSTAND US.

    I mean how could they understand tian-an-men square incident where we gave orders to wheel tanks over our very own children and then are ashamed to admit such an incidence thus eradicate any documents pertaining to that event. How could foreigners understand this ? They don't. Tiananmen Square never happened. Taiwan is part of mainland china and the U.S. can't do anything about it. We will lurke the Taiwanese into mainland china. We have our own devilous tactics.

    And Tibet will always be suppressed by china, coz we are the stronger nation. We will never grant them any human rights. It's own triple T secret society.

    ReplyDelete
  55. bravo, to moderation! now we will have to wait decades for comments to appear.

    moderation hampers the natural flow of evolution.

    ReplyDelete
  56. moderation is not free market oriented i am unsure whether this will be as good as it is believed to be.

    ReplyDelete
  57. lance and bill are a mathematician so obviously he knows what he id doing when he moderates aka they are objective either way.

    but please bill, can you block more or tell us whether you are busy nowadays. what's going on ? and lance has promised us updates on his book progresss .... wat's going on there ?

    ReplyDelete
  58. x=1/3
    y=pi

    What do you mean it's not an 18th-degree polynomial?

    ReplyDelete
  59. My great Niece guessed 2000 (the correct next value) and 2002 (the correct next
    value after that).

    How did she do that?

    I do not know.

    GASARCH

    ReplyDelete
  60. I guessed right, but after considerable trial and error. I tried virtually everything I could think of before I started writing the numbers out in English..I am not entirely sure what is the use of this I am also not sure how this problem could be classified as hard/easy? This problem may be extraordinarily hard
    (if we are only looking at eban) for someone who is not familiar with English.

    ReplyDelete
  61. I cant solve it.

    ReplyDelete
  62. One of my bright High School Students
    got it right with the hint
    `This puzzle is really stupid.''

    ANYWAY, based on all of your responses
    I think we conclude that this is a hard puzzle. Whether or not it is a stupid one is a matter of opinion.

    ReplyDelete
  63. When I first saw this puzzle, my mathematical mind was stumped -- I couldn't even think of a hypothesis to try. Two hours later, I happened to think of it again, and the right idea popped into my head. Sometimes it helps to take a break.

    Some people would call this an exercise in creative thinking. In my case, I think it was more a function of what kinds of similar puzzles I had been exposed to in the past.

    ReplyDelete
  64. I think the difficulty of this problem is to some degree a question of learning theory (and then a question of human communication). The problem is one of finding a hypothesis that describes the examples that we're presented with and generalizes to unseen examples. As we all know, if the complexity of the hypothesis space is virtually unbounded, the problem is virtually impossible.

    Here the problem can be posed in a natural and simple hypothesis space. After all there is a very small FSA that decides membership in the sequence, were the sequence written out in English. The difficulty comes from subtly suggesting the wrong hypothesis space. The problem is posed in a mathematical language and in a mathematical context, which suggests the usual hypothesis space for these sequence problems: simple algebraic functions. Even extensions of this space however will lead you nowhere - any valid description is ridiculously complicated. Were the problem posed as a membership question in a sequence of strings, then we would have the right hint as to what kind of pattern we're looking for.

    So in a few words, the difficulty comes from posing the question in one language (by writing out the sequence in digits) even though the simplest correct hypothesis works on a "translation" (and an entirely human one) into another language.

    ReplyDelete
  65. tabish- that is not the answers the maker of the problem had in mind. The sequence is the list of all numbers that, when written in English, do not have the number e in them.

    The answer is quite large.

    ReplyDelete
  66. "What are x and y?"

    Well, x and y are two letters of the alphabet of course! The numeric representation in ASCii is X=120 and y=121.

    ReplyDelete
  67. found the answer in one of the sequence website. :( after 15mins of thinking.

    ReplyDelete