A grasshopper sits on the first square of a 1×N board. He can jump over one or two squares and land on the next square. The gras
shopper can jump forward or back but he must stay on the board. Find the least number n such that for any N ≥ n the grasshopper can land on each square exactly once. 100 PTS PLS HELP. Can someone answer this genuinely and not just take the points?!!? Thank you
You can start by imagining this scenario on a small scale, say 5 squares.
Assuming it starts on the first square, the grasshopper can cover the full 5 squares in 2 ways; either it can jump one square at a time, or it can jump all the way to the end and then backtrack. If it jumps one square at a time, it will take 4 hops to cover all 5 squares. If it jumps two squares at a time and then backtracks, it will take 2 jumps to cover the full 5 squares and then 2 to cover the 2 it missed, which is also 4. It will always be one less than the total amount of squares, since it begins on the first square and must touch the rest exactly once. Therefore, the smallest amount n is N-1. Hope this helps!