- #1
Bingk1
- 16
- 0
Hello, I need some ideas on this problem, but there's a bit of an explanation before I get to the actual problem.
Say you have C couples to be arranged over N tables. Rules for arrangement are as follows: 1) Couples may not be seated in the same table (i.e. the husband and wife must be separated) and 2) If a couple is already seated at table I and J, then no other couple may be seated at I and J (i.e. if one member of the couple is seated at table I and the partner at table J, then if a member of another couple is seated at table I, that member's partner should not be seated at table J).
If it helps, you may think of the couples as the edges of a graph and tables as vertices. So rule 1 tells us that there are no loops, and rule 2 tells us there aren't any multiple/parallel edges.
I'm not too concerned about the possible arrangements of the couples. I'm more interested in the number of people seated in each table (e.g. If we have 5 tables, four of which have 1 person seated, and the remaining table has 5 people seated, this could be the result of having 4 husbands seated together and their wives each get their own table. Ofcourse, there are other possibilities, but I'm just concerned about the configuration of the tables)
Now, my problem is this. I have N tables, with table i having Ti people seated. What can I do to determine if the seating is a possible arrangement that follows the above rules?
Some things that I have determined:
1) If the table configuration is to satisfy only the first rule, then it is enough that there should be an even number of people and if the table with the most people seated there has P people, then this should be less than or equal to half the total number of people (I'm 99% sure about this, my proof needs work, but I may not get around to it as this is only for the case of the first rule being satisfied).
2)The most that can be seated in one table is N-1 (N is the number of tables). So, if there is a table with N or more people, then the configuration does not satisfy the rules.
Just to be clear, the labeling of the tables is not important either (e.g. It doesn't matter if Table 1 has 1 person, Tables 2 and 3 have two people each, and Table 4 has 3 people, what matters is that there is a table with 1 person, 2 tables with 2 people each, and another table with 4 people). But for convenience, we may label the tables (i.e. Table 1 has the least number of people seated, Table 2 has the next least number of people seated, etc.). Last thing, tables may be empty.
Any help would be much appreciated! Including guiding me to related literature (i.e. if this looks like it fits in a particular area of math that I'm not aware of, or if there are other similar/related problems).
Thanks in advance! :D
Say you have C couples to be arranged over N tables. Rules for arrangement are as follows: 1) Couples may not be seated in the same table (i.e. the husband and wife must be separated) and 2) If a couple is already seated at table I and J, then no other couple may be seated at I and J (i.e. if one member of the couple is seated at table I and the partner at table J, then if a member of another couple is seated at table I, that member's partner should not be seated at table J).
If it helps, you may think of the couples as the edges of a graph and tables as vertices. So rule 1 tells us that there are no loops, and rule 2 tells us there aren't any multiple/parallel edges.
I'm not too concerned about the possible arrangements of the couples. I'm more interested in the number of people seated in each table (e.g. If we have 5 tables, four of which have 1 person seated, and the remaining table has 5 people seated, this could be the result of having 4 husbands seated together and their wives each get their own table. Ofcourse, there are other possibilities, but I'm just concerned about the configuration of the tables)
Now, my problem is this. I have N tables, with table i having Ti people seated. What can I do to determine if the seating is a possible arrangement that follows the above rules?
Some things that I have determined:
1) If the table configuration is to satisfy only the first rule, then it is enough that there should be an even number of people and if the table with the most people seated there has P people, then this should be less than or equal to half the total number of people (I'm 99% sure about this, my proof needs work, but I may not get around to it as this is only for the case of the first rule being satisfied).
2)The most that can be seated in one table is N-1 (N is the number of tables). So, if there is a table with N or more people, then the configuration does not satisfy the rules.
Just to be clear, the labeling of the tables is not important either (e.g. It doesn't matter if Table 1 has 1 person, Tables 2 and 3 have two people each, and Table 4 has 3 people, what matters is that there is a table with 1 person, 2 tables with 2 people each, and another table with 4 people). But for convenience, we may label the tables (i.e. Table 1 has the least number of people seated, Table 2 has the next least number of people seated, etc.). Last thing, tables may be empty.
Any help would be much appreciated! Including guiding me to related literature (i.e. if this looks like it fits in a particular area of math that I'm not aware of, or if there are other similar/related problems).
Thanks in advance! :D