Jump to content
BrainDen.com - Brain Teasers
  • 0

Descartes Racing.......


superprismatic
 Share

Question

Let's have a race in the cartesian plane. We define a point as a pair, (x,y), where

x and y are both integers. We will start the race at the point (0,0). Then, we stop

at the points (18,20), (14,12), (35,25), (30,8), then back to (0,0), in that order.

In order to tell how we can move each time, we have a movement vector (a,b). if we are

at point (x,y) and the movement vector is (a,b), the next point we will visit is (x+a,y+b).

The movement vector starts at (0,0). Before each move, we may add or subtract 1 from

either or both or none of the elements of the movement vector, then we use it to move.

To move from (0,0) to (18,20), for example, we can move as follows:

01. at point (0,0); movement vector=(0,0); new movement vector=(-1,1); new point=(-1,1)

02. at point (-1,1); movement vector=(-1,1); new movement vector=(-2,2); new point=(-3,3)

03. at point (-3,3); movement vector=(-2,2); new movement vector=(-3,2); new point=(-6,5)

04. at point (-6,5); movement vector=(-3,2); new movement vector=(-2,3); new point=(-8,8)

05. at point (-8,8); movement vector=(-2,3); new movement vector=(-1,4); new point=(-9,12)

06. at point (-9,12); movement vector=(-1,4); new movement vector=(0,3); new point=(-9,15)

07. at point (-9,15); movement vector=(0,3); new movement vector=(1,3); new point=(-8,18)

08. at point (-8,18); movement vector=(1,3); new movement vector=(2,2); new point=(-6,20)

09. at point (-6,20); movement vector=(2,2); new movement vector=(3,1); new point=(-3,21)

10. at point (-3,21); movement vector=(3,1); new movement vector=(4,1); new point=(1,22)

11. at point (1,22); movement vector=(4,1); new movement vector=(5,0); new point=(6,22)

12. at point (6,22); movement vector=(5,0); new movement vector=(6,-1); new point=(12,21)

13. at point (12,21); movement vector=(6,-1); new movement vector=(6,-1); new point=(18,20)

In this example, it took 13 moves to get from (0,0) to (18,20). Our next target is (14,12),

but we are stuck with our movement vector of (6,-1) which we can change before we use it to

get to our next point. The problem is to go from (0,0) back to (0,0) stopping at the points

(18,20), (14,12), (35,25), and (30,8) (in that order, along the way) in the fewest number of

moves. Are you up to the challenge?

Link to comment
Share on other sites

12 answers to this question

Recommended Posts

  • 0


cur coor|  move

0,0  	0,0

0,0  	1,1

1,1  	2,2

3,3  	3,3

6,6  	3,4

9,10	3,3

12,13  3,4

15,17  3,3

18,20  2,2

20,22  1,1

21,23  0,0

21,23  -1,-1

20,22   -2,-2

18,20   -2,-3

16,17   -1,-3

15,14   -1,-2

14,12	0,-1

14,11   1, 0

15,11	2,1

17,12	3,2

19,14	4,3

23,17	5,3

28,20	4,3

32,23	3,2

35,25 	2,1

37,26	1,0

38,26    0,-1

38,25	-1,-2

37,23   -1,-3

36,20	-1,-4

35,16   -1,-3

34,13   -1,-2

33,11   -1,-2

32,9 	-2,-1

30,8  	-3,-1

27,7 	-4,-1

23,6 	-5,-1

18,5 	-5,-1

13,4 	-4,-1

9,3  	-3,-1

6,2  	-3,-1

3,1  	-3,-1

0,0

43 moves.

Link to comment
Share on other sites

  • 0

x y a b

0 0 1 1

1 1 2 2

3 3 3 3

6 6 4 4

10 10 3 4

13 14 2 3

15 17 2 2

17 19 1 1

18 20 1 0

19 20 0 -1

19 19 -1 -2

18 17 -2 -2

16 15 -1 -2

15 13 -1 -1

14 12 0 0

14 12 1 1

15 13 2 2

17 15 3 3

20 18 4 3

24 21 4 2

28 23 3 2

31 25 2 1

33 26 1 0

34 26 1 -1

35 25 1 -2

36 23 0 -3

36 20 -1 -4

35 16 -2 -4

33 12 -3 -4

30 8 -4 -3

26 5 -5 -2

21 3 -6 -1

15 2 -7 -1

8 1 -8 -1

0 0 -9 -1

Link to comment
Share on other sites

  • 0

1: ( 0, 0) [ 1, 1] !!!

 2: ( 1, 1) [ 2, 2]

 3: ( 3, 3) [ 3, 3]

 4: ( 6, 6) [ 4, 4]

 5: (10,10) [ 3, 4]

 6: (13,14) [ 2, 3]

 7: (15,17) [ 2, 2]

 8: (17,19) [ 1, 1]

 9: (18,20) [ 0, 0] !!!

10: (18,20) [-1,-1]

11: (17,19) [-2,-2]

12: (15,17) [-1,-3]

13: (14,14) [ 0,-2]

14: (14,12) [ 1,-1] !!!

15: (15,11) [ 2, 0]

16: (17,11) [ 3, 1]

17: (20,12) [ 4, 2]

18: (24,14) [ 4, 3]

19: (28,17) [ 3, 3]

20: (31,20) [ 2, 2]

21: (33,22) [ 1, 2]

22: (34,24) [ 1, 1]

23: (35,25) [ 1, 0] !!!

24: (36,25) [ 2,-1]

25: (38,24) [ 1,-2]

26: (39,22) [ 1,-3]

27: (40,19) [ 0,-4]

28: (40,15) [-1,-3]

29: (39,12) [-2,-2]

30: (37,10) [-3,-1]

31: (34, 9) [-4,-1]

32: (30, 8) [-5,-2] !!!

33: (25, 6) [-6,-3]

34: (19, 3) [-6,-2]

35: (13, 1) [-7,-1]

36: ( 6, 0) [-6, 0]

37: ( 0, 0)         !!! 

Edited by Dej Mar
Link to comment
Share on other sites

  • 0

The fastest method using only x and a, I get 33 moves. Using only y and b, I get 31.

This is number of moves for x and y independently of the other (but taking into consideration direction change for next move) until arrival at each destination:

1. 8, 8

2. 4, 6

3. 10, 9

4. 4, 6

5. 7, 2

Will reanalyse shortly. Some can be modified (see 4,6) to include "turnaround time" as I like to call it.

Link to comment
Share on other sites

  • 0

Best I could find is:

y b

1 1

2 3

3 6

4 10

4 14

3 17

2 19

1 20 !!

0 20

-1 19

-2 17

-2 15

-2 13

-1 12 !!

0 12

1 13

2 15

3 18

3 21

2 23

1 24

1 25

0 25 !!

-1 24

-2 22

-2 20

-3 17

-4 13

-5 8 !!

-4 3

-3 0 !!

...x...y

1. 8, 8

2. 4, 6

3. 9, 9

4. 5, 6

5. 5, 2

If y can't be improved for any instance of y > x (steps 2 and 4) at the expense of a longer trip where x > y, the shortest trip should be the sum of the larger from each step.

1. 8

2. 6

3. 9

4. 6

5. 5

= 34

Edited by Molly Mae
Link to comment
Share on other sites

  • 0

...x...y

1. 8, 8

2. 4, 5

3. 9, 9

4. 5, 7

5. 5, 2

b..y

1 1

2 3

3 6

4 10

4 14

3 17

2 19

1 20 ! -> 12

0 20

-1 19

-2 17

-3 14

-2 12 ! ->25

-1 11

0 11

1 12

2 14

3 17

2 19

3 22

2 24

1 25 ! -> 8

0 25

-1 24

-2 22

-3 19

-4 15

-3 12

-4 8 ! -> 0

-4 4

-4 0 !

Reduces the time for the second leg of the trek at the cost of a longer trip on the 4th leg. -1 and +1 = No net gain.

34 is looking like our lower limit.

Link to comment
Share on other sites

  • 0

Molly Mae, I fear you are right. My heart tells me that any time I'm not accelerating or decelerating, I'm wasting time (these are places where the acceleration is 0, rather than 1 or -1). There are a half dozen of those in my 2-D solution, and a smaller number in your 1D solutions. Yet they seem to all be necessary in order to prepare to land on the next waypoint, or to do so while preparing for the subsequent path (or for marking time because of the longer distance in the other dimension).

I very much enjoy your penultimate "flight home" from 35,25 in the Y dimension--two steps from 8 to 0 is awesome!

Link to comment
Share on other sites

  • 0
There are (at least) 672 different ways to race from (0,0) to (0,0)

in the minimum 34 steps with stopping at each of the four intervening check points.

A] 8 steps between (0,0) and (18,20):

(1,1), (2,2), (3,3), (4,4), (3,4), (2,3), (2,2), (1,1)

(1,1), (2,2), (3,3), (3,4), (3,4), (3,3), (2,2), (1,1)

B] 6 steps between (18,20) and (14,12):

(1,0), ( 0,-1), (-1,-2), (-2,-2), (-1,-2), (-1,-1)

(1,0), ( 0,-1), (-1,-2), (-1,-2), (-2,-2), (-1,-1)

(0,0), ( 0,-1), (-1,-2), (-1,-2), (-1,-2), (-1,-1)

(0,0), ( 0,-1), ( 0,-2), (-1,-2), (-2,-2), (-1,-1)

(0,0), ( 0,-1), (-1,-2), (-2,-2), (-1,-2), ( 0,-1)

(0,0), (-1,-1), (-1,-2), (-1,-2), (-1,-2), ( 0,-1)

(0,0), (-1,-1), (-2,-2), (-1,-2), ( 0,-2), ( 0,-1)

C] 15 steps between (14,12) and (30,8) [with stop at (35,25)]:

C1a] 9 steps between (14,12) and (35,25):

(0,0), (1,1), (2,2), (3,3), (4,3), (3,2), (3,1), (3,1), (2,0)

(0,0), (1,1), (2,1), (3,2), (4,3), (3,3), (3,2), (3,1), (2,0)

(0,0), (1,1), (2,2), (3,3), (4,3), (4,2), (3,1), (2,1), (2,0)

(0,0), (1,1), (2,1), (3,2), (4,3), (4,3), (3,2), (2,1), (2,0)

C1b] 6 steps between (35,25) and (30,8):

(1,-1), (0,-2), (0,-3), (-1,-4), (-2,-4), (-3,-3)

(1,-1), (0,-2), (0,-3), (-1,-4), (-2,-3), (-3,-4)

(1,-1), (0,-2), (0,-3), (-1,-4), (-2,-4), (-3,-4)

-or-

C2a] 10 steps between (14,12) and (35,25):

(0,0), (1,1), (2,2), (3,3), (4,3), (4,2), (3,2), (2,1), (1,0), (1,-1)

(0,0), (1,1), (1,2), (2,3), (3,3), (4,2), (4,2), (3,1), (2,0), (1,-1)

(0,0), (1,1), (2,2), (3,2), (4,3), (4,3), (3,2), (2,1), (1,0), (1,-1)

(0,0), (1,1), (1,2), (2,2), (3,3), (4,3), (4,2), (3,1), (2,0), (1,-1)

C2b] 5 steps between (35,25) and (30,8):

(1,-2), (0,-3), (-1,-4), (-2,-4), (-3,-4)

D] 5 steps between (30,8) and (0,0):

(-4,-3), (-5,-2), (-6,-2), (-7,-1), (-8,0)

(-4,-3), (-5,-2), (-6,-1), (-7,-1), (-8,-1)

(-4,-2), (-5,-2), (-6,-2), (-7,-1), (-8,-1)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...