4

I'm not very strong with math so be gentle. I decided against posting this to StackOverflow, even though it has to do heavily with Excel VBA. I think my primary questions belong here.

Let's say I have the numbers 1 through 30 (inclusive), and I'm "matching" them with each other and want to find out a few things:

  1. I'm confident with this, but want confirmation: am I correct in assuming that there are 30! possible ways to arrange the numbers 1 to 30? This feels like the deck of cards situation to me.

The next question is more difficult to describe so I'll attempt to simplify it.

Let's say instead that I have 30 people. I'm pairing people off every day: #1 pairs with #30, #2 pairs with #29, #3 pairs with #28, and so on...

Tomorrow they do the same thing, but since 1 and 30 already met, they can't anymore, ever again. #1 meets with #29 instead, and so on all the way down to #2, once per day until the options are exhausted.

In the end, I have decided that 29 possible outcomes exist, or n - 1. This is because each day you're removing an option that exists for every single person. So by the end of the 29 days, everyone will have met everyone else ONLY once.

My intention here is to produce all the possible outcomes in columns in excel, for n = 30 in this case, but ultimately for any n. I'm attempting to figure out the logic behind that, but wanted to confirm all the math first.

Thanks very much.

Edit: I have some follow up thoughts. The number 435 has been bugging me. I would argue that while 1 meets with 2, there are a number of other possible meetings available for the rest of the people. For example, 3 could meet with: 4, 5, 6...or 30. Does 435 cover all possible potential meetings? It may help to show the second part of my question here which shows a screenshot of partial results of my data: https://stackoverflow.com/questions/43684136/excel-vba-producing-all-combinations-of-a-range-of-values

Thanks again!

Community
  • 1
Ferenth
  • 43
  • 1
    Yes you're right about your first question ($30!$). For your second one, I think you're referring to $n\choose 2$, which in the case of $n=30$ would be $435$. – John Doe Apr 27 '17 at 20:38
  • 1
    Your first thought (about factorial giving the number of arrangements or permutations) is correct. The second part is trickier. If you only need to have pairs of people that meet exactly once, something like what you propose will work, with fifteen pairs meeting each day for $29$ days (and thus covering the $\binom{30}{2}$ possible pairs). – hardmath Apr 27 '17 at 20:39
  • Awesome guys, thanks for the quick replies. Just to clarify...John Doe mentioned 30 Choose 2, which is 435. However, after spending a long time thinking about this, I wasn't quite sure about that? – Ferenth Apr 27 '17 at 20:41
  • 1
    @JohnDoe: I think the second question is to find a largest-possible set of pairwise disjoint perfect matchings. – hmakholm left over Monica Apr 27 '17 at 20:41
  • 1
    @Ferenth: You have a good argument that you can't have more than 29 matchings, but it is not clear (at least not to me) that you can reach as high as 29 matchings. – hmakholm left over Monica Apr 27 '17 at 20:43
  • @HenningMakholm thanks for the reply, could you elaborate? I think with some clarification this might help me understand why my 29 may not be correct. edit: I guess...29 will satisfy my criteria, but that 29 could be 29 of a possible 435 options? – Ferenth Apr 27 '17 at 20:43
  • 1
    The Wikipedia article gives a construction of such parallel pairings, called a 1-factorization of a complete graph on an even number of nodes. So $29$ days of scheduling can be achieved for $30$ people. – hardmath Apr 27 '17 at 20:50
  • 2
    I wasn't saying that 29 is wrong, only that your argument does not prove it is right. (Meanwhile, I found the same reference that @hardmath just cited, to show that 29 is indeed right). – hmakholm left over Monica Apr 27 '17 at 20:51
  • @HenningMakholm Oh! I see, apologies... thanks for the link, I'm going to read that and when I get back into work tomorrow I may request a few more back and forths, or if possible, message you to discuss further. Thanks to everyone else as well who commented so quickly. Much appreciated! I'll do some reading! – Ferenth Apr 27 '17 at 20:52

1 Answers1

4

You're right about the first part.

For the second part, 29 is indeed the correct answer (though your reasoning in itself only proves that it cannot be more than 29).

Here is a concrete way to construct a 29-day meeting schedule:

Appoint one of the persons king and give each of the rest of the persons a number from $1$ up to $29$.

  • To find the day two non-royal will meet, add their numbers and subtract $29$ if the result is $30$ or more. The result is a number between $1$ and $29$, which you interpret as the number of a day.

  • To find the day someone meets the king, add his number to itself and subtract $29$ if the result is $30$ or more.

(This works because every day each person can find someone to meet with that matches this rule: He subtracts his own number from the date and adds $29$ if that gives $0$ or a negative number. The result tells him whom to meet; if he gets his own number back, he will meet with the king.

Being the king is more complex: To find his partner he needs to divide either the date or the date plus $29$, by $2$ -- exactly one of those will be even).

This procedure works for every even number of persons. If we have an odd number of people, at least one of them need to be without a partner each day. The best we can do then is to pretend there is one person more (making an even number), and then cancel all of the pretend person's appointments after we make the plan. In that way it will take as many days as there are persons until everyone has met everyone, and everybody gets one day of rest along the way.

If you're going to implement this on a computer, the "subtract 29 if too large" business can be conveniently implemented by taking (x+y) mod 29 -- or (x+y) % 29, depending on language -- combined with numbering people and days from $0$ to $28$ instead of $1$ to $29$. (Since what is really going on behind the scenes here is artihmetic modulo $29$, calling number 29 number 0 instead will make no substantial difference).

hmakholm left over Monica
  • 286,031
  • Thanks for addressing the odd number of people situation as well, that's certainly something I expect to come across. I think also, describing my original problem as a round-robin type scenario would've helped...forgot to do that. I think part of the issue with my question was also my attachment to 29. I now see it as, for n = 30, it will take 29 "days" to match everyone. However, the total number of possible combinations is much higher than 29 (is it 435?). This is because while 1 is meeting 30, 2 can meet with 28 other people and so on...I have a few more questions but running out of space. – Ferenth Apr 28 '17 at 13:29
  • 1
    @Ferenth: Yes, there are 435 different one-on-one meetings going on. There's a variety of ways to justify that number -- one is that each of the 30 people goes to 29 different meetings, so "someone walks into a meeting room" happens $30\cdot 29=870$ times, and it takes to of these to have a meeting, so there are $870/2=435$ meetings. Note also that 15 meetings a day over 29 days gives $15\cdot 29=435$. – hmakholm left over Monica Apr 28 '17 at 13:43
  • Perfect! I appreciate you being so patient with this. Those 2 numbers 435 and 30! are what I was mainly looking for, so I'll mark this question as answered...I did send you an email to discuss some specifics that are less related to my original question, hopefully you don't mind me bugging you a little more! Thanks also to everyone else who contributed! – Ferenth Apr 28 '17 at 13:48
  • I know this is already considered answered, but have I just found a stack exchange article related to my question in my above comment? http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – Ferenth Apr 28 '17 at 16:45