Counting and probability gift exchange problem There are 50 people (numbered 1 to 50) and 50 identically wrapped presents around a table at a party. Each present contains an integer dollar amount from $1 to $50, and no two presents contain the same amount. Each person is randomly given one of the presents. Beginning with player #1, each player in turn does one of the following: 


*

*Opens his present and shows everyone the contents; or 

*If another player at the table has an open present, the player whose turn it is may swap presents with that player, and leave the table with the open present. The other player then immediately opens his new present and shows everyone the contents. 
For example, the game could begin as follows: 


*

*Player #1 opens his present. (The game must always begin this way, as there are no open presents with which to swap.) 

*Player #2 decides to swap her present with Player #1. Player #2 takes the money from her newly acquired present and leaves the table. Player #1 opens his new present (which used to belong to Player #2). 

*Player #3 opens her present. (Now Players #1 and #3 have open presents, and Player #2 is still away from the table.) 

*Player #4 decides to swap his present with Player #1. Player #4 takes the money from his newly acquired present and leaves the table. Player #1 opens his new present (which used to belong to Player #4). 
The game ends after all the presents are opened, and all players keep the money in their currently held presents. 
Suppose each player follows a strategy that maximizes the expected value that the player keeps at the end of the game. 
(a) Find, with proof, the strategy each player follows. That is, describe when each player will choose to swap presents with someone, or keep her original present. 
(b) What is the expected number of swaps?
Hints only please*
How would I start this problem? If you give me a hint, please stay online so I can ask you additional questions regarding the problem, or clarification on the hint, or share with you what I figured out using your hint. Thanks! :) 
 A: You said you only wanted hints; on the other hand, it's been quite some time, and the question was just reasked on this site. I've written up the full solution in spoiler blocks below, so you can decide for yourself. In case you still only want hints: Start at the end of the game (see backward induction), find some invariant and prove it by induction. Think about what the last player does and how to characterize the present she gets, and try generalizing that for when $k$ players have yet to play.
The full solution is in two blocks; the first block determines the strategies and the second determines the expected number of swaps; so you can read only one of them if you like. 

First, we can prove by induction that at any point in the game, if $k$ players have yet to move, they will get the best $k$ of the remaining presents. The base case $k=1$ is clear: The last player knows the content of her unopened present, and will either open it if it is the best remaining one, or instead swap for the best remaining one. Now assume that the statement holds for $k-1$ players. The player making the $k$-th to the last move knows which presents remain and, by the induction hypothesis, that the remaining $k-1$ players will get the best $k-1$ presents left after her move. Thus, if she opens her present, she will at most get the $k$-th best remaining present. Her optimal strategy is: If she sees one of the best $k$ remaining, swap for the best she sees and leave. If not, then the unopened ones are exactly the best $k$ remaining, and she should open hers; in this case, by the induction hypothesis, she will be left with the $k$-th best remaining present at the end of the game.

$ $

To calculate the expected number of swaps, note that under these strategies, if a present is opened that is not worse than all the unopened ones, it will be immediately swapped and taken off the table. Thus there is always at most one such present, and it can only be the last one opened. Therefore the probability that the $k$-th to the last player swaps is the probability $k/(k+1)$ that the present just opened was not the worst of the remaining $k+1$ presents. If there are $n$ players, $n-1$ of them have a chance to swap, and the expected number of swaps is

\begin{equation}\sum_{k=1}^{n-1}\frac k{k+1}=\sum_{k=1}^{n-1}\left(1-\frac1{k+1}\right)=\sum_{k=1}^n\left(1-\frac1k\right)=n-H_n\;,\end{equation}
where $H_n$ is the $n$-th harmonic number. For $n=50$, this is

\begin{equation}\frac{141008987635075780359241}{3099044504245996706400}\simeq45.5\;,\end{equation}

and for $n=4$ it is $23/12$, as determined by Barry.

A: This is not a solution, just some thoughts based on an exchange of comments with the OP.  I could be overlooking some simplification, but the problem as stated, with $50$ people, seems awfully complicated, so it seems like a good idea to start with much smaller numbers, where the problem can be easily analyzed completely.
One thing does seem clear in general:  On each person's turn, he or she knows which numbers have already appeared, so he can compute the expected value of the (unopened) present he starts with.  If that expected value is less than the largest number remaining at the table, he should swap with that number.  Where it gets tricky is if the expected value is greater than all the open numbers still at the table.  I think we'll see cases where he should swap anyway, as a protective measure:  By swapping, he can guarantee himself a reasonably large number, whereas by staying at the table he risks either opening his present and discovering it's small, or finding it's large but having it taken away in a swap with a later person.  The final person, of course, doesn't face that dilemma; because he has the final unopened present, he knows exactly what it is, and there's no one to take it away from him if he keeps it.
If there are only two people (instead of $50$), there's not much of a problem:  If person A finds number $1$ when he opens his present, person B will let him keep it.  Otherwise he'll swap.  In either case, person A winds up with number $1$ and person B winds up with $2$.  The expected number of swaps is $1/2$.
With three players it gets a little more interesting.  If A gets $1$, B will let him keep it; C will either swap with B or not, depending on whether B opens the $3$.  On the other hand, if A gets the $3$, B will definitely swap with him; C will then either swap or not, depending on what A got in the swap with B.  Finally, if A gets the 2, B will do best to swap for it:  If he doesn't, then he'll either open his present and find it to be the $1$, or wind up with the $1$ anyway in a swap with C.  All this can be summarized as follows:
$$\begin{align}
123&\to123\quad0\\
132&\to123\quad1\\
213&\to123\quad1\\
231&\to123\quad2\\
312&\to132\quad1\\
321&\to132\quad2
\end{align}$$
where the left hand column shows the $6$ permutations for what each player brings to the table, the middle column shows what each player winds up with (note that player A always gets stuck with the $1$), and the right hand column gives the number of swaps, assuming optimal play.  So for $3$ players, the expected number of swaps is $7/6$.
The $4$-player case should still be manageable:  There are only $24$ permutations to consider, and the logical reasoning players B and C need to employ isn't unduly complicated.  (Player A can only sit at the table and open his gift; player D knows exactly who holds what.)  For example, if A has the $2$, then player B should swap for it even though the expected value of his unopened present is $(1+3+4)/3=2.666\gt2$, because he should think as follows:  If I get the $4$, it'll be taken away from me right away by C; if I get the $3$, it'll still be taken away by C, because he'll know he either holds the $1$ or the $4$ and he's smart enough to figure out that he'll wind up stuck with the $1$ if he doesn't swap for my $3$; so if I don't swap for A's $2$, I'm going to wind up stuck with the $1$.
Indeed, this example leaves me with an idea for what general answer is, even for $50$ people.  Since all the OP wants is a hint, I won't say more at this point except that if I'm right, then the expected number of swaps in the $4$-player case will turn out to be $23/12$.
