1
$\begingroup$

Imagine this Checkers Now, the first case describes how you can connect the two points. You are only allowed to connect them vertically or horizontally, not diagonally. Is this possible for the second scenario? Please explain your answer.

$\endgroup$
3
  • 2
    $\begingroup$ isn't it just up right right? pretty sure it's not but i'm not understanding the question $\endgroup$
    – suomynonA
    Sep 24, 2016 at 23:49
  • 1
    $\begingroup$ I am not sure, whether I get the intent of the qeustion, but it is not possible to visit all the squares exactly once in the second case. $\endgroup$
    – Peter
    Sep 24, 2016 at 23:49
  • 1
    $\begingroup$ if what peter said was correct, you can't because once you go to the squares to the top or the bottom of the destination you are trapped. $\endgroup$
    – suomynonA
    Sep 24, 2016 at 23:52

3 Answers 3

3
$\begingroup$

McLinux: Please edit your question to explain that the path has to visit all the squares, and each exactly once.

Not possible in Case 2. With the exception of the dotted squares, every other square must be entered once and exited once. In particular, the path must use both "walls" of every corner square. Now look at the corners on the right side: both walls that separate them from the dotted square must be used. Which means the path to the right-side dot must come from BOTH corners on the right side. Contradiction.

$\endgroup$
3
$\begingroup$

Color the squares in a checkerboard pattern - black, white. Two squares that share a common edge are colored differently. Now, if there is a path that visits all squares, moving from square to square only through the edges, starting from on point and ending at the other, then a necessary condition for such path to exist is that both points are on squares that are colored the same way.

Now a path that goes through all squares should go from black to white to black... (order the sequence in a linear order). Then the path should have the number of black and white squares equal to the number of black and white squares from the board. So if one starts from black, it cannot end at white. If you add the numbers, you'll see they do not add up. If you start from black and end up at white, then the total number of squares should be even (because next to each black there is a white square forward). But the number of the squares on the board is odd.

Now if one corner square is black, then all corner squares are black. If one starts from a white square the end should be white too by the above argument. But then the number of white squares in a path is more than the number of black squares. But these are the same squares from the board, on which the number of black squares is larger than the white. So there is no path between white-white. Basically, we cannot start or end at a white vertex. It has to be black

$\endgroup$
2
  • $\begingroup$ That is a necessary condition, but not a sufficient one. Suppose for definiteness that the corner squares are black. Then there exists such a path for all choices of black start- and end-points, but not for any choice of white start- and end-points. $\endgroup$
    – TonyK
    Sep 25, 2016 at 0:30
  • $\begingroup$ @TonyK Man, I really didn't feel like going too much into detail for this question. But I edited my answer to accommodate your correct observation. $\endgroup$ Sep 25, 2016 at 0:53
0
$\begingroup$

The only way you can visit all the squares is to roll the checkerboard and make a cylinder then follow the path in this drawing below: enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.