Jump to content
  • Advertisement
Sign in to follow this  
irreversible

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.

If you intended to correct an error in the post then please contact us.

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 :D):


hmmmath.jpg


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 this post


Link to post
Share on other sites
Advertisement
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:


hmmmath.jpg

Uploaded with ImageShack.us

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!