Re: Minimum steps

Kevin Stone <newsaccount@xxxxxxxxxx> wrote:
> An interesting question I've been asked:
> Determine the minimum number of moves needed to cross N steps.
> The first move starts with one step and every subsequent step can be one
> more or less than its previous move. You have to land on the final step
> exactly.

I'm assuming (as are others in this thread) that a move of 0 is not
allowed.

Firstly: the parity of any number reachable in k moves is equal to
that of the kth triangular number (because any sequence of k moves
involves summing k numbers which alternate in parity, and therefore
the parity of the result is fixed). Thus odd numbers can only be
reached by sequences of lengths 1,2,5,6,9,10,13,14,17,18,...,
whereas 3,4,7,8,11,12,15,16,... are the only lengths that can get to
even numbers.

Next obvious point: the largest number reachable in k moves _is_ the
kth triangular number (because that's what you get if you take the
longest step you can at every stage).

Thirdly: 2 and 5 are completely unreachable. The former would
require a move of 1 after the initial 1, which is disallowed, and
the latter would require a disallowed move of 2 (or 1,1 which is
just as bad) after the first two forced moves 1,2.

Big theorem: within a given parity, minimum move counts increase
monotonically. Therefore, the minimum move count for any number n
(apart from the two unreachable ones given above) is equal to the
smallest k such that the kth triangular number has the same parity
as n and is >= n.

Proof:

Given any target number n, start by finding k as specified above.
Now write down the move sequence 1,2,...,k, which reaches the kth
triangular number in k moves.

We can now repeatedly reduce this move sequence, step by step, in
such a way that its target reduces by 2 every time. We do this by
one of two possible strategies:

(a) if the last move in the sequence is one _more_ than the one
before it, we can just reduce that last move by two.

(b) alternatively, look for a move which is one more than both the
moves surrounding it, and then we can reduce _that_ one by two.

The only situation in which we cannot do either of (a) or (b) is
when all moves are either 1 or 2, meaning we can't reduce anything
by two at all. So the k-move sequence with the smallest total is an
alternation of k 1s and 2s, which comes to 3k/2 (if k is even) or
3(k-1)/2+1 = (3k-1)/2 if k is odd.

It remains only to demonstrate that this number is less than or
equal to the next triangular number down for all k (meaning that
k-move sequences can always get down as low as the next lower
possible move count). The worst case for this is when the next valid
k is three lower than this one, so that the target triangular number
is (k-3)(k-2)/2 = (k^2-5k+6)/2. So we want to show that this exceeds
(3k-1)/2, and hence we subtract the latter from the former to get
(k^2-8k+7)/2. This is clearly greater than zero for any k > 8, so we
need only examine a small number of low-end cases to complete the
proof. Actually doing this is trivial but tedious so I leave it as a
reader exercise :-) Case analysis will show again that 2 and 5 are
unreachable but that everything else follows this theorem. []

If zero moves _are_ allowed, most of this analysis remains
unchanged. The last bit is much easier because the smallest number
reachable in k steps is now done using an alternation of 1s and 0s
and hence is somewhere in the region of k/2, thus _even more_ easily
shown to be less than the next lower triangular number of the right
parity. Hence allowing zero moves renders 2 and 5 reachable (1,0,1
and 1,2,1,0,1 respectively), and does not change the minimum number
of steps required for any other number at all.
--
Simon Tatham "The difference between theory and practice is
<anakin@xxxxxxxxx> that, in theory, there is no difference."
.

Relevant Pages

  • Re: Mathematical function for Smiling Jack the Anarch
    ... that's the sum of integers from 1 to x.  The sequence is also ... referred to as triangular numbers, because they count the number of ... It's a very useful sequence and function to know. ... There's a story where Carl Friedrich Guass (a famous mathematician in ...
    (rec.games.trading-cards.jyhad)
  • Re: CRC32 : theory and pratice.
    ... This means that if just one bit of the unique sequence changes, the CRC32 is not valid anymore. ... Sometimes CRC is implemented with a "Long Check" which enforces even parity on each bit. ... Then, if a "channel" is bad you know which one, and along with CRC can have even limited error correction. ... Usually though bad blocks are just re-transmitted or re-read in tape drives and communications that implement this three-way check. ...
    (borland.public.delphi.non-technical)
  • Re: any one recognize this sequence?
    ... Looks like every term of the sequence is 2^T times an odd number, ... a triangular number. ... if we reverse the order of the terms in each ...
    (sci.math)
  • Re: Discrete with fast method...
    ... I can make a sequence with ... we may start with one way fillings, ... Points have a given parity: ... And accordingly belong to A or to B ... ...
    (sci.math)