# Thread: golden maze

1. ## golden maze

Can you give me some ideas how to solve this question.

Thank

dupe

2. Hello, ma203!

It seems pretty elementary . . . Did you try anything?

Here is a maze of rooms; each room contains some bags of gold.
The numbers tell you how many bags of gold there are in each room.

You have to find a way through the maze, collecting bags of gold as you go.

You must get as much gold as you can, but can enter each room just once.

You must set up each maze in the same way.

1. In the maze below, what is the most gold you can collect?

Code:
      *-----------*-----------*-----------*-----------*
|           |           |           |           |
Enter →     1           2           3           4     |
|           |           |           |           |
*---*   *---*---*   *---*---*   *---*---*   *---*
|           |           |           |           |
|     5           6           7           8     → Exit
|           |           |           |           |
*-----------*-----------*-----------*-----------*

Our path will be: 1 - 5 - 6 - 7 - 3 - 4 - 8
. . skipping only "2", and collecting 34 bags of gold.

This is our strategy when there is an even number of columns.
We enter into room "1", move down one room,
. . then move right two rooms (under and past "2")
. . then proceed up-right-down-right- ... etc. to the Exit.

With two rows and $\displaystyle n$ columns, the numbers run from 1 to $\displaystyle 2n$.
And we will collect all the numbers except "2": .$\displaystyle \frac{2n(2n+1)}{2} - 2 \:=\:2n^2+2n-2$

If there is an odd number of columns, we can enter all the rooms.
We enter room "1", move down one room, then right one room,
. . then proceed up-right-down=right- . . . etc. to the Exit.

With two rows and $\displaystyle n$ columns , the numbers run from 1 to $\displaystyle 2n.$
And we will collect all the numbers: .$\displaystyle \frac{2n(2n+1)}{2} \;=\;2n^2+n$