7
$\begingroup$

If we take all the digits from 1 to 9 and lay them out in order.
123456789
Now repeat the sequence and add it to the end.
123456789123456789
Now let's copy and reverse everything to create a second sequence
987654321987654321

Now we merge both together and wrap them into a circle. So we have 18 digits running in order clockwise and 18 digits running in reverse anticlockwise.

circle of an 18 digit sequence running in both directions

The above image is an example of how the numbers could be arranged

Now if we examine the arrangement we can find a place where we can split the circle into orthogonally connected sections of 9 cells where no digit repeats.

circle split into 4 sections of non repeating digits

Question
Is there are way of arranging the gaps between the clockwise and anticlockwise sequences around the circle in such a way to make it impossible to divide the circle into 4 sections where each section contains all of the digits 1 to 9 without repeats?

Or can you prove that no matter how the 2 sequences interweave around the circle there will always be a place where you can split the circle into 4 groups without repeated digits?

Note
The star in the image is meaningless

$\endgroup$
0

1 Answer 1

4
$\begingroup$

It is

always possible to split.

Proof

Lets call numbers up and down depending on which sequence they came from before intermixing. In OP up numbers are red and down numbers green. Pick a pair of neighbouring up and down numbers.

1. If their values are equal (k, say) then the ccw one forms a full set with its 8 ccw neighbours (and the cw one with its 8 cw neighbours). Indeed, there will be some number j of up neighbours taking values k+1,k+2,...,k+j (mod 9) and 8-j down neighbours taking values k-1, k-2,...,k-8+j=k+j+1 (mod 9).

Further, the next 9 neighbours ccw form another full set by essentially the same argument (Split into up and down numbers and observe that they cover complementary (contiguous) subsets). And so on.

2. If their values are different, u and d, say, then again by essentially the same argument u and d together with their d-u-1 (mod 9) ccw neighbours (which take values u+1,u+2,...,d-1 (mod 9)) and their u-d-1 (mod 9) cw neighbours (which take values d+1,d+2,...,u-1 (mod 9)) form a full set. As above the next 9 ccw (or cw) also form a full set.

$\endgroup$
2
  • $\begingroup$ Does the split still work if the sequence runs 3 times clockwise and only once anticlockwise $\endgroup$
    – Maff
    Mar 27, 2023 at 10:23
  • $\begingroup$ @Maff not 100% sure but off the top of my head I can't see a reason the proof wouldn't go through unchanged. $\endgroup$
    – loopy walt
    Mar 27, 2023 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.