Problem 49803. Compute expulsions from the Kimberling shuffle

ChrisR

14 solvers

1 likes

Solve

Solve Later

The Kimberling shuffle uses a semi-infinite array of numbers in which the first row is simply the numbers 1, 2, 3, 4, 5,… Subsequent rows are generated by shuffling the previous row: the first number is the number to the right of the main diagonal of the previous row, the second is the number to the left of the main diagonal, the third is the number two slots to the right of the main diagonal, etc. When numbers run out on the left of the main diagonal, the rest of the numbers are the remaining numbers of the previous row--except for the number on the main diagonal of the previous row, which is expelled. The first few rows of the array are 
 2   3   4   5   6   7   8   9  10...
 3   4   5   6   7   8   9  10  11...
 2   5   6   7   8   9  10  11  12...
 2   7   4   8   9  10  11  12  13...
 7   9   2  10   6  11  12  13  14....
Write a function to determine the row after which the input number is expelled. For example, because 5 appears on the main diagonal of row 3, your function should return 3. An optional challenge is to determine whether all numbers are eventually expelled from the array.