seating arrangement

It would be unfair of me to expect an airtight proof for this one, for reasons I will explain later. But maybe you can tell me what you think the answer probably is.

k is an arbitrary positive integer.

At Podunk College there are k committees, each consisting of k faculty members, and all committees meet in the same room, which has k chairs. At most one person belongs to the intersection of any two committees. The members have OCD, so... is it always possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs?

At first glance, I thought it was a trivially simple "yes".

After thinking about it some more, I don't see a way to construct groups that conflict.

If there were more than k groups, it would certainly be possible to create a situation were each person couldn't have their own chair.

Originally posted by Paul Dirac II
It would be unfair of me to expect an airtight proof for this one, for reasons I will explain later. But maybe you can tell me what you think the answer probably is.

k is an arbitrary positive integer.

At Podunk College there are k committees, each consisting of k faculty members, and all committees meet in the same room, whi ...[text shortened]... each member sits in the same chair for all the different committees to which he or she belongs?

If it were not possible then an airtight proof could be constructed by giving a counter-example. In the pre-amble you said that you didn't expect an airtight proof for reasons you would explain later. Therefore it must be possible for the faculty members to sit in the same seats in all the sessions that they attend.

Originally posted by forkedknight
At first glance, I thought it was a trivially simple "yes".

After thinking about it some more, I don't see a way to construct groups that conflict.

If there were more than k groups, it would certainly be possible to create a situation were each person couldn't have their own chair.

I tend to agree. I wonder if it is possible to construct a proof by iteration, or some kind of diagonal argument. For a proof by iteration the cases k = 0, 1, 2 are trivial. In case 2 we either have committee 1 with {a, b} in and committee 2 with {c, d} in, or we have committee 2 with {a, c} in.

Doing the first step of the iteration by hand:

Take the two people committees {a, b} and {a, c} and add a person to each committee, we can't add a, b or c to either of these committees as either they are already on the committee or they're in the other one and a is already in both, call the new people d and e - they have to be different people again because a is already in both committees:

This gives us:
{a, b, d} and {a, c, e}
If committee 3 has a in then we need two more people f and g as a would prevent anyone else already on a committee from being on committee 3. Suppose instead we have b on committee 3, then both a and d are ruled out of being on that committee and we can either add two new person or one and only one of c or e to the committee and a new person, suppose we add e and f. Our three committees written in seating order are then:
{a, b, d}
{a, c, e}
{f, b, e}

Iterating by hand again, the case where a is in all three committees from the previous step is easy, the remaining committee members cannot be in any of the other committees. So starting from the less trivial case (and relabelling to make it less obscure):

{a, b, c, d}
{a, e, f, g}
{h, b, f, i} - again I've written them in seating order
There are a lot of possibilities for committee 4, but I don't think there's a conflict. The problem is I don't see a systematic way of generating a proof by iteration.

Good thoughts above. 🙂

In a day or two I'll cough up the official mathematicians' status of this problem.

Originally posted by Paul Dirac II
It would be unfair of me to expect an airtight proof for this one, for reasons I will explain later. But maybe you can tell me what you think the answer probably is.

k is an arbitrary positive integer.

At Podunk College there are k committees, each consisting of k faculty members, and all committees meet in the same room, whi ...[text shortened]... each member sits in the same chair for all the different committees to which he or she belongs?

Intuitively, and going against the forum grain here: no. (And stop caring about unimportant details such as the chair you sit on - focus on cutting meeting time instead!)

Originally posted by Shallow Blue
Intuitively, and going against the forum grain here: no. (And stop caring about unimportant details such as the chair you sit on - focus on cutting meeting time instead!)

DeepThought's law of committee meetings is that all meetings overrun to fill all time until the next meeting is due to start. It's just one of those things.

Suppose there are (k - 1) committees which all have k members and fulfil the criteria given in the OP. Take the first person, in other words the person in chair 1, from committee 1 the person in chair 2 from committee 2 and so on. We need one new person from the infinite pool of faculty members to go into seat k. This would fulfil the requirements except that I haven't shown that the intersection rule is respected (this is the diagonal argument I referred to earlier).

I think there is an ambiguity in the question. What does "Is this always possible?" mean? If there are enough faculty members then we simply enforce a rule that no one is on more than one committee and the criteria are fulfilled. If there are exactly k faculty members then it is never possible as all the committees have to be the same (and it breaks the only one intersection rule).

I think that this is a truly hard problem. Intuitively the critical case is where there is exactly one faculty member in the intersection between each committee and the set of intersections has exactly k members. I'm still stuck on a way of proceeding though.

Originally posted by DeepThought
I think there is an ambiguity in the question. What does "Is this always possible?" mean?

If I haven't goofed up in my thinking, for any fixed value of k the number of faculty involved can vary through any value of k^2 - k + 1 up to and including k^2. So when the question asks "Is this always possible?" it is asking you to examine all the cases falling in that range for that value of k, and figure out if the answer is "yes" or "no." If the answer is "no" for at least one value of k, you are done because you have identified a counterexample. If the answer is "yes" at one value of k, and if you can show that it has to continue being "yes" at higher values, you are able to say "yes" in all generality.

My formula above cannot be right, because I just drew up an example with k=5 in which there are 18 faculty members total.

Anyway, the three members are leaning this way:
forkedknight --> Yes
DeepThought --> Yes
Shallow Blue --> No

I can't say which of you are right. 😕

A "yes" answer was conjectured in 1972, and a money prize was offered for a proof (though apparently not for a disproof).

The staffing of committees can be illustrated with a network of vertices and edges ("graph theory" a.k.a. "network theory" ) with the vertices representing the faculty members and the edges indicating that a pair of faculty members are in the same committee, and the chairs can be denoted by coloring vertices. A red vertex means that member represented by the vertex sits in the red chair for all of his or her committee meetings.

An example for k=4 and 11 faculty members is shown at this link:
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture

Finding a counterexample in the context of graph theory would mean drawing a graph for committee membership in which at least one edge was forced to join vertices of the same color, meaning multiple butts would have to share the same chair. Or equivalently, more than k colors would need to be utilized in order that an edge never joins two vertices with the same color, meaning extra chairs (not just k of them) would have to be kept on hand for certain committee meetings in order to keep a single butt in a single chair.

The difficulty of proving a "yes" is why I said it would be "unfair to expect an airtight proof."

By the way, mathematician Paul Erdős is worth reading about if you get the chance. He was a single-minded savant. He had no other hobbies.

Originally posted by Paul Dirac II
If I haven't goofed up in my thinking, for any fixed value of k the number of faculty involved can vary through any value of k^2 - k + 1 up to and including k^2. So when the question asks "Is this always possible?" it is asking you to examine all the cases falling in that range for that value of k, and figure out if t ...[text shortened]... at it has to continue being "yes" at higher values, you are able to say "yes" in all generality.

I wasn't accusing you of getting the question wrong - I just wanted clarification of what "is this always possible" meant - you've given that. Using graph theory hadn't occurred to me - I was trying to write it down in terms of set theory (and not making any progress!).

some trivial answers:

Since at most 1 person is member of two committees:

* If the same person is member of all k committees, there ios no problem.
* If no person is member of two committees there is no problem.

In fact I think that the answer has to be yes on this rather heuristic argument: Since no person can sit in more than two committees and we only have k committees only k-1 people can sit in two committes. Since we do have k places only k-1 places are fixed for the people on two committees. The other are taken by other people.

This sounds so trivial that there must be an error somewhere.

Edit: In fact this is Deep Thoughts argument in a different formulation. Only that I claim that the set of intersecting member is k-1 instead of k. lets see:

3 committees members A and B are on committee1 and one more (committee2 for A and committee 3 for B) the set of intersections is k-1...
4 committees A B C are member of c1, a of c2, b of c3, C of c4: k-1.

Again: what did I miss?

Actually even if we had k people sitting in two committees wwe still could assign them to seats s1 to sk...so with the boundary condition of at most 1 we are fine.

Can you point us to the original problem? I fear that there must be another condition.

Originally posted by Ponderable
Can you point us to the original problem? I fear that there must be another condition.

The Wikipedia page I linked to in post 9 is the only place I have seen this problem. I was essentially quoting a paragraph from that page, but I threw in the "Podunk College" bit.

My brother used to sing a song that went, "Podunk City here I come / right back where I started from / open up that outhouse door" in the car on vacation trips. 😛

Originally posted by Ponderable
some trivial answers:

Since [b]at most 1 person is member of two committees:

* If the same person is member of all k committees, there ios no problem.
* If no person is member of two committees there is no problem.

In fact I think that the answer has to be yes on this rather heuristic argument: Since no person can sit in more than two commit ...[text shortened]...
4 committees A B C are member of c1, a of c2, b of c3, C of c4: k-1.

Again: what did I miss?[/b]

What I missed was "any of two".

So for the four committees we have

K1.....K2.....K3.....K4

A......A......H......H
B......E......B......E
C......F......F......J
D......G.....I......I

I am still about to bring in some light into this. I have downloaded the latest proof which is quite hard to follow...