8
$\begingroup$

You are a lowly party planner, tasked with inviting some Nobs to a wedding dinner, and then seating them appropriately. Now, Nobs are very picky about their seating arrangement: they insist on having their seats positioned and turned so that everyone that they like is strictly in front of them, and everyone else is strictly behind them.

The Nobs will each present you a with list of who they like on the morning of the party. If you are unable to seat the Nobs to their satisfaction, you will be executed!

How many Nobs can you safely invite?

$\endgroup$
  • $\begingroup$ Let's pretend we are not concerned if any of the Nob(s) is/are blinded. $\endgroup$ – Alex Mar 1 '18 at 23:24
  • 2
    $\begingroup$ Are we arranging the Nobs in a line, or in two-dimensional space? $\endgroup$ – Mike Earnest Mar 2 '18 at 0:20
  • $\begingroup$ 2- dimensional plane $\endgroup$ – QuadmasterXLII Mar 2 '18 at 0:34
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Mar 4 '18 at 5:48
  • $\begingroup$ Are only nobs invited or also “normal“ people who might be liked or disliked by the nobs but have no preference on their own? $\endgroup$ – Gimli Mar 4 '18 at 6:58
10
$\begingroup$

I interpret the question as, you can arrange the nobs in 2 dimensions however you like, and draw a line through them where one side is "in front" and the other is "behind". Call this line the front/back line.

At most 3 Nobs can be arranged in every possible set of preferences for those Nobs.

Because

4 Nobs does not work: Suppose you have Nobs A, B, C and D, where A likes B, B likes C, C likes A, and D likes nobody. The only possible way to arrange A, B, and C is in a triangle where the front/back line of each Nob passes between the other 2. These three lines form an inner triangle, and inside of this triangle is the only place nobody is looking, and therefore the only place D can be. But, there's no way to draw a line passing through this triangle that does not pass between any 2 of A, B, and C, ie. a line that would allow D to see nobody, because this triangle is inside of the triangle formed by A, B, and C. So this set of preferences, with 4 Nobs, can't be satisfied.

3 Nobs does work: If you arrange 2 Nobs so that their front/back lines intersect, and then face them such that they are happy with the other one, you can place the third Nob in whichever of the 4 regions formed by these lines would satisfy the other 2 Nobs, and then draw a front/back line either between the first 2 Nobs (if Nob C likes only one) or not between the first 2 Nobs (otherwise), and you will be able to face Nob C along that line such that they are satisfied.

I strongly suspect that if you generalize the problem to N dimensions (eg. you can hang Nobs in the air looking slantwise),

N+1 Nobs is the maximum you can safely accommodate.

$\endgroup$
  • $\begingroup$ @Separatrix Yes, when I said eg. "A likes B", I meant "and nobody else" $\endgroup$ – Vitruvius Mar 2 '18 at 9:30
3
$\begingroup$

I am interpreting the question differently from Jaap Scherphuis: I imagine a 2D plane with each Nob able to rotate freely, dividing the room into those in front and those behind. Obviously in 3D you can seat more Nobs, but it will be harder to keep them in their chairs.

In that case, the most you can safely invite is:

3

because

Drawing the line that divides front and back for each of the first 3 Nobs divides the room into at most 7 regions. But there are 8 possibilities for how the first three Nobs regard the fourth (liked/not liked)^(number of Nobs). So it is always possible for the 4th Nob to be someone who cannot be put in the room.

$\endgroup$
  • 1
    $\begingroup$ This implies that for every set of 3 Nobs and their preferences, there is a 4th Nob who, not even taking into account his own preferences, cannot be placed in a way to satisfy the other 3. But this is not true, because you can re-arrange the other 3 as needed. For example, if the first 3 Nobs all like none of the others in the 3, then for any possible opinions they have of the 4th, you can still arrange them to accommodate the 4th. $\endgroup$ – Vitruvius Mar 2 '18 at 0:32
  • $\begingroup$ No, you can't insert a 4th Nob that the first three all like. $\endgroup$ – Rupert Morrish Mar 2 '18 at 0:34
  • 1
    $\begingroup$ You can: Arrange A, B, and C so that C is behind the point where A and B's front/back intersect, and C's front/back line is parallel to line AB. Then you have none of A, B, and C seeing each other, and a region where A, B, and C all see. You can re-order A, B, and C as needed within this arrangement to accommodate D's preferences. $\endgroup$ – Vitruvius Mar 2 '18 at 0:37
  • $\begingroup$ In that case, you can't accommodate the D that A and B like but C doesn't, because all of A(intersect)B is included in C. $\endgroup$ – Rupert Morrish Mar 2 '18 at 1:42
  • 1
    $\begingroup$ Ah, the point I was missing is that you can move the chairs after they arrive. $\endgroup$ – Rupert Morrish Mar 2 '18 at 2:20
1
$\begingroup$

I interpret the "strictly in front/behind" as meaning that the nobs will have to be arranged in a straight line, each facing forward or backward along that line.

Two observations:
1. It is possible for everyone to like only one other person and not like everyone else. For example with three people A, B, C, you could have A likes B, B likes C, C likes A with none of those being reciprocated.
2. The two people at the start/end of the line will have to either like everyone else or not like everyone.

As soon as you have 3 or more people, the situation in #1 means that no one likes everyone and no one hates everyone, so observation #2 means no arrangement is possible.

Two people is always possible. You can turn each one either to face the other or turned away from the other depending on whether they like them or not.

$\endgroup$
1
$\begingroup$

My guess is:

at most 2 Nobs

In this case,

if we invited only 2 Nobs (say A and B), then we can seat these 2 in a column, where they will be facing each other, facing away from each other or looking at other's back depends on their like / dislike status.

Now what happens if we invite one more?

That is, we add Nob C. Now in the case where both Nob A and B like each other AND each also likes Nob C, A and B will be facing each other, where Nob C will have to be seated between them since A and B both liked C. Now if C likes both A and B, while sitting in between A and B, the lowly party planner will be executed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.