The 8-dimensional vegetable kebab

Question

You are given two of each from the array of 8 vegetables numbered 1 to 8 as shown above. So in total you have 16 veggies(8 pairs). Your task is to make the longest kebab (sequence of vegetables arranged linearly) such that the number of vegetable between any pair of vegetables should match exactly to the number written on the pair itself.

For example a 3-dimensional (using 3 different veggies) kebab would be

So in the 3-d case, between the two red capsicums (n=1) there is exactly one vegetable (eggplant) as required and similar case holds for n=2 and n=3.

Another example: For 4-d a valid sequence would be
41312432

In addition to finding the longest kebab (8-d sequence) you can also try some related questions shown below.

1) Find one possible 8-d kebab.(main question)

2) How many 8-d kebabs are possible?

3) Are there any dimensions in which it is impossible to make a kebab?If yes then whats the general formula for figuring out the allowed dimensions?

Answer 1

1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8

is probably the lexicographically-least 8D answer.

Here are some solutions for various dimensions:

3: 2 3 1 2 1 3
4: 2 3 4 2 1 3 1 4
7: 1 4 1 5 6 7 4 2 3 5 2 6 3 7
8: 1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8
11: 1 2 1 4 2 8 9 10 4 11 6 3 7 5 8 3 9 6 10 5 7 11
12: 1 2 1 3 2 8 9 3 10 11 12 5 7 4 8 6 9 5 4 10 7 11 6 12
15: 1 2 1 3 2 4 10 3 11 12 4 9 14 15 13 7 8 10 5 6 11 9 12 7 5 8 6 14 13 15
16: 1 2 1 3 2 4 8 3 12 13 4 10 14 15 16 8 9 6 11 5 7 12 10 13 6 5 9 14 7 15 11 16
19: 1 2 1 3 2 4 5 3 9 15 4 14 5 13 16 17 18 19 9 10 7 12 6 8 11 15 14 13 7 6 10 16 8 17 12 18 11 19
20: 1 2 1 3 2 4 5 3 6 16 4 15 5 14 17 6 12 19 20 18 9 11 13 7 10 8 16 15 14 12 9 7 17 11 8 10 13 19 18 20

There appear to be 300 8D solutions. The reverse of a solution also is a solution. I found no solutions for n in the set {1, 2, 5, 6, 9, 10, 13, 14} and found solutions for n in {3, 4, 7, 8, 11, 12, 15, 16, 19, 20}, suggesting there are solutions only for n of the form 4k and 4k-1. (I didn't test at n=17 or 18 or n>20 as the program might take weeks to get done. First-solutions at n=19 and 20 took 20 minutes and 57 minutes to find.)

In a solution, let us write the occurrences of fruit i as i and i'. Fruits i and i' are not distinguishable, so we can arrange that i always appears before i'. Thus we can exhaust all possible orders of 2n items by generating and testing all permutations of n items, accepting those permutations such that an array of 2n cells can be filled in via the following C code, with elements i and i' at distance i+1. For a given n-permutation, there is one way or no way to fill in the array of 2n cells.

void testPerm(int n) { // See if n-perm makes valid n-kabob
  int minplace, i, j;
  memset(dat, 0, sizeof(dat));
  minplace = 1;
  for (i=1; i<=n; ++i) {
    j = pi[i];
    while (dat[minplace])
      ++minplace;       // Get to next available spot in dat
    dat[minplace] = j;
    if (minplace+j+1 > 2*n) return; // Fail if out of bounds
    if (dat[minplace+j+1]) return;  // Fail if already in use
    dat[minplace+j+1] = j;
  }
  exitnow = 1;
  showKebab(n);
}

Note, the above routine uses some globally-declared variables, as below. The current permutation is held in pi[1]...pi[n], and dat is used in trying to generate an n-kabob from the n-permutation, or when printing a solution. Var exitnow tells the caller whether to exit (eg, if a solution is found).

#define NMAX 21
int pi[NMAX+1], dat[2*NMAX+2];
int exitnow;

The routine that calls testPerm is like the following, which implements a permutation algorithm of Dijkstra's.

void permuter(int n) {
  int i, j, r, s, temp;
  for (i=0; i <= n; i++) pi[i] = i; // Init to first perm, 1, 2...n
  i = 1;
  while (i && !exitnow) {
    testPerm(n);
    // Generate next permutation
    i = n-1;
    while (pi[i] > pi[i+1]) i--;
    j = n;
    while (pi[i] > pi[j]) j--;
    temp = pi[i]; pi[i] = pi[j]; pi[j] = temp;
    r = n; s = i+1;
    while (r > s) {
      temp = pi[r]; pi[r] = pi[s]; pi[s] = temp;
      r--; s++;
    }
  }
}

Answer 2

So far the answers have been dealing with brute force. Here I present the mathematical proof that such kebab only exists iff $n\equiv -1,0 \pmod 4$.

Prove that no kebab could exist if $n\equiv 1,2 \pmod 4$.

Let $x_1, x_2, \ldots, x_n$ be the positions of the left-most vegetable, for each vegetable numbered $1, 2,\ldots, n$, respectively. Then the positions for the other vegetables are: $x_1+2, x_2+3, \ldots, x_n+n+1$. Note that these $2n$ positions should all be distinct and in the range of $[1,2n]$.

Note that for all $i$, if $i$ is odd, $x_i$ and $x_i+i+1$ will have the same parity, and if $i$ is even, they will have different parity.

Now, suppose $n=4k+1\equiv 1 \pmod 4$

There are $2k+1$ vegetables with odd index, and $2k$ vegetables with even index.

There are in total $8k+2$ positions to be filled, with $4k+1$ even-indexed positions and $4k+1$ odd-indexed positions.

Since the vegetables with even index will use one even-indexed position and one odd-indexed position, there will be $4k+1-2k=2k+1$ even-indexed positions and $2k+1$ odd-indexed positions left for the vegetables with odd index. But each pair of vegetable with odd index will use two position with the same parity. Since $2k+1$ is odd, we won't be able to place all the odd index vegetables.

For the case $n=4k+2\equiv 2(\mod 4)$, it's quite analogous to previous case, again resulting in $2k+1$ odd-indexed positions for the remaining $2k+1$ odd index vegetables, each requiring two positions with the same parity.

So it's impossible to have a kebab when $n\equiv 1,2\pmod 4$

Prove that there is a kebab for $n\equiv -1,0\pmod 4$

I intended to give a constructive proof here, but it seems difficult.

Answer 3

I wrote some code for this and brute forced it. I would greatly prefer a non-brute force solution or at very least more elegant code.

4 example solutions it found included but there are many:

- 4567348536271218 - 5673485364712182 - 6734583647512182 - 7345638475261218

The code was:

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] desc = {1,2,3,4,5,6,7,8};
        int[] sep = {1,1,1,1,1,1,1,0};
        int c=0;

        while (c<8*7*6*5*4*3*2){
            c++;
            boolean unique=false;
            while(!unique){
                int k=7;
                while(k>0&&sep[k]==7){sep[k]=1;k--;}
                sep[k]++;
                desc[0]=sep[0];
                for(int j=1;j<8;j++){desc[j]=(desc[j-1]+sep[j]-1)%8+1;}
                unique=true;
                for(int j=1;j<8;j++){
                    for(int x=0;x<j;x++){
                        if(desc[x]==desc[j]){unique=false;}
                    }
                }
            }

            int[] list = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
            int i=0;
            int j=0;
            while(j<8){
                while(list[i]>0){i++;}
                list[i]=desc[j];
                if(i+desc[j]+1>15||list[i+desc[j]+1]>0){
                    break;
                } else {
                    list[i+desc[j]+1]=desc[j];
                }
                j++;
            }
            boolean tester=true;
            for(int z=0; z<15; z++){if(list[z]<1||list[z]>8){tester=false;}}            
            if(j>7 && tester){
            for(int z=0; z<15; z++){System.out.print(list[z]);}
            System.out.println(list[15]);}
        }
    }
}

Answer 4

8 6 4 2 5 7 2 4 6 8 5 3 1 7 1 3

8 6 4 2 7 5 2 4 6 8 3 5 7 1 3 1

should work. I started boxing the even numbers and then shuffled in the remaining odd numbers. If what I posted in the comment above is ok, then one could add 5 or 1.

For the first two "dimensions", there's obviously no such kebab. Thinking about $d>8$.

(Again, if my comment holds, kebabs for d=5, d=9 and d=10 are quite easily found.)