Which is the hardest problem?

General chat, humour, riddles, logic/lateral/word puzzles...
Post Reply
JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

Which is the hardest problem?

Post by JohnMorris »

Waiting for end of the summer break, I took to wondering which of all the 202 current problems is the hardest. All other things being equal, the harder the problem, the fewer people will have solved it, and that's how PE orders its "by difficulty" listing.

But that neglects the length of time the problem has been available: a problem that has been solved by 100 people in a year is probably harder than one which was solved by 100 people in the first day.

So some measure of the difficulty of a problem should be how many people have solved it per day since its release. The smaller this number, the harder the problem.

Now, before you all jump on me pointing out that this calculation makes all sorts of unjustified assumptions that are probably incorrect - I know. It's just a bit of fun, so don't take it too seriously.

So here are the - maybe - top ten hardest problems:
*  1: Problem 143 (View Problem) (02 Mar 2007;  514 days ago): solved by   204:   0.40/day
*  2: Problem 106 (View Problem) (07 Oct 2005; 1025 days ago): solved by   413:   0.40/day
*  3:  Problem 88 (View Problem) (04 Feb 2005; 1270 days ago): solved by   512:   0.40/day
*  4: Problem 153 (View Problem) (05 May 2007;  450 days ago): solved by   191:   0.42/day
*  5: Problem 126 (View Problem) (18 Aug 2006;  710 days ago): solved by   313:   0.44/day
*  6: Problem 152 (View Problem) (27 Apr 2007;  458 days ago): solved by   202:   0.44/day
*  7: Problem 154 (View Problem) (12 May 2007;  443 days ago): solved by   197:   0.44/day
*  8: Problem 105 (View Problem) (23 Sep 2005; 1039 days ago): solved by   485:   0.47/day
*  9: Problem 103 (View Problem) (26 Aug 2005; 1067 days ago): solved by   499:   0.47/day
* 10: Problem 156 (View Problem) (25 May 2007;  430 days ago): solved by   202:   0.47/day
Image
User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: Which is the hardest problem?

Post by Tommy137 »

I'm a bit surprised that the "sum set problems" 103, 105 and 106 are in this list.
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Which is the hardest problem?

Post by daniel.is.fischer »

Thumbo wrote:Waiting for end of the summer break, I took to wondering which of all the 202 current problems is the hardest. All other things being equal, the harder the problem, the fewer people will have solved it, and that's how PE orders its "by difficulty" listing.

But that neglects the length of time the problem has been available: a problem that has been solved by 100 people in a year is probably harder than one which was solved by 100 people in the first day.

So some measure of the difficulty of a problem should be how many people have solved it per day since its release. The smaller this number, the harder the problem.
But every new problem is solved by a large proportion of the [ge] 99%ers and at least a handful of newer members before the weekend is over, be it hard or not. So that measure is not yet reliable for recent problems. Assuming that each problem is solved by at least 40 people within the first week, none could make it into the top ranks before it's three months old - during that time more will solve it, so it'll be rather four months. Of course, that is quite sensible, you can't confidently judge the difficulty of a problem before it's been in the open for a while, but it introduces a bias against hard recent problems (and IMO, some of Problem 167 (View Problem), Problem 177 (View Problem), Problem 194 (View Problem), Problem 195 (View Problem), Problem 198 (View Problem) are considerably harder than several in your list) of which one must be aware.

Perhaps a measure of (solutions - q*100%ers)/days where q is a factor between 0.5 and 1 would lessen that bias, though I have no idea how to justify any value of q :?
Now, before you all jump on me pointing out that this calculation makes all sorts of unjustified assumptions that are probably incorrect - I know. It's just a bit of fun, so don't take it too seriously.
*jumps*, *points*, :lol:
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

Re: Which is the hardest problem?

Post by JohnMorris »

daniel.is.fischer wrote: Assuming that each problem is solved by at least 40 people within the first week, none could make it into the top ranks before it's three months old - during that time more will solve it, so it'll be rather four months. Of course, that is quite sensible, you can't confidently judge the difficulty of a problem before it's been in the open for a while, but it introduces a bias against hard recent problems (and IMO, some of Problem 167 (View Problem), Problem 177 (View Problem), Problem 194 (View Problem), Problem 195 (View Problem), Problem 198 (View Problem) are considerably harder than several in your list) of which one must be aware.
Yes. Messing around, and following a similar train of though to yours, I decided to try discounting the first 40 solvers and the first week after release, changing the per day solve rate from (solvers / days) to ((solvers - 40) / (days - 7)).

Do that and the table becomes:
1: Problem 143 (View Problem) (02 Mar 2007;  515 days ago): solved by   204:   0.32/day
  2: Problem 153 (View Problem) (05 May 2007;  451 days ago): solved by   191:   0.34/day
  3: Problem 198 (View Problem) (14 Jun 2008;   45 days ago): solved by    53:   0.34/day
  4: Problem 152 (View Problem) (27 Apr 2007;  459 days ago): solved by   202:   0.36/day
  5: Problem 154 (View Problem) (12 May 2007;  444 days ago): solved by   197:   0.36/day
  6: Problem 106 (View Problem) (07 Oct 2005; 1026 days ago): solved by   413:   0.37/day
  7: Problem 177 (View Problem) (11 Jan 2008;  200 days ago): solved by   112:   0.37/day
  8:  Problem 88 (View Problem) (04 Feb 2005; 1271 days ago): solved by   512:   0.37/day
  9: Problem 156 (View Problem) (25 May 2007;  431 days ago): solved by   202:   0.38/day
 10: Problem 126 (View Problem) (18 Aug 2006;  711 days ago): solved by   313:   0.39/day
  ...
 13: Problem 167 (View Problem) (09 Nov 2007;  263 days ago): solved by   147:   0.42/day
  ...
 57: Problem 194 (View Problem) (17 May 2008;   73 days ago): solved by    84:   0.67/day
  ...
 78: Problem 195 (View Problem) (23 May 2008;   67 days ago): solved by    85:   0.75/day
I would guess that in reality the solve-rate curve for each problem has a high start peak (the keen ones), then something like a decaying exponential, all offset by steady growth - especially at the lower problem numbers - due to new members discovering PE. Trying to approximate that with a single horizontal line, which is more or less what I'm doing here, is (to be kind to myself) foolish.
*jumps*, *points*, :lol:
Hey! I told you not to do that! <sulk>
Image
User avatar
rayfil
Administrator
Posts: 1412
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Which is the hardest problem?

Post by rayfil »

I started analyzing this last winter and came up with a crude formula which is a function of the length of time the problem has been published, the number of solutions, and a "fudge" factor to cover the 100-percenters and all those others who may try new problems as they come out before continuing their quest to solve previous ones.

My algo disregards rating a problem until it has been solved at least 100 times. It's also designed to provide a rating between 1 and 20, anything at or above 20 being reported as 20+. I applied it to the data at the end of March, April and May and noticed that the majority of problems kept the same rating over that period. During that period of time, very few ratings changed by more than 1 unit on that 1-20 scale unless the problem was quite easy.

My results on May 30th included problems up to #195 which had been published the week before. Problems # 177, 192, 194 and 195 still had not reached 100 solutions and could not be rated; (177 and 192 have since exceeded 100 solutions and would be rated as 20+ based on today's data, while 194 and 195 are still below 100 solutions).

For problems published in June, 198, 199, 201 and 202 still have not reached 100 solutions and could be considered as being in the 20+ category (or close to it). The other problems which were in the 20+ category at the end of May were 163, 167 and 180.

I would thus consider those 11 problems as the most difficult up to now.
When you assume something, you risk being wrong half the time.
User avatar
greekcandyman
Posts: 7
Joined: Tue Jul 29, 2008 5:22 pm

Re: Which is the hardest problem?

Post by greekcandyman »

I've solved most of those "hard" problems so I don't think they should count as hard.
But I'm stumped on some of the "easy" ones! :shock:
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Which is the hardest problem?

Post by daniel.is.fischer »

Hardness of problem is evidently a very personal metric. The best we can do is take the average of our membership.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

Re: Which is the hardest problem?

Post by JohnMorris »

Browsing my hard drive, I came across the program and decided to run it again. My totally unofficial and unscientific listing of the ten hardest problems - according to the solve rate by Project Euler members - is now:
1: Problem 143 (View Problem) (02 Mar 2007;  720 days ago): solved by   299:   0.42/day
  2: Problem 153 (View Problem) (05 May 2007;  656 days ago): solved by   282:   0.43/day
  3: Problem 177 (View Problem) (11 Jan 2008;  405 days ago): solved by   176:   0.43/day
  4: Problem 156 (View Problem) (25 May 2007;  636 days ago): solved by   295:   0.46/day
  5: Problem 152 (View Problem) (27 Apr 2007;  664 days ago): solved by   309:   0.47/day
  6: Problem 154 (View Problem) (12 May 2007;  649 days ago): solved by   306:   0.47/day
  7: Problem 167 (View Problem) (09 Nov 2007;  468 days ago): solved by   222:   0.47/day
  8: Problem 147 (View Problem) (31 Mar 2007;  691 days ago): solved by   335:   0.48/day
  9: Problem 163 (View Problem) (13 Oct 2007;  495 days ago): solved by   250:   0.51/day
 10: Problem 126 (View Problem) (18 Aug 2006;  916 days ago): solved by   466:   0.51/day
Six out of the ten were in March to May 2007. I guess the PE team were just in a mean mood that Spring :)
Image
Ted
Posts: 21
Joined: Sun Apr 02, 2006 10:46 pm

Re: Which is the hardest problem?

Post by Ted »

Hardest problem: What is the sum of the solutions to the ten hardest problems? :)

Please do NOT post the solution!!!
mbh038
Posts: 10
Joined: Wed Jun 22, 2016 8:24 pm

Re: Which is the hardest problem?

Post by mbh038 »

Thank you John Morris! I found 88 to be, by some distance, the hardest of the first 100.
My parapet, a few outliers excepted, is currently around the 130 mark, and on a clear day I can see as far 150-ish. It looks grim out there.
Post Reply