19
$\begingroup$

At PuzzlingCorp, all employees have a break at 10:00am sharp every day, and immediately proceed to get either plain water or a diet coke.

The people at PuzzlingCorp are also highly susceptible to peer pressure. The way this works is as follows: each one of the employees has a set of other employees that that employee views as her friends. (Friendship is a symmetric relationship.) At 10:00am, when employees drink their morning drinks, each one of them observes the water/diet coke choice of the rest of her peer group. If, in the group, there is a majority for water, the next day that employee will get water for herself. If there is a majority for diet coke, she will go with diet coke. If there is a tie, the employee will simply drink the following day whatever she had to drink on the previous day.

Question. It is clear that ultimately the drinking patterns of PuzzlingCorp's employees will settle on a cycle. What are possible lengths of this cycle?

(Hint: only two lengths are at all possible.)

$\endgroup$
  • 4
    $\begingroup$ Ooh, Diet Coke - @Rubio had better be the one to solve this puzzle :D Also, very nice puzzle, Dominic! You've had some excellent content for a new user. $\endgroup$ – Brandon_J May 31 at 12:24
  • 3
    $\begingroup$ Is Diet Pepsi ok? $\endgroup$ – Wondercricket May 31 at 17:58
  • 2
    $\begingroup$ For the record, Diet Pepsi is swill. I'm a mod. Fight me. ;) $\endgroup$ – Rubio Jun 1 at 1:59
  • 1
    $\begingroup$ I don't know what the etiquette is regarding giving links to answers, but an answer to (a more general form of) this question can be found in E. Goles, J. Olivos: "Periodic behaviour of generalized threshold functions", Discrete Mathematics 30(2), 1980, 187-189. $\endgroup$ – Dan Petersen Jun 10 at 18:16
7
$\begingroup$

The two possible cycle lengths are:

1 (e.g. when all employees have no friends, so everybody stays with their current drink.)
2 (e.g. when there are two employees, friends of each other, drinking something different. Both will switch drinks each day in this case.)

I have yet to figure out why these are the only ones, but here's a thought:

While an employee (call him/her A) doesn't have that much influence over what they're drinking themselves the next day (they only do in case of a tie), they are the most important contributor (either alone or tied) for their drink two days later; for another employee (B) to have that much influence, they'd need to be friends with all of A's friends but not be friends with A.

$\endgroup$
  • $\begingroup$ Do external relationships affect these groups? Say Bob is a friend to one member of Group A and a friend to one member of Group B? $\endgroup$ – LeppyR64 May 31 at 13:16
7
$\begingroup$

@Glorfindel is absolutely right, but I'd like to elaborate on why he's right. Unfortunately, my elaboration appears to be somewhat limited - see the end of the post.

When (in any group) there is a majority of people drinking one drink on day one,

the people in the majority will keep drinking what they have been drinking, because either the majority of their friends are drinking the same drink (in, for example, a 3v1 scenario) or because it's a tie among their friends (2v1,3v2, 4v3, 5v4, etc.).

and

the people in the minority will obviously switch to the majority drink, resulting in everyone in a friend group drinking the same drink forever. This results in a one-day cycle.

Note that the above scenario is guaranteed to occur with any odd-numbered friend group, including one person, because there must be a majority in such a group. The above scenario will occur in the majority of even-numbered friend groups (not all, because there can be a tie).


When (in any group) there are equal numbers of people drinking one drink on day one,

Every person perceives themselves to be in the minority - in a group of 8, every person perceives that only 3 of their friends are drinking their drink, and they also see 4 friends drinking the other drink. In a group of 2, they see their only friend drinking the other drink. In a group of 5438 people, they see 2719 people drinking the opposite drink, and 2718 people drinking their drink. Thus, Everyone will switch every day, resulting in a two-day cycle.

Well, @LeppyR64 has pointed out a significant problem with my answer. I only account for completely integrated friend groups - as in, scenarios where everyone in a group of friends knows everyone else in that group and no one else. This will affect my answer, and I am currently working on fixing it.

$\endgroup$
  • 2
    $\begingroup$ Do external relationships affect these groups? Say Bob is a friend to one member of Group A and a friend to one member of Group B? $\endgroup$ – LeppyR64 May 31 at 13:15
  • $\begingroup$ @LeppyR64 Hmm...I'll have to think about this. I think that I'm still right, but I need a little bit more explanation before I can confidently say so. Thanks for bringing this up. $\endgroup$ – Brandon_J May 31 at 13:19
  • $\begingroup$ If I'm honest, my suspicion is the same, but I also agree that I couldn't confidently say so immediately. $\endgroup$ – LeppyR64 May 31 at 13:19
  • 1
    $\begingroup$ BTW, the mathematical terminology for what you seem to mean by "completely integrated friend groups" is "equivalence class", and the term for friendship giving rise to this is "transitive" (an equivalence relation has to be symmetric, which is already given in the puzzle statement, and reflexive, i.e. everyone has to be friends with themselves). $\endgroup$ – Acccumulation May 31 at 15:36
  • 2
    $\begingroup$ The possibility of non-transitive groups makes it possible to have a mixture of people who water every day, people who only drink diet coke every day, people who drink water on even days only, and people who drink diet coke on even days only. For example, if the vertices of an octahedron are up/down/north/south/east/west, and on even days up, north, and south drink water, then on odd days up, east, and west will drink water. $\endgroup$ – supercat May 31 at 22:46

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.