Here is the problem:
There are 1000 people in a hall. Initially one person had his hand painted. Every second everyone shakes their hand with someone else (in the sense that every second 500 couples form and the two people in the same couple shake hands with each other). In addition no two people can ever shake hands more than once. Of course whenever someone with a painted hand shakes the hand of someone who has it clean, it gets it painted. How much time, at most, is needed to paint all the hands? Prove it.
Clarification: we are only considering games that run the full length, i.e. the game has to be able to get to the last round after which all possible handshakes have occurred, no dead ends allowed. So the question is posed within the framework of such games.
My considerations:
I've tried pretty hard to get the answer for a general n people game, or even for this 1000 people game, but there really seems to be nothing helpful to prove it or even guess it or find it easily for large n, especially given the fact that I have manually bashed the first cases for n = 2,4,6,8,10,12 (the answers being 1,2,3,5,6,8 rounds respectively) which look to have no useful relationship whatsoever between eachother or with n. I think the greedy algorithm is optimal, but I haven't even bothered proving that, since it doesn't really help to find the answer to the problem and prove it, so at times I've just tried to assume it, but even then it didn't quite get me anywhere. Also I don't think there is some beautifully simple symmetry argument to get an answer here, because that should hopefully be reflected in the cases for the first few n, but maybe I am missing it, I couldn't think of anything of that kind.
What I am thinking now is that the answer might be some really complicated non closed form/non elementary function of n, or possibly some not even expressible function of n (this last statement in the sense that it's some function who's values for each given n are defined to be the ones given by such a game like this one, or some isomorphic problem, and there definitely are such kind of functions out there, so this could be a possibility). But if any of these last options I've given are correct, how could one possibly prove that?
Thank you very much for the help, I hope there is someone who can solve this.
from Hot Weekly Questions - Mathematics Stack Exchange
Gen
Post a Comment