Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Why is the count of solutions for distance 19 and 20 lower than for 17 and 18?


I was asking myself the same thing.. intuitively I feel like it's right but I'm no expert.


An intuitive way of thinking about it is that if you have an arrangement with distance 20, any move you make is going to make it distance 19. Since there are 12 possible moves, every distance 20 arrangement has 12 distance 19 neighbors.


That logic has a flaw: for every 'distance 19' arrangement you find that way, there may be more than one 'distance 20' arrangement one can reach from it in one move.

For example, you have two parents, but that does not imply that, combined, you and all your siblings have more parents than there are in that group of siblings.


Same reason why, given a point on a 100-dimensional cube, the number of points x steps away from that point starts decreasing for x > 50.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: