Skip to main content
Puzzling

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

#Upper Bound#

Upper Bound

Given 10 people, there are 45 possible pairings. This would mean that there is an upper bound of 45 items.

However, the first pair to enter the dungeon will be the same level (level 1), so there will be no item awarded.

Similarly, the last pair to enter the dungeon will have gone with all 8 others first and both will be at level 9. Their final trip through the dungeon will not get an item.

Thus, the maximum possible items is 43.

#40 Solution#

40 Solution

Lets split the people into 2 groups of 5. They will be $\{a_1,b_1,c_1,d_1,e_1\}$ and $\{z_1,y_1,x_1,w_1,v_1\}$. The subscript denotes their level.

The first two to enter the dungeon are $\{a_1,z_1\} \implies \{a_2,z_2\}$. No item is obtained.

Now, the two groups will only pair up amongst themselves. Lets work with the first group. We will do the following pairings.

  1. $\{a_2,b_1\} \implies \{a_3,b_2\}$ (item)
  2. $\{b_2,c_1\} \implies \{b_3,c_2\}$ (item)
  3. $\{c_2,d_1\} \implies \{c_3,d_2\}$ (item)
  4. $\{d_2,e_1\} \implies \{d_3,e_2\}$ (item)
  5. $\{a_3,e_2\} \implies \{a_4,e_3\}$ (item)
  6. $\{a_4,c_3\} \implies \{a_5,c_4\}$ (item)
  7. $\{c_4,e_3\} \implies \{c_5,e_4\}$ (item)
  8. $\{b_3,e_4\} \implies \{b_4,e_5\}$ (item)
  9. $\{b_4,d_3\} \implies \{b_5,d_4\}$ (item)
  10. $\{a_5,d_4\} \implies \{a_6,d_5\}$ (item)

So now we have the following $\{a_6,b_5,c_5,d_5,e_5\}$. Lets assume the other group did something similar so they have $\{z_6,y_5,x_5,w_5,v_5\}$ and we have obtained 20 items so far (optimal).

Now we need to start pairs between the groups. We will do a zig zag pattern from $a - y - c - w - e$.

  1. $\{a_6, y_5\} \implies \{a_7,y_6\}$ (item)
  2. $\{y_6, c_5\} \implies \{y_7,c_6\}$ (item)
  3. $\{c_6, w_5\} \implies \{c_7,w_6\}$ (item)
  4. $\{w_6, e_5\} \implies \{w_7,e_6\}$ (item)

We will do the same for $z-b-x-d-v$.

  1. $\{z_6, b_5\} \implies \{z_7,b_6\}$ (item)
  2. $\{b_6, x_5\} \implies \{b_7,x_6\}$ (item)
  3. $\{x_6, d_5\} \implies \{x_7,d_6\}$ (item)
  4. $\{d_6, v_5\} \implies \{d_7,v_6\}$ (item)

Lastly, we will have the last one $e$ and $v$ pair off with the first.

  1. $\{a_7, v_6\} \implies \{a_8,v_7\}$ (item)
  2. $\{z_7, e_6\} \implies \{z_8,e_7\}$ (item)

Now we have the following:

$$\{a_8, b_7, c_7, d_7, e_7\}$$ $$\{z_8, y_7, x_7, w_7, v_7\}$$

This time, we will do it a bit differently.

  1. $\{a_8, x_7\} \implies \{a_9, x_8\}$ (item)
  2. $\{x_8, e_7\} \implies \{x_9, e_8\}$ (item)
  3. $\{e_8, y_7\} \implies \{e_9, y_8\}$ (item)
  4. $\{y_8, d_7\} \implies \{y_9, d_8\}$ (item)

Similarly, starting from $z$.

  1. $\{z_8, c_7\} \implies \{z_9, c_8\}$ (item)
  2. $\{c_8, v_7\} \implies \{c_9, v_8\}$ (item)
  3. $\{v_8, b_7\} \implies \{v_9, b_8\}$ (item)
  4. $\{b_8, w_8\} \implies \{b_9, w_8\}$ (item)

Again, completing the loop:

  1. $\{d_8, z_9\} \implies \{d_9, z_{10}\}$ (item)
  2. $\{w_8, a_9\} \implies \{w_9, a_{10}\}$ (item)

The following pairings are left;

$$\{b_9,y_9\}, \{c_9,x_9\}, \{d_9,w_9\}, \{e_9,v_9\}$$

And nothing more can be doe. This solution gets us 40 items.

#Upper Bound#

Given 10 people, there are 45 possible pairings. This would mean that there is an upper bound of 45 items.

However, the first pair to enter the dungeon will be the same level (level 1), so there will be no item awarded.

Similarly, the last pair to enter the dungeon will have gone with all 8 others first and both will be at level 9. Their final trip through the dungeon will not get an item.

Thus, the maximum possible items is 43.

#40 Solution#

Lets split the people into 2 groups of 5. They will be $\{a_1,b_1,c_1,d_1,e_1\}$ and $\{z_1,y_1,x_1,w_1,v_1\}$. The subscript denotes their level.

The first two to enter the dungeon are $\{a_1,z_1\} \implies \{a_2,z_2\}$. No item is obtained.

Now, the two groups will only pair up amongst themselves. Lets work with the first group. We will do the following pairings.

  1. $\{a_2,b_1\} \implies \{a_3,b_2\}$ (item)
  2. $\{b_2,c_1\} \implies \{b_3,c_2\}$ (item)
  3. $\{c_2,d_1\} \implies \{c_3,d_2\}$ (item)
  4. $\{d_2,e_1\} \implies \{d_3,e_2\}$ (item)
  5. $\{a_3,e_2\} \implies \{a_4,e_3\}$ (item)
  6. $\{a_4,c_3\} \implies \{a_5,c_4\}$ (item)
  7. $\{c_4,e_3\} \implies \{c_5,e_4\}$ (item)
  8. $\{b_3,e_4\} \implies \{b_4,e_5\}$ (item)
  9. $\{b_4,d_3\} \implies \{b_5,d_4\}$ (item)
  10. $\{a_5,d_4\} \implies \{a_6,d_5\}$ (item)

So now we have the following $\{a_6,b_5,c_5,d_5,e_5\}$. Lets assume the other group did something similar so they have $\{z_6,y_5,x_5,w_5,v_5\}$ and we have obtained 20 items so far (optimal).

Now we need to start pairs between the groups. We will do a zig zag pattern from $a - y - c - w - e$.

  1. $\{a_6, y_5\} \implies \{a_7,y_6\}$ (item)
  2. $\{y_6, c_5\} \implies \{y_7,c_6\}$ (item)
  3. $\{c_6, w_5\} \implies \{c_7,w_6\}$ (item)
  4. $\{w_6, e_5\} \implies \{w_7,e_6\}$ (item)

We will do the same for $z-b-x-d-v$.

  1. $\{z_6, b_5\} \implies \{z_7,b_6\}$ (item)
  2. $\{b_6, x_5\} \implies \{b_7,x_6\}$ (item)
  3. $\{x_6, d_5\} \implies \{x_7,d_6\}$ (item)
  4. $\{d_6, v_5\} \implies \{d_7,v_6\}$ (item)

Lastly, we will have the last one $e$ and $v$ pair off with the first.

  1. $\{a_7, v_6\} \implies \{a_8,v_7\}$ (item)
  2. $\{z_7, e_6\} \implies \{z_8,e_7\}$ (item)

Now we have the following:

$$\{a_8, b_7, c_7, d_7, e_7\}$$ $$\{z_8, y_7, x_7, w_7, v_7\}$$

This time, we will do it a bit differently.

  1. $\{a_8, x_7\} \implies \{a_9, x_8\}$ (item)
  2. $\{x_8, e_7\} \implies \{x_9, e_8\}$ (item)
  3. $\{e_8, y_7\} \implies \{e_9, y_8\}$ (item)
  4. $\{y_8, d_7\} \implies \{y_9, d_8\}$ (item)

Similarly, starting from $z$.

  1. $\{z_8, c_7\} \implies \{z_9, c_8\}$ (item)
  2. $\{c_8, v_7\} \implies \{c_9, v_8\}$ (item)
  3. $\{v_8, b_7\} \implies \{v_9, b_8\}$ (item)
  4. $\{b_8, w_8\} \implies \{b_9, w_8\}$ (item)

Again, completing the loop:

  1. $\{d_8, z_9\} \implies \{d_9, z_{10}\}$ (item)
  2. $\{w_8, a_9\} \implies \{w_9, a_{10}\}$ (item)

The following pairings are left;

$$\{b_9,y_9\}, \{c_9,x_9\}, \{d_9,w_9\}, \{e_9,v_9\}$$

And nothing more can be doe. This solution gets us 40 items.

Upper Bound

Given 10 people, there are 45 possible pairings. This would mean that there is an upper bound of 45 items.

However, the first pair to enter the dungeon will be the same level (level 1), so there will be no item awarded.

Similarly, the last pair to enter the dungeon will have gone with all 8 others first and both will be at level 9. Their final trip through the dungeon will not get an item.

Thus, the maximum possible items is 43.

40 Solution

Lets split the people into 2 groups of 5. They will be $\{a_1,b_1,c_1,d_1,e_1\}$ and $\{z_1,y_1,x_1,w_1,v_1\}$. The subscript denotes their level.

The first two to enter the dungeon are $\{a_1,z_1\} \implies \{a_2,z_2\}$. No item is obtained.

Now, the two groups will only pair up amongst themselves. Lets work with the first group. We will do the following pairings.

  1. $\{a_2,b_1\} \implies \{a_3,b_2\}$ (item)
  2. $\{b_2,c_1\} \implies \{b_3,c_2\}$ (item)
  3. $\{c_2,d_1\} \implies \{c_3,d_2\}$ (item)
  4. $\{d_2,e_1\} \implies \{d_3,e_2\}$ (item)
  5. $\{a_3,e_2\} \implies \{a_4,e_3\}$ (item)
  6. $\{a_4,c_3\} \implies \{a_5,c_4\}$ (item)
  7. $\{c_4,e_3\} \implies \{c_5,e_4\}$ (item)
  8. $\{b_3,e_4\} \implies \{b_4,e_5\}$ (item)
  9. $\{b_4,d_3\} \implies \{b_5,d_4\}$ (item)
  10. $\{a_5,d_4\} \implies \{a_6,d_5\}$ (item)

So now we have the following $\{a_6,b_5,c_5,d_5,e_5\}$. Lets assume the other group did something similar so they have $\{z_6,y_5,x_5,w_5,v_5\}$ and we have obtained 20 items so far (optimal).

Now we need to start pairs between the groups. We will do a zig zag pattern from $a - y - c - w - e$.

  1. $\{a_6, y_5\} \implies \{a_7,y_6\}$ (item)
  2. $\{y_6, c_5\} \implies \{y_7,c_6\}$ (item)
  3. $\{c_6, w_5\} \implies \{c_7,w_6\}$ (item)
  4. $\{w_6, e_5\} \implies \{w_7,e_6\}$ (item)

We will do the same for $z-b-x-d-v$.

  1. $\{z_6, b_5\} \implies \{z_7,b_6\}$ (item)
  2. $\{b_6, x_5\} \implies \{b_7,x_6\}$ (item)
  3. $\{x_6, d_5\} \implies \{x_7,d_6\}$ (item)
  4. $\{d_6, v_5\} \implies \{d_7,v_6\}$ (item)

Lastly, we will have the last one $e$ and $v$ pair off with the first.

  1. $\{a_7, v_6\} \implies \{a_8,v_7\}$ (item)
  2. $\{z_7, e_6\} \implies \{z_8,e_7\}$ (item)

Now we have the following:

$$\{a_8, b_7, c_7, d_7, e_7\}$$ $$\{z_8, y_7, x_7, w_7, v_7\}$$

This time, we will do it a bit differently.

  1. $\{a_8, x_7\} \implies \{a_9, x_8\}$ (item)
  2. $\{x_8, e_7\} \implies \{x_9, e_8\}$ (item)
  3. $\{e_8, y_7\} \implies \{e_9, y_8\}$ (item)
  4. $\{y_8, d_7\} \implies \{y_9, d_8\}$ (item)

Similarly, starting from $z$.

  1. $\{z_8, c_7\} \implies \{z_9, c_8\}$ (item)
  2. $\{c_8, v_7\} \implies \{c_9, v_8\}$ (item)
  3. $\{v_8, b_7\} \implies \{v_9, b_8\}$ (item)
  4. $\{b_8, w_8\} \implies \{b_9, w_8\}$ (item)

Again, completing the loop:

  1. $\{d_8, z_9\} \implies \{d_9, z_{10}\}$ (item)
  2. $\{w_8, a_9\} \implies \{w_9, a_{10}\}$ (item)

The following pairings are left;

$$\{b_9,y_9\}, \{c_9,x_9\}, \{d_9,w_9\}, \{e_9,v_9\}$$

And nothing more can be doe. This solution gets us 40 items.

Source Link
Trenin
Trenin
  • 9k
  • 22
  • 53

#Upper Bound#

Given 10 people, there are 45 possible pairings. This would mean that there is an upper bound of 45 items.

However, the first pair to enter the dungeon will be the same level (level 1), so there will be no item awarded.

Similarly, the last pair to enter the dungeon will have gone with all 8 others first and both will be at level 9. Their final trip through the dungeon will not get an item.

Thus, the maximum possible items is 43.

#40 Solution#

Lets split the people into 2 groups of 5. They will be $\{a_1,b_1,c_1,d_1,e_1\}$ and $\{z_1,y_1,x_1,w_1,v_1\}$. The subscript denotes their level.

The first two to enter the dungeon are $\{a_1,z_1\} \implies \{a_2,z_2\}$. No item is obtained.

Now, the two groups will only pair up amongst themselves. Lets work with the first group. We will do the following pairings.

  1. $\{a_2,b_1\} \implies \{a_3,b_2\}$ (item)
  2. $\{b_2,c_1\} \implies \{b_3,c_2\}$ (item)
  3. $\{c_2,d_1\} \implies \{c_3,d_2\}$ (item)
  4. $\{d_2,e_1\} \implies \{d_3,e_2\}$ (item)
  5. $\{a_3,e_2\} \implies \{a_4,e_3\}$ (item)
  6. $\{a_4,c_3\} \implies \{a_5,c_4\}$ (item)
  7. $\{c_4,e_3\} \implies \{c_5,e_4\}$ (item)
  8. $\{b_3,e_4\} \implies \{b_4,e_5\}$ (item)
  9. $\{b_4,d_3\} \implies \{b_5,d_4\}$ (item)
  10. $\{a_5,d_4\} \implies \{a_6,d_5\}$ (item)

So now we have the following $\{a_6,b_5,c_5,d_5,e_5\}$. Lets assume the other group did something similar so they have $\{z_6,y_5,x_5,w_5,v_5\}$ and we have obtained 20 items so far (optimal).

Now we need to start pairs between the groups. We will do a zig zag pattern from $a - y - c - w - e$.

  1. $\{a_6, y_5\} \implies \{a_7,y_6\}$ (item)
  2. $\{y_6, c_5\} \implies \{y_7,c_6\}$ (item)
  3. $\{c_6, w_5\} \implies \{c_7,w_6\}$ (item)
  4. $\{w_6, e_5\} \implies \{w_7,e_6\}$ (item)

We will do the same for $z-b-x-d-v$.

  1. $\{z_6, b_5\} \implies \{z_7,b_6\}$ (item)
  2. $\{b_6, x_5\} \implies \{b_7,x_6\}$ (item)
  3. $\{x_6, d_5\} \implies \{x_7,d_6\}$ (item)
  4. $\{d_6, v_5\} \implies \{d_7,v_6\}$ (item)

Lastly, we will have the last one $e$ and $v$ pair off with the first.

  1. $\{a_7, v_6\} \implies \{a_8,v_7\}$ (item)
  2. $\{z_7, e_6\} \implies \{z_8,e_7\}$ (item)

Now we have the following:

$$\{a_8, b_7, c_7, d_7, e_7\}$$ $$\{z_8, y_7, x_7, w_7, v_7\}$$

This time, we will do it a bit differently.

  1. $\{a_8, x_7\} \implies \{a_9, x_8\}$ (item)
  2. $\{x_8, e_7\} \implies \{x_9, e_8\}$ (item)
  3. $\{e_8, y_7\} \implies \{e_9, y_8\}$ (item)
  4. $\{y_8, d_7\} \implies \{y_9, d_8\}$ (item)

Similarly, starting from $z$.

  1. $\{z_8, c_7\} \implies \{z_9, c_8\}$ (item)
  2. $\{c_8, v_7\} \implies \{c_9, v_8\}$ (item)
  3. $\{v_8, b_7\} \implies \{v_9, b_8\}$ (item)
  4. $\{b_8, w_8\} \implies \{b_9, w_8\}$ (item)

Again, completing the loop:

  1. $\{d_8, z_9\} \implies \{d_9, z_{10}\}$ (item)
  2. $\{w_8, a_9\} \implies \{w_9, a_{10}\}$ (item)

The following pairings are left;

$$\{b_9,y_9\}, \{c_9,x_9\}, \{d_9,w_9\}, \{e_9,v_9\}$$

And nothing more can be doe. This solution gets us 40 items.