Exceptionally difficult questions

General chat, humour, riddles, logic/lateral/word puzzles...
Post Reply
wrongrook
Posts: 403
Joined: Sat Oct 17, 2009 10:39 pm

Exceptionally difficult questions

Post by wrongrook »

Out of curiosity I was wondering how often the Project Euler team comes across a question that:
1) is interesting and easy to explain
2) has a nice simple solution (e.g. 15 lines of Python)
3) is considered too hard to be used as a Project Euler problem(!)

It is simple enough to find questions that satisfy 2 properties, e.g. Project Euler is full of questions that satisfy 1 and 2, while mathoverflow is full of hard questions, often with simple solutions - but I can usually understand neither question nor answer :(

Or perhaps the limits on the question can normally be tuned to make the problem easy enough to be used?

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Exceptionally difficult questions

Post by hk »

If we come across a problem that nobody of us understands we can't develop it into a problem.
If we come across a problem that three of us understand we develop it into a problem that meets the criteria of Project Euler.
1) the one minute rule using a compiled language.
2) it can be solved without using arbitrary precision.
3) You needn't be a professor or assistent professor in Maths (Mathoverflow is aimed at those) or CS to solve it.
A more general knowledge of math and CS should suffice. (And a prerequisite is an inquisitive mind and a willingness to
explore).

Probably if 3) is not met we won't understand it either. :lol:
However, I'm curious how much trouble some of those Mathoverflow persons would have with some of our problems.

ad 3)
Initially PE was set up by Colin (aka Euler) following the principle of inductive chain learning.
That is, while solving the problems for #1 to #current, you will gradually develop the knowledge and experience needed for the next ones. However, many problems contain something new that you have to find out or find resources for on the web.
Sometimes the jumps are rather large, I must admit.
And (blush, blush) sometimes we forget about that principle.

I'm not that impressed with that condition of 15 lines of Python.
Python has a lot of built-in goody's that some other languages lack.
And beware what you can do with 15 lines of J (although it might take you a life time to be able to use J to that extend.)
Image

wrongrook
Posts: 403
Joined: Sat Oct 17, 2009 10:39 pm

Re: Exceptionally difficult questions

Post by wrongrook »

Thank you very much for your reply, this satisifes my curiosity.

(Although I was kind of hoping that someone had suggested a problem (and worked solution) along the lines "What is the smallest N such that if the integers {1, 2, ..., N} are colored, each with one of 2 different colors, then there are at least 16 integers in arithmetic progression all of the same color?" but the team had decided that it would have been too hard for non-mathematicians (such as myself) to be able to solve...http://en.wikipedia.org/wiki/Van_der_Waerden_number)

Post Reply