Math in Everyday Life

[SpooN]

First of all I congratulate it to reading my post despite the terrifying title. You are either a math enthusiast as myself and will surely enjoy it or you are just a brave forum knight not afraid to fight the the horrors within and I challenge you hereby to do so:

In this thread I want to post little problems that are solvable with little or no professional training. Please feel free to do the same but be aware that I don't want it to be a common riddle thread.

So let me begin with the first problem:
Most recently some friends and I had a little winetasting going naturally hand in hand with frequent rounds of dinking classes. Although it was getting late and my head already cloudy I could not help observing that the process of dinking classes was horribly chaotic and inefficient.
Due to my intoxication I couldn't solve this issue at that time but the next day I sat down and could not only solve but prove the solution of the following nice little problem:

You have a group of n people sitting around a circular table. Every person can only say cheers to one other person at a time. In a "round of dinking glasses" any number of pairs of people may simultaneously dink their classes as long as they don't cross over other pairs' arms (in Germany that would be bad mannered).
What is the smallest amount of "rounds of dinking glasses" you need so that every person said cheers to every other person under this conditions?
If you are not able to prove your solution please explain at least your system.

Bonus question: What changes if you are allowed to cross arms?
Bonus bonus question: What changes if one person may dink glasses with k other persons simultaneously (I am pretty sure I have the correct solution for that as well but didn't formally prove it as of now, so go ahead please )?
[EDIT]: Clarification: One group of k persons may say cheers to each other at a time and none of them has to say cheers to any other of that k persons again.

I hope you enjoy it.

[Jockel]

I can't imagine how i would get this bored to ask myself questions like that when i'm buzzed.

[mr_m0nks]

n /k = I don't care if I'm drinking

[Necronopticous]

Professor! I think I've got it!

[shiftace]

If n is odd:

For the first round, start with one pair of adjacent guys. Form the second pair from the neighbors of that pair, and continue forming pairs from the neighbors of those already paired, until just one guy is left out. This gives (n-1)/2 pairs, and if you use this configuration rotated n times you will get n(n-1)/2 pairs, which is the number needed. You can see that no pair is repeated by thinking about the distance between paired people, parallel lines on a regular polygon, or lots of other ways probably. n rounds is optimal because you can't form n(n-1)/2 pairs any faster than this.

If n is even:

You can do n/2 rotations as above, starting with an adjacent pair, to get (n/2)^2 of the pairs. You can get the rest by working similarly, but form the first pair using two guys who are sitting two places apart; this will leave the very first guy and the very last guy unpaired, and you can do n/2 rotations getting (n-2)/2 pairs per rotation for n(n-2)/4. That's n(n-1)/2 pairs in total, which might not be optimal. It sems like it shouldn't be optimal, what with 2 guys unused half the time, but I don't want to think much harder about this.

If arms can cross: Still takes n rounds when n is odd. Getting n-1 rounds when n is even is easy.

k at a time: Obviously ceil(log_k(n)) is a lower bound, but to solve this without arm-crossing sounds painful.

[SpooN]

Jockel, it kind of comes naturally if half the people you are drinking with are math people.

Necronopticous, no need to hold back then.

shiftace, you are correct (your approach is a bit complicated though) but there is a very easy way to show that this system is optimal, so to everyone else how would you prove that the total rounds is n too if n is even (you can use the very same approach to show that the system is optimal for uneven n)?

The solution to k at a time should be easier than you think but proving it could be nasty (I believe it isn't though).
[EDIT]: Perhaps my theory can help you finding a starting point: I presume that for 1<n<=k the solution is 1 (obviously) and for n>k it is n-k+2 holding true for the above example of k=2. Please note that this might be wrong.

[shiftace]

original problem, n is even, showing n is optimal:

This way should work, although "ugly." Consider:
(a) A pair sitting directly across, with (n-2)/2 people on each side.
(b) A pair sitting one-off from directly across, with n/2 people on one side and (n-4)/2 on the other.

And these facts, subject to no arm crossing:
(1) There are n/2 pairs of type (a).
(2) There are n pairs of type (b).
(3) A round contains 0-1 pairs of type (a).
(4) A round contains 0-2 pairs of thye (b).
(5) A round cannot contain a pair of type (a) and a pair of type (b).

Using all this, I can argue that n rounds is a lower bound. Since a solution that yields n has been found, it is optimal. It'd be fun to hear more clever arguments though.

k at a time:

I can't think of any nice approaches here. I'll just mention that if arm-crossing is ignored (and respecting arm-crossing here seems really strange), then I think (n,k) = (6,3) can be done in 4 rounds.

[SpooN]

Sadly it doesn't seem like anyone else pays attention to this so I think it doesn't matter if I "reveal" it:

If your left and right neighbour say cheers you have to suspend a round (obvious), thus since everyone has to say cheers to everyone every person has to suspend at least once => If you find a system where every person excactly suspends one time it must be optimal (if n is even or not).
[EDIT]: To be excact: people don't say cheers more than one time to each other.

I tried to do (6,3) in 4 rounds but couldn't do it (only once though, could you explain/draw how you do it?), of course without crossing otherwise it would be a pretty simple combinatoric problem I think.

[shiftace]

If you haven't checked for yourself yet, this should do it:

Code: Select all

Require:            ab ac ad ae af bc bd be bf cd ce cf de df ef
Round 1: abc def --       ad ae af    bd be bf cd ce cf
Round 2: ade bcf --             af    bd be    cd ce
Round 3: acf bde --                            cd ce
Round 4: abf cde --

I did think of the idea that "if your neighbors say cheers, you have to skip this round," but didn't recognize it as a useful or complete argument, damn.

[SpooN]

Perhaps I misunderstand your example (or we had a misunderstanding about the rules) but Round 2, 3 and 4 seem impossible: You can't connect b and f if a and c say cheers etc.

[Never_Scurred]

I should have known! Math enthusiast and simple explanation never go hand in hand.