18
$\begingroup$

enter image description here

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

enter image description here

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?

$\endgroup$
  • 5
    $\begingroup$ This doesn't appear to really have anything to do with dimensions -- all of these kebabs are one-dimensional. $\endgroup$ – qaphla Aug 6 '14 at 21:43
  • $\begingroup$ @qaphla yes off-course physically all kebabs are in one spatial dimension. but here i just use the word dimension to indicate the no of pairs used. $\endgroup$ – Hubble07 Aug 6 '14 at 21:55
  • 9
    $\begingroup$ That was not clear...could you call it an 8th order, 16 element, or just 8veggie kebab? $\endgroup$ – kaine Aug 6 '14 at 23:51
  • $\begingroup$ I have 8 pairs and the task is to make the longest 8-d kebab. So is it limited to 16 elements or not? For example: would 1312132 be a valid 3-d kebab, too? $\endgroup$ – 355durch113 Aug 7 '14 at 1:38
18
$\begingroup$

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++;
    }
  }
}
$\endgroup$
  • $\begingroup$ @kaine, see code now in answer. I haven't thought of an approach better than testing all permutations of n items, to find an n-kabob with 2n elements $\endgroup$ – James Waldby - jwpat7 Aug 7 '14 at 4:41
  • $\begingroup$ Note, exitnow gets initialized in main, along with solcount (not shown in above code, but used for counting 8D sols, along with exitnow = n != 8 in place of exitnow = 0) $\endgroup$ – James Waldby - jwpat7 Aug 7 '14 at 4:52
  • $\begingroup$ @jwpat7 Brilliant, you have answered all questions correctly. BTW this problem is called Langford Pairing. en.wikipedia.org/wiki/Langford_pairing $\endgroup$ – Hubble07 Aug 7 '14 at 10:48
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Instead of writing $(\mod 4)$ to generate $(\mod 4)$, you could also write $\pmod 4$ to generate $\pmod 4$ which has a neater format. Here, p stands for parentheses :P $\endgroup$ – Feeds Sep 10 '18 at 9:15
  • 1
    $\begingroup$ @user477343 Done =D $\endgroup$ – justhalf Sep 10 '18 at 21:08
  • $\begingroup$ Looks better now! I wish I could upvote... again :P $\endgroup$ – Feeds Sep 10 '18 at 21:27
3
$\begingroup$

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]);}
        }
    }
}
$\endgroup$
  • $\begingroup$ Note the program found 300 solutions you can run it at Ideone.com $\endgroup$ – kaine Aug 7 '14 at 2:54
  • $\begingroup$ Nice work. Actually there is a quick technique for finding a valid sequence by hand. start with n/2 if n is even or otherwise (n-1)/2 and then just keep adding the next highest integer till you can. for eg with n=8 i will start with 4 and so i can go upto 8. So i have 4 5 6 7 8. Then just put some blanks which u can fill later easily. So you get 4 5 6 7 8 4 _ 5 _ 6 _ 7 _ 8 _ _ Now you can easily fill the blanks with the remaining pairs to get 4 5 6 7 8 4 1 5 1 6 3 7 2 8 3 2 $\endgroup$ – Hubble07 Aug 7 '14 at 11:14
1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Re your comment about whether 1312132 is a valid 3-kebab, the question starts by saying “You are given two of each...”, which suggests to me that 1312132 is invalid $\endgroup$ – James Waldby - jwpat7 Aug 7 '14 at 2:47
  • $\begingroup$ @jwpat7 I thought so and thus did not post the extended variations explicitly. I wasn't sure because of the phrase "make the longest kebab". $\endgroup$ – 355durch113 Aug 7 '14 at 2:51
  • 4
    $\begingroup$ Stack Exchange: where the phrase "There exists no such kebab." has valid meaning. $\endgroup$ – Aza Aug 7 '14 at 5:13

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.