Wikipedia:Reference desk/Archives/Mathematics/2021 November 28
Mathematics desk | ||
---|---|---|
< November 27 | << Oct | November | Dec >> | November 29 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
November 28
editSeating rearrangement
editI came across a statement that if an even number of people are seated round a circular table, then no changes of their positions can give every pair a different number of places between them than the initial value. I was not able to prove this. Looking at an odd number of people, I found it possible for five and seven but for no others I tried. Is there an easy way to show for which numbers the property is possible or not?→ 2A00:23C6:AA07:4C00:F4DA:6147:E989:5D9F (talk) 14:23, 28 November 2021 (UTC)
- What about the rearrangement from (1 2 3 4 5 6 7 8 9 10) to (1 3 8 6 4 2 10 5 7 9)? I don't see a pair that is reseated at the same distance. --Lambiam 17:51, 28 November 2021 (UTC)
- @Lambiam: see 4 and 9, which have four people between them in each arrangement. eviolite (talk) 17:54, 28 November 2021 (UTC)
- OK, thanks. --Lambiam 21:33, 28 November 2021 (UTC)
- @Lambiam: see 4 and 9, which have four people between them in each arrangement. eviolite (talk) 17:54, 28 November 2021 (UTC)
- Consider, for odd n, the rearrangement from (1 2 3 ··· n ) to (1 3 5 ··· n 2 4 6 ··· n−1). It appears that this rearrangement avoids same-distance reseating if and only if all prime factors of n are at least 5. So this works for n = 275 = 5×5×11. I conjecture that no rearrangement works for n not of this form. --Lambiam 23:37, 29 November 2021 (UTC)
- That pattern and its reversal are the only solutions for n = 5, and two of the four solutions for n = 7. If it is possible to show that this condition (all prime factors at least 5) is necessary and sufficient for there to be a solution, that would cover the case of n even. Maybe there is a more direct way of showing infeasibility in that case?→2A00:23C6:AA07:4C00:7933:461E:C152:F071 (talk) 12:49, 30 November 2021 (UTC)
- Perhaps, but at least in my experience it is not unusual that the easier road to a proof of some statement is to seek a proof of some more general statement of which it is an instance. It may be easier to understand why 2 and 3 are both buzzkills. I expect that proving sufficiency may be somewhat laborious by requiring case analysis but otherwise straightforward. --Lambiam 15:41, 30 November 2021 (UTC)
- I can't put my finger on it, but it seems like this is a variant of a sort of cyclical Derangement problem; insofar as the "fixed points" in the rearrangement of seats is the gaps between the numbers; I feel like I've seen something like this before (perhaps as a Numberphile video), but it is escaping me currently. --Jayron32 16:19, 30 November 2021 (UTC)
- Perhaps, but at least in my experience it is not unusual that the easier road to a proof of some statement is to seek a proof of some more general statement of which it is an instance. It may be easier to understand why 2 and 3 are both buzzkills. I expect that proving sufficiency may be somewhat laborious by requiring case analysis but otherwise straightforward. --Lambiam 15:41, 30 November 2021 (UTC)
- That pattern and its reversal are the only solutions for n = 5, and two of the four solutions for n = 7. If it is possible to show that this condition (all prime factors at least 5) is necessary and sufficient for there to be a solution, that would cover the case of n even. Maybe there is a more direct way of showing infeasibility in that case?→2A00:23C6:AA07:4C00:7933:461E:C152:F071 (talk) 12:49, 30 November 2021 (UTC)