Leveling up and Getting Items!

Question

You are playing an online RPG game with 9 friends of yours (10 people in total) and in the game, there is a 2-player dungeon where you level up every time you enter and complete it. Only up to two players are allowed inside it at a time. At the beginning of the game, everybody is level 1 as usual. Before the game released, there was a beta and you know how to level up fast from it, but there are some tricks you discovered.

• You cannot complete the dungeon alone.
• After completing this 2-player dungeon with your friend, you and your friend will get 1 level.
• If you play the dungeon with someone exactly one level below you, you will get an extra item at the end of the dungeon, but you cannot enter the dungeon with a friend more than one level below you.
• If you try to enter the dungeon with the same person again, no one will get any experience to level up or item.
• You can share the items later, they are not soulbound!

What is the maximum number of extra items you will get in total as a group from this dungeon?

Answer 1

Let's start low: 40.

Let's name the players A,B,C,D,E,F,G,H,I,J and define "n-next" of a player to be the player who is positioned n places afterwards, with round wrapping. Eg, the 2-next of A is C, and the 3-next of J is C.

1. First, AB go in to become level 2.
2. Then, for eight rounds, the player who was 1-next of his partner in the previous round goes in along with their 1-next (ie: BC,CD,DE...IJ). This yields 8 EI(Extra Items),as each time one level 1 and one level 2 go in. Now A,J are level 2 and the rest are level 3.
3. Each time there are 2 players with a specific level and all the others have one level more, there is always (checked practically but can't prove) a set of 10 pairs such that a) All pairs have the same "distance" between players, b) there is an order to go in so that, after the 10 pairs are finished, all the levels are 2 higher that the beginning 3) each pair produces an EI. Thus, for distance of 2,3 and 4, we have 30 EI.
4. Unfortunately, the same is not true for distance 5. You can only find 2 pairs here, the two low-levels and their corresponding 5-next.

This yields a total of 8+30+2=40 items.

Answer 2

• Between 10 friends, there are only 45 unique pairs.
• Each friend will participate exactly 9 times, which means after 45 rounds everyone will be level 10.
• Since it's impossible to get an item on the first & last run, there is a theoretical maximum of 43 items you can get.

However, due to some restrictions, it seems to me like it's impossible to get this theoretical maximum.

Here's an example for 40 items. I wrote a conjecture for the maximum possible at the bottom.

Red index means no item, Green index means item and Yellow squares are the two that leveled up.

Conjecture:

The maximum possible items you can get for n > 3 is:
n& - n/2 for even numbers and
n& - (n-1)/2 for odd numbers, where
n& is 1 + 2 + 3 + ... + (n-1).

For now I will leave it at that and see if anyone can prove this. Otherwise, I might come back to this.

Answer 3

@Oray congrats this question is glorious!

I agree with everybody else on 40, but I'll try to explain why that's the max in my own special way.

The easiest way for me to understand what's happening is to break everything down into cycles. If a player just leveled up once, in the next round they should help another player level up. So 1 helps 2, 2 helps 3, 3 helps 4 and so on. So a cycle is when, after some number of pairs go in the dungeon, it comes back around to the first guy who went in.


Each cycle is going to start with player 1 and then by taking constant steps a bunch of cycles emerge. Some of these cycles have to start with player 2 because 10 is divisible by 2. But 10 is also divisible by 5 and we see that the "5-apart" cycles (which are all a single pair in length) will start with a 1,2,3,4,5.

Next, how do you build a long chain of functional pairing that give you items? Take the [1,2] pairing and save it for the very end. Take the remainder of the "1 apart" cycle and that's where we start. The next part is fun, just add every other cycle one after the other. You'll notice that every cycle we add will always give us the coveted extra items we are looking for. We skipped [1,2] initially, so any cycle starting on a 1 or a 2 is going work perfectly for us.

]

But maybe you'll see the problem. Of the "5-apart" cycles, three of them do not start with a 1 or a 2. They do not help us in any way. The big reason this isn't obvious is because you can very well take those pairs and mix them up into one of the other cycles we already had. If you're clever about it, you can actually make other kinds of cycles using those 3 pairs and then you might think that you can beat the 40 item mark. But, no matter what you do, three pairs (from somewhere) will always "drop out" from what you're doing. It's a bad explanation, but it boils down to the fact that these cycles do not want a player to be in them an odd number of times.

Like everybody else said, the first and 45th pair cannot possibly be different levels, so of the 45 total pairings, we conclude only 40 extra items is possible.

Answer 4

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$.

21. $\{a_6, y_5\} \implies \{a_7,y_6\}$ (item)
22. $\{y_6, c_5\} \implies \{y_7,c_6\}$ (item)
23. $\{c_6, w_5\} \implies \{c_7,w_6\}$ (item)
24. $\{w_6, e_5\} \implies \{w_7,e_6\}$ (item)

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

25. $\{z_6, b_5\} \implies \{z_7,b_6\}$ (item)
26. $\{b_6, x_5\} \implies \{b_7,x_6\}$ (item)
27. $\{x_6, d_5\} \implies \{x_7,d_6\}$ (item)
28. $\{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.

29. $\{a_7, v_6\} \implies \{a_8,v_7\}$ (item)
30. $\{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.

31. $\{a_8, x_7\} \implies \{a_9, x_8\}$ (item)
32. $\{x_8, e_7\} \implies \{x_9, e_8\}$ (item)
33. $\{e_8, y_7\} \implies \{e_9, y_8\}$ (item)
34. $\{y_8, d_7\} \implies \{y_9, d_8\}$ (item)

Similarly, starting from $z$.

35. $\{z_8, c_7\} \implies \{z_9, c_8\}$ (item)
36. $\{c_8, v_7\} \implies \{c_9, v_8\}$ (item)
37. $\{v_8, b_7\} \implies \{v_9, b_8\}$ (item)
38. $\{b_8, w_8\} \implies \{b_9, w_8\}$ (item)

Again, completing the loop:

39. $\{d_8, z_9\} \implies \{d_9, z_{10}\}$ (item)
40. $\{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.