2
$\begingroup$

Consider a sequence $1,-1,-1,-1,-1,-1,...,-1$. Start at the first element and move down the sequence according to the following rules:

  • 1) If you jump from a $-1$ to another $-1$, turn the latter into a $0$.
  • 2) If you would land on a $0$, skip it instead.
  • 3) If you would reach the end of the sequence, wrap around instead.

For example, the first jump for the above sequence would leave the sequence unchanged, but the next would create a $0$ giving me $1,-1,0,-1,...,-1$. Assume I keep jumping around until only two elements are left

Call a jump from $-1$ to $1$ "nice". Given an initial sequence length $n$, how many "nice" jumps will I make, and from where?

Can you solve this with the $1$ in an arbitrary position, not just at the beginning?

Another example: Suppose we start with $-1,1,-1,-1$.

The first jump is nice and doesn't change the sequence. The second jump doesn't change anything either. The third takes us from the $-1$ in position 3 to the $-1$ in position 4, so the sequence is now $-1,1,-1,0$. The next three jumps - the second of which is nice - don't change the sequence, but after that I jump from the last $-1$ back around to the first one, changing it to a $0$, and I end with $0,1,-1,0$. For this sequence, I ended up making two "nice" jumps, both from index 1.

Is there a faster way to calculate this besides simulating it directly?

$\endgroup$
  • 1
    $\begingroup$ Note : If you do not understand question, please see chat.stackexchange.com/rooms/82585/thesimplifires-chatroom .Go to the first message containing my name and read from there .You will understand question and may get some idea too.I am available there you may ping me . $\endgroup$ – user61264 Jul 13 at 5:21
  • $\begingroup$ Since this is work for school, which is designed to teach you the material by having you figure it out on your own, we here generally frown on people asking for answers to coursework problems outright. If you tell us what you have tried and what help (short of “just do my homework for me”) you’re looking for, it will be more likely to be answered appropriately. $\endgroup$ – Rubio Jul 13 at 6:26
  • $\begingroup$ @Rubio it is not homework problem .Also instructor will tell answer if we ask them.But yeah i can tell what i did .Also do you think i need to re write the question ? $\endgroup$ – user61264 Jul 13 at 6:29
  • $\begingroup$ The question should be self-contained - I glanced at the chat transcript you pointed at and it was far too long for me to want to wade through to better understand the question. If you can make it more clear and more completely self contained, that would definitely help. I’d suggest also providing the exact wording of the problem as a block quote, but only if it’s in English. $\endgroup$ – Rubio Jul 13 at 6:35
  • $\begingroup$ @Rubio Ok i try to elaborate more .Don't mind but did you understood the question now ?. Also i love answers given in partial hidden form Example : puzzling.stackexchange.com/questions/85930/ix-nay-on-the-ix-say $\endgroup$ – user61264 Jul 13 at 6:38
2
$\begingroup$

For the first question, there is an easy pattern that we can detect. First, all of the nice jumps will come from the n-1 position for an array of length n.

As for how many, I'll print the first few and then try to point out the pattern

2: 0

3: 0

4: 1
5: 0

6: 2
7: 1
8: 1
9: 0

10: 3
11: 2
12: 2
13: 1
14: 2
15: 1
16: 1
17: 0

2 and 3 are basically special cases. After that, however, notice that each grouping I've made has the following property: the second half of the grouping is identical to the entire grouping above. The first half of the grouping is exactly the same, but with every element increased by 1.

This suggests the following recursive definition:

def nice(n):
  if n < 3: return 0
  k = n-2 # each grouping starts 2 numbers above a power of 2
  below = int(2**floor(log2(k)) # the biggest power of 2 less than k
  mid = below+below/2 # this is where the sequence splits in half
  if k < mid:
     return 1+nice(below/2+(k%mid)+2)
  else:
     return nice(below/2+(k%mid)+2)

I've tested it, and this correctly counts the nice moves in log2(n) recursive calls. The recursive part basically finds out where the element is in the "half-list" (k%mid) and looks for that same element in the previous grouping. Then it adds 1 if the element is in the first half of its grouping, and 0 if it is in the second half.

We add the 2 back in to make up for the fact that we had to subtract 2 up front to make everything line up on the powers of 2.

$\endgroup$
  • $\begingroup$ I think a quicker way to say this is that the number for $n$ is equal to the number of zero bits in the binary representation of $n-2$ (not counting leading zeroes of course). $\endgroup$ – Jaap Scherphuis Jul 25 at 11:18
1
$\begingroup$

To formalize user61579's answer, a simple reinterpretation of the rules is that, defining a pass as a move from the $1$ all the way around the sequence, every pass, every second $-1$ becomes $0$

Then, it is trivial to show that the state of a length-n sequence after each pass corresponds to the first n columns of this infinite table:

1 -1 -1 -1 -1 -1 -1 -1 -1 ...
1 -1  0 -1  0 -1  0 -1  0 ...
1 -1  0  0  0 -1  0  0  0 ...
1 -1  0  0  0  0  0  0  0 ...
...

A nice jump occurs in a pass if and only if the rightmost -1 in that pass is also the rightmost -1 in the next pass (i.e. it doesn't get deleted), which should give the formula user62579 noticed. (The pattern about nice jump locations, however, does not hold true: a length-7 sequence has a nice jump from position 5, for example)

If the $1$ is not the first element of the initial sequence, the same process can be used, except you first jump to $1$ (possibly executing a nice jump along the way), rotate your sequence so that $1$ is on the first element, and then insert columns of $0$s into the table so it matches your rotated sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy