12
$\begingroup$

Once, a number of couples, each one of them happening to be composed of a mathematician and an athlete (hence 'mathletic'), wanted, in order to diversify communication, to sit down at opposite sides of a (rectangular) dinner table randomly, in such a way that mathematicians face athletes. A certain athlete proposed: let's simply not allow any couple members to face one another, this increases average distance between couple members by 0.35 chairs, and such will diversify communication even more.

How many couples were there?

Assume no mathematician is also an athlete, and vice versa, or, at least, any couple member is always strictly more mathematician than athlete, or, strictly more athlete than mathematician (so one member can be labeled 'm' and the other one 'a', or vice versa).

The proposal got accepted unanimously. :-)

'distance' between 'couple members' is measured in number of chairs away to the left or to the right. Below some examples of distance 2 between couple members 'm' and 'a' of couple '(m,a)' from 'm' point of view:

2|1|0|1|a    1|0|1|2|3
  table   or   table   or ...
2|1|m|1|2    1|m|1|a|3

This question, which I once came up with, was recently originally posted on 'mathematics' website, but, I was kindly suggested to rather post it here on the 'puzzle' website.

$\endgroup$
3
  • $\begingroup$ I'm confused by the meaning of "average distance between couple members". Is the 0.35 increase an increase on the average distance between two particular sittings? Or the increase on the expected average distance when sitting fully randomly and the expected average distance when sitting randomly with the new constraint? $\endgroup$
    – Stef
    Oct 19, 2021 at 11:48
  • 1
    $\begingroup$ @Stef : It is rather your second description if I read you correctly. Every couple (m,a) has a distance defined in terms of numbers of chairs. The average (over all possible ways of sitting) of such distance increases when respecting new constraint. $\endgroup$ Oct 19, 2021 at 11:57
  • $\begingroup$ One may wonder why I chose 0.35 chairs, well: it's the first distance value that's short to decimal write down exactly given a not too small amount of couples :-) $\endgroup$ Nov 3, 2021 at 23:01

2 Answers 2

12
$\begingroup$

There are

20 couples.

If you seat $n$ such couples randomly, then

the average distance between a pair is just the average of all possible absolute differences $|i-j|$ with $1\leq i,j\leq n$. That's $\bigl\{[0|n|+1|n-1|+2|n-2|)+\cdots+(n-1)|1|] + n|0| + [(n-1)|-1|+\cdots+1|-(n-1)|+0|-n|]\bigr\} / n^2$

where

each product is |signed distance| $\times$ number of pairs. The numerator is $(n^3-n)/3$ (one can express it in terms of well-known sums, or just note that it's obviously a cubic polynomial, compute the first few values, and use finite differences). So the average distance is $(n^2-1)/3n$.

If we forbid couples to sit opposite one another,

the only thing that changes is that the $n|0|$ term disappears and the denominator reduces from $n^2$ to $n^2-n$. (Because we have ruled out the $n$ cases where $i=j$.) So now the average distance is $(n+1)/3$.

The increase in average distance is

$[n(n+1)-(n^2-1)]/3n=(n+1)/3n$.

So,

if this is exactly 0.35 then $(n+1)/n=1.05$, so $1/n=0.05$, so $n=20$.

$\endgroup$
2
  • $\begingroup$ you nailed it down! fwiw: I don't think you ever heard about this puzzle, did you? because then it may have been invented two times :-) $\endgroup$ Oct 18, 2021 at 16:19
  • 2
    $\begingroup$ I don't remember seeing this puzzle or any equivalent before, no. $\endgroup$
    – Gareth McCaughan
    Oct 18, 2021 at 18:20
3
$\begingroup$

This isn't an official answer to the question, but rather its intent is to compliment @Gareth McCaughan's existing answer.


Let $ap$ represent the average permutation distance, and let $ad$ represent the average derangement distance:

$$ap(n)=\frac{(n-1)(n+1)}{3n}$$ $$ad(n)=\frac{(n+1)}{3}=\frac{n(n+1)}{3n}$$
As a result:
$$ad(n)-ap(n)=\frac{(n+1)}{3n}$$
remains to find solution for
$$\frac{(n+1)}{3n}=0.35$$
Perhaps one could call a 'permutation', which is not a 'derangement', an 'arrangement' :-)

One way to reason and calculate is to average the pair member distances $$|m-a|$$ over all possibilities. Note that average behaves linear and also for any difference d and any couple (m,a) there are always same amount of permutations having $$m-a=d$$ Consider the nxn matrix of (m,a) positions:

$\begin{bmatrix}(1,n) & ... & (n,n)\\: & (m,a) & :\\(1,1) & ... &(n,1)\end{bmatrix}$

The total sum of all distances $$|m-a|$$ in

$\begin{bmatrix}|1-n| & ... & |n-n|\\: & |m-a| & :\\|1-1| & ... & |n-1|\end{bmatrix}$

equals: $$\frac{(n-1)n(n+1)}{3}$$ (this can be proved by induction and is a somewhat standard formula).

The total amount of pairs in the matrix is: $$n^2$$ (these correspond to permutations).

The total amount of pairs in the matrix for which $$m<>a$$ is: $$n^2-n=n(n-1)$$ (these correspond to derangements).

so $$ap(n)=\frac{(n-1)n(n+1)}{3n^2}=\frac{(n-1)(n+1)}{3n}$$ and $$ad(n)=\frac{n(n+1)}{3n}=\frac{n+1}{3}$$

$\endgroup$
0

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.