Trailblazer

Logic Level 1

Starting at the square marked with a star, and moving from square to square either horizontally or vertically, it is possible to visit every square only once.

Which of the squares marked with a letter cannot be the end of the path?

A B C D

2 solutions

Jason Dyer Staff
Oct 11, 2016

The purple marked path is forced by the corner squares each having only one possible route. Using this route as the basis, C is the only square which cannot be the final square of the path.

+1 Your solution is a great read:

There is a quick argument that we definitely cannot end on C, without caring about squares A, B, D. Hint: Parity.

Thanks for contributing and helping other members aspire to be like you!

Calvin Lin Staff - 4 years, 8 months ago

Eli Ross Staff
Oct 21, 2016

Call the starting square $(0,0).$ Each move changes your $x$ or $y$ coordinate by $\pm 1,$ and there are 18 other squares to visit, so the sum of your $x$ and $y$ coordinates must be even after 18 steps. But C is 2 down and 1 over from the start, so the sum of its coordinates is odd.

(To complete the proof, you need to show that A, B, and D are possible, which Jason has done in his solution.)

Trailblazer

2 solutions

0 pending reports