David Ding: Riddler Classic December 16, 2022

Every Christmas, Gary’s family has a gift exchange. And every year, there is a big fight over how much folks should spend on the gifts. This year, they decided to pair up. So if Virginia gives Justin a gift, then Justin gives Virginia a gift. This way, while there will still be arguments, only two people will be involved in each argument.

There are 20 people in the gift exchange. In the first round, everyone writes down the name of a random person (other than themselves) and the names go in a hat. Then if two people randomly pick each other’s names out of that hat, they will exchange gifts, and they no longer participate in the drawing. The remaining family members go on to round two. Again, they write down the name of anyone left, and again, any two people who pick each other exchange gifts.

This continues until everyone is paired up. And yes, if exactly two people remain, they still go through the process of selecting each other, even though they know who their partner will be.

On average, what is the expected number of rounds until everyone is paired up?

We are using Monte-Carlo simulation via MATLAB with one million simulations. There are two scenarios: without replacment and with replacement. For without replacement, below is the code for one trial:

function rounds = getAvgRoundsNoReplacement(N)
    % Given N potential pairs of 2N people, use the Monte-Carlo method to
    % determine the average number of rounds before everyone is paired off.
    % Assume NO replacement.

    rounds = 0;
    pairs = N;

    while pairs > 0
        rounds = rounds + 1;
        totalPeople = 2*pairs;
        % We first have everyone write down their preferred gift target
        giftMatrix = NaN(totalPeople, totalPeople - 1); % They can't write down their own names

        for k = 1:totalPeople
            row = 1:totalPeople;
            row = row(row ~= k);
            giftMatrix(k, :) = row;
        end

        % Have each person write down their names and add to the pool
        recPool = NaN(totalPeople, 1);
        for k = 1:totalPeople
            idx = randi(totalPeople - 1);  
            recPool(k) = giftMatrix(k, idx);
        end

        % Next we do the draw;
        % Assume NO replacement
        giftList = NaN(totalPeople, 1);
        giftIdx = randperm(totalPeople);
        for k = 1:totalPeople
            giftList(k) = recPool(giftIdx(k));
        end

        % Finally we see if pairs can be matched
        for k = 1:totalPeople
            if giftList(k) == k
                continue; % No self-gifting!
            end

            lucky = giftList(k);
            if giftList(k) ~= -1 && giftList(lucky) == k
                % found a match!
                pairs = pairs - 1; 

                % Ensuring no double counting
                giftList(k) = -1;
                giftList(lucky) = -1;
            end
        end
    end

end

% Next we do the draw;
% Assume with replacement
giftList = NaN(totalPeople, 1);
for k = 1:totalPeople
	giftIdx = randi(totalPeople);
	giftList(k) = recPool(giftIdx);
end

So for the above, we let each person pick something from the pool and two people can pick the same slip of paper.

It is interesting to see that for both cases, they have similar distributions, but the without replacement case has a lower mean than its replacement counterpart. An intuitive explanation for this is that with replacement, it is more likely for multiple people to draw the same person. However, that lucky person can only form a gift-giving pair with only one other person, thereby prolonging the process.

Therefore, if you want the process to finish faster, go with the no replacements rule.

Riddler Classic: December 16, 2022

Giving and Taking