I think this is just one of the pitfalls that the author points out: it is not the sheer number of possibilities that defines the difficulty of a problem. He links to his previous blog post
“Sorting a bunch of numbers! Hoo-wee, that’s a hard one. If I had 1000 numbers, I would have to check all orderings of the numbers to find the sorted order. That is 1000999998…21 orders and that is more than the hairs on a Hobbit’s toes.”
http://mat.tepper.cmu.edu/blog/?p=6995
with a nice example: sorting.
“Sorting a bunch of numbers! Hoo-wee, that’s a hard one. If I had 1000 numbers, I would have to check all orderings of the numbers to find the sorted order. That is 1000999998…21 orders and that is more than the hairs on a Hobbit’s toes.”