# Math challenge (no particular purpose, prize = a -50% coupon on steam)

This topic is 2545 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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!

##### Share on other sites
I think the simplest solution would be to take all the positions, pick a few of the positions as stationary positions, pick some positions as moving positions, and of those moving positions a person is moved a certain number of spaces in a certain direction depending on the position they were in. The positions that are stationary/moved would probably change round to round, but I don't think you would get many rounds out of it before 2 people who had talked previously are already talking again. However if you lower the scope so your objective is to minimise the amount of conversation between any two people you can probably get a substantial number of moves out of the system before any two people talk to each other 3 times for example.

Also, if you set one of the guidelines for success for this algorithm being that the best algorithm is the one that utilizes the fewest number of moves ( i.e. A move of 5 seats around the table, rather than just swapping to the other side) we might get some really cool algorithms up in here.

So bored I whipped up an image:

##### Share on other sites
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.

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

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites

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.

1. 1
2. 2
3. 3
Rutin
20
4. 4
khawk
14
5. 5

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633655
• Total Posts
3013187
×