tag:blogger.com,1999:blog-4278359056787870942.post5571071947383022298..comments2023-09-16T06:51:29.097-07:00Comments on Singular Value Decomposition: Holiday Math - Bonus Problem!Alexander Monthttp://www.blogger.com/profile/09406587991425120623noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-4278359056787870942.post-14288441425054858722008-12-22T18:15:00.000-08:002008-12-22T18:15:00.000-08:00It is correct that Uncle Sam assumed that everyone...It is correct that Uncle Sam assumed that everyone has a different favorite gift, which is not necessarily true.<BR/><BR/>I don't really understand Dan's reasoning, but here is my solution:<BR/><BR/>---<BR/><BR/>Suppose that two people, X and Y, ended up with gifts that the other one liked better. Suppose that X selected his gift in the Ith round, while Y selected his in the Jth round. (These round numbers mean the last time that the players in question selected a gift, so they selected the gift they ended up with.) Suppose I < J. Then during the Jth round, when it is Y's turn to select a gift, X's gift will be available (since it was last selected in a previous round) so he would have selected that gift over his one. The same argument applies the other way around if I > J. Thus we must have I = J. Assume that in that round, X selected before Y. Then when X selected, both X's and Y's gifts were available, so he would have selected Y's gift because that's the one he prefers. Of course if Y was the first to select in that round, the he would have selected X's gift instead. Thus there is a contradiction.Alexander Monthttps://www.blogger.com/profile/09406587991425120623noreply@blogger.comtag:blogger.com,1999:blog-4278359056787870942.post-6097361389606471962008-12-22T17:54:00.000-08:002008-12-22T17:54:00.000-08:00Uncle Sam is assuming that Player I's favorite gif...Uncle Sam is assuming that Player I's favorite gift is no one else's favorite gift. But you haven't assumed that, right? I mean, it is possible for two players to actually have identical gift rankings, right?<BR/><BR/>I would start from the Nth player. The Nth player absolutely gets his or her favorite gift. If it was from the pile that means the (N-1)th player keeps his or her favorite gift -- she didn't like the one remaining in the pile as much or she would have taken it.<BR/><BR/>If Player N takes it from Player N-1 then player N-1 will get her second favorite gift.<BR/><BR/>If Player N takes it from a different player, then player N-1 might get her favorite gift taken from her, so she will end up with her second or third favorite gift.<BR/><BR/>Going backwards like this, I think that we end up with a Pareto Optimal situation. But I don't have the patience to think this through completely. But I'm guessing that I'm missing something or you wouldn't have posed this problem. Where is the flaw in my reasoning?Dan Monthttps://www.blogger.com/profile/05893970837257594648noreply@blogger.comtag:blogger.com,1999:blog-4278359056787870942.post-41670071322497669412008-12-22T11:12:00.000-08:002008-12-22T11:12:00.000-08:00Alex,I must be missing something. I would think t...Alex,<BR/><BR/>I must be missing something. I would think that play would go like this...<BR/><BR/>Round 1, Player 1 picks the gift that they like the most. No reason to take from somebody else. Nobody has a gift yet. Round over.<BR/><BR/>Round 2; Player 2 picks the gift from the pile that they like most. They would not take the gift from player 1 as that isn't their favorite gift. They would pick their favorite from the pile. Round over.<BR/><BR/>And so on... <BR/><BR/>Nobody would ever take a gift from someone else as the gift that they want is still remaining in the pile.<BR/><BR/>And, everyone would wind up with their favorite gift.Awesome in Arlingtonhttps://www.blogger.com/profile/12010145121052705808noreply@blogger.com