Conserving contiguity with a transposed progression

  • Context: Graduate 
  • Thread starter Thread starter Loren Booda
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the possibility of rearranging a sequence of integers from 1 to N such that no two adjacent integers in the new arrangement retain their original adjacency. The scope includes theoretical exploration and mathematical reasoning regarding the conditions under which such rearrangements can or cannot occur.

Discussion Character

  • Exploratory, Mathematical reasoning, Debate/contested

Main Points Raised

  • One participant questions whether a sequence can be rearranged without retaining original adjacency.
  • Another participant suggests a specific rearrangement for a small value of N, proposing the sequence 1,3,5,2,4,6.
  • A participant inquires if the proposed rearrangement holds for any N.
  • It is noted that for N <= 3, it is impossible to achieve the desired rearrangement.
  • For N >= 5, a participant claims that listing the odd numbers followed by the even numbers suffices for the rearrangement.
  • The case of N=4 is discussed in detail, with a participant providing reasoning that shows it is not possible to rearrange the sequence without retaining adjacency when considering endpoints as neighbors.
  • Specific challenges are raised regarding starting points for the sequence and their implications on adjacency, indicating that wrap-around conditions complicate the arrangement for N=4.

Areas of Agreement / Disagreement

Participants generally agree that for N <= 3 and N=4, it is not possible to rearrange the sequence as required. However, for N >= 5, there is a proposal that it can be done, indicating a lack of consensus on the broader applicability of the rearrangement method.

Contextual Notes

The discussion highlights limitations in the reasoning for specific values of N and the implications of considering endpoints as neighbors, which remain unresolved.

Loren Booda
Messages
3,115
Reaction score
4
Can a sequence of integers from 1 to N be rearranged so that no two neighbors retain their original adjacency?
 
Physics news on Phys.org
I suppose running it backwards (6,5,4,3,2,1) is not enough for what you meant.

Then, how about 1,3,5,2,4,6.
 
And for any N?
 
Well, for N <= 3 you obviously can't, so the trivial response is "no".

For N >= 5 you only need to list the odds, then the evens.

The interesting case is N=4. If you don't count the endpoints, 2,4,1,3 suffices. If you count them as neighbors, then
- Sequences starting with "1" won't have a place for "2": second and fourth are neighbors to "1", and third place would make it neighbor to wherever you place "3".
- Similar for sequences starting with "4": there's no place for "3" (third place leaves no place for "2").
- Similar when starting with "2", where there is no place for "3" (second and fourth are neighbors to "2", third would leave no place for "4").
- And same for starting with "3", where similarly there is no place for "2" (third place leaves no place for "1").
So with wrap-around, N=4 is a no-no.
 
Last edited:

Similar threads

Equivalence between Bravais lattice definitions
  • · Replies 0 ·
Replies
0
Views
1K
High School Determinant of a transposed matrix
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Understanding permutations and combinations in a coin toss experiment
  • · Replies 6 ·
Replies
6
Views
2K
Bishops and permutations on chessboard
  • · Replies 23 ·
Replies
23
Views
4K
Graduate How Does U(1) Double-Cover SO(2) for a Specified Angle?
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction
  • · Replies 8 ·
Replies
8
Views
5K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
2K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
Graduate Pseudorandom integer sequence having at least 15 adjacent differences > 36
  • · Replies 1 ·
Replies
1
Views
3K