Define the cost of a lattice point (i, j) to be i × j. A particle starts at (0, 0) and makes a series of 10 hops. Each hop increases the particle’s x-coordinate by 1 or y-coordinate by 1. Let the price of the particle’s path be the sum of the costs of the lattice points it meets, including (0, 0) and its final position. Find the maximum price of any path the particle can take.
Intuitively it makes sense, when hopping, to increase whichever coordinate is smaller to get the highest product from the destination point. So the highest scoring path should end at (5,5). Each odd hop can be either up or right. Each even hop should be the 'other' choice from the previous hop.
The trajectory passes through each point (k,k) every other step, for k going from 0 to 5.
0 + 0 + 1 + 2 + 4 + 6 + 9 + 12 + 16 + 20 + 25 = 95
|
Posted by Larry
on 2025-04-26 09:09:40 |