A particle travels on a grid of lattice points. Every trip starts at (0,0) and stops at (1,0). It can travel in any orthogonal direction provided:
* it remains in the first quadrant (i >= 0, j >= 0);
* it never visits the same lattice point more than once during the same trip.
During each trip it earns income of i*j dollars for each lattice point visited, but must pay a tax of one dollar for each step taken. For example, if it travels {up, right, down}, its earnings would $1, taxes $3, for a loss of $2. In this trip it visited 4 lattice points if you include (0,0), but there were only 3 steps.
(1) Determine the maximum profit the particle can make for a trip of exactly 7 steps?
(2) Same question for a trip of 13 steps.
(3) What is the minimum number of steps a trip would need to be for a profit of 100 or more?
(4) Same question for a profit of 1000 or more.
Inspired by Path Cost
Seven steps can produce only 2 in profit via the path shown:
7 2
0 1
1 1
1 2
2 2
2 1
2 0
1 0
For thirteen steps the profit can be 40:
13 40
0 1
1 1
1 2
2 2
2 3
3 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
The first number of steps to show over 100 in profit is 19, and for over 1000, 37, as shown below.
9 9
0 1
1 1
1 2
2 2
3 2
3 1
2 1
2 0
1 0
11 22
0 1
1 1
1 2
2 2
2 3
3 3
3 2
3 1
2 1
2 0
1 0
13 40
0 1
1 1
1 2
2 2
2 3
3 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
15 66
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 3
4 2
3 2
3 1
2 1
2 0
1 0
17 99
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
19 142
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
21 194
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
23 258
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
25 333
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
27 422
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 7
7 7
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
29 524
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 7
7 7
8 7
8 6
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
31 642
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 7
7 7
7 8
8 8
8 7
8 6
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
33 775
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 7
7 7
7 8
8 8
9 8
9 7
8 7
8 6
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
35 926
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 7
7 7
7 8
8 8
8 9
9 9
9 8
9 7
8 7
8 6
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
37 1094
0 1
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
6 7
7 7
7 8
8 8
8 9
9 9
10 9
10 8
9 8
9 7
8 7
8 6
7 6
7 5
6 5
6 4
5 4
5 3
4 3
4 2
3 2
3 1
2 1
2 0
1 0
clearvars,clc
for init=4:2:20
for extra=[1,3]
pos=[0,0]; tot=0;
path=double.empty(0,2);
moves=2*init+extra-2;
for i=1:init/2
pos=pos+[0,1]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
pos=pos+[1,0]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
end
if extra==1
pos=pos-[0,1]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
else
pos=pos+[1,0]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
pos=pos-[0,1]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
pos=pos-[1,0]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
end
while ~isequal(pos,[1,0])
pos=pos-[0,1]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
pos=pos-[1,0]; path(end+1,:)=pos;
tot=tot+prod(pos)-1;
end
fprintf('%4d %6d\n',[moves,tot])
for i=1:size(path,1)
fprintf(' %3d %3d\n',path(i,:))
end
end
end
|
|
Posted by Charlie
on 2025-05-05 23:26:01 |
computer solution
