I currently have 3 coupons among which you can select the prize (might have more as the end of the year approaches depending on what challenges they post): Valve -33%, Pax Payne 2 -50%, Trine 2 -50%. If you want to do this for funsies, no problem.

There is no other reason for posting this other than the fact that it's the holidays and I think those with more mathematical inclination might want to try it out.

The challenge:

suppose a dinner table shaped like a cross (image snatched from Kyall below ):





The rules are (just assume these to be absolute ):

The sides of the arms can accommodate 15 people each.
The ends can accommodate one person.
Each person sitting at the table can interact with at most three people opposite to them and one person on either side from them (five total).
Each person at the outer edge of an arm can interact with four people.
Each person at the end of an arm, can interact with four people total.
Each person at an inner intersection can interact with seven people total (by turning slightly and shouting a bit).

How many ways are there to scramble these people in such a way that no individual can interact with one or more of the people he or she has already interacted with?

To clarify: no person can talk to any other person he or she has already talked to before during the dinner.

The answer: an algorithm that scrambles the people and proof as to how many times the algorithm can run before placing two people who have already interacted near each other.

The note: I do not have an answer so if only one person participates, the challenge is off. If possible, post your algorithm in code!

Happy holidays!

We have 4 arms with 15 people on each side, that makes 120 people, plus 4 people on each arm's end, total 124 people. At inner edge there's a person that counts for both arms, so we'll lower this number by 4, 120 people left.
Originally each person is allowed to interact with 119 people (of course you cannot interact with yourself; not with so many people around at least).

Lets make sure same person won't seat in inner intersection more than once. Means 119 - 7 = 112 people left.
Whoever was in inner intersection now moves to outer edge; 112 - 4 = 108
There's twice more outer edges than inner intersections, so he'll sit there twice; 108 - 4 = 104
We used up "unique seats", now lets sit him at the table everytime; 104 / 5 = 20.8
1 + 2 + 20 = 23 scrambles.

But this is just random thoughts.

Will be nice for my christmas holiday, but I have a suspicion it's an NP problem, so probably won't be very easy.

That's why I'd prefer the algorithm in code so it's empirically quantifiable, if not by any other standards, then by sheer efficiency of implementation.

I would assume the order in which the arrangements are used matter.. so it's not just about finding a possible arrangement.. as it could block other arrangements down the line after multiple rearrangements, if you want to find the maximum number of rearrangements possible without anyone being able to talk to anyone else they have already talked to.

Another variant, which is probably much easier: What is the minimum number of times you have to move people around, to make it impossible for everyone to sit so that no one can talk to anyone they have talked to before?

Another variant, which is probably much easier: What is the minimum number of times you have to move people around, to make it impossible for everyone to sit so that no one can talk to anyone they have talked to before?

Well people in internal corner interact with 7 people at once. 119 / 7 = 17. So on 18th time it'll be impossible to find 7 new people.