Fill rectangle cells 2 * 100 with a continuous sequence of numbers

Lemma If we fix the columns on which the numbers 1 and 200 are located, then

• There are exactly 2 possible solutions if the columns are different,
• There are exactly 2 possible solutions if this is the same column and it is the last,
• in other cases there is no solution.

The proof is obvious (i.e., I am too lazy to write it) .

Solution A total of 100 * 100 choices of columns for numbers 1 and 200, of which 98 are impossible.

Total - 2 * (100 * 100 - 98) = 19804 options.

Where am I wrong? :)

Let's try to solve the problem recursively.

Let F ( n ) be the number of solutions for a 2 × n board, G ( n ) the number of solutions for a 2 × n board, which begin in the lower left corner. (We assume that the rectangle is horizontal).

Without loss of generality, assume that the first point is located at the bottom (this reduces the number of options for F ( n ) by half).

Obviously, in each of the paths there must be a vertical segment. Consider the first one. Let it be on the k- th step. Our way is

k+1 1 2 3 ... k 

We have such options:

1) k ≠ 1, and the upper part goes in the same direction as the first segment:

  k+1 k+2 1 2 3 ... k-1 k 

It is impossible to get to the left part of k + 1, and this part is not empty. So this option is not possible.

2) k ≠ 1, and the upper part goes in the opposite direction from the first segment.

  k+2 k+1 1 2 3 ... k-1 k 

while our path can not get to the right side, that is, it must be empty. That is, the path looks like this:

 2k 2k-1 2k-2 ... k+2 k+1| 1 2 3 ... k-1 k | 

The rest of the board has dimensions of 2 × ( n - k ), and it can be circumvented in G ( n - k ) ways.

3) k = 1

 2 3 1 

while our path can not get to the left side, it means that it should be empty, that is, we have this picture:

 |2 3 |1 

The number of bypass options is G ( n - 1).

Let's make recurrence relations.

For an arbitrary starting point: The number of options in 1) is 0. The number of options in 2) is equal to the sum of all possible k (from 2 to n ) values ​​of G ( n - k ), i.e., G ( n - 2) + G ( n - 3) + ... + G ( n - n ) = G (0) + G (1) + ... + G ( n - 2). This sum must also be multiplied by 2, for two possible directions (left and right), and another 2 for two possible lines for the starting point. The number of options for 3) is equal to G ( n - 1), and this should be multiplied by 2 for two possible lines for the starting point, and another 2 for the position of the unit on the left and right. Total:

G ( n ) = 4 × [G (0) + G (1) + ... + G ( n - 1)]

Now we make a recurrence relation for G ( n ). Consider the same three options (remember that 1 is in the lower left corner).

Option 1) is not possible for the same reasons.

Option 2) essentially means such a picture

 |2k 2k-1 2k-2 ... k+2 k+1| | 1 2 3 ... k-1 k | 

that is, k = n , this gives exactly one option for n > 1 and not a single option for n = 1.

Option 3) remains unchanged and gives G ( n - 1) option.

Total:

G (0) = 1
G (1) = 1
G ( n ) = 1 + G ( n - 1) for n > 1

It easily follows from this that G ( n ) = n for n > 0.

Finally, we obtain: F (100) = 4 × ([1 + 1 + 2 + 3 + ... + 99]) = 4 + 4 × 99 × 100/2 = 19804.

I hope that I was not mistaken anywhere.

Lemma 1 . A fragment of the path can be only two types: a snake or a loop . Snake is a continuous chain of vertical U- shaped fragments, where their vertical directivity alternates. A loop is a horizontal U- shaped fragment, where the legs can be of any (and different) length.

Lemma 2 . A loop at least on one side comes to the edge.

Lemma 3 . Loops can be 0, 1 or 2.

Lemma 4 . Snakes can be 0 or 1. The presence of a Snake breaks the ends of the Path (0 and 200). In the absence of a snake, the ends are side by side.

The minimum horizontal loop length is 1 transition (2 values):

 1 2 4 3 

The minimum length of the Snake horizontal consider two transitions (3 value in the mountains:

 1 2 3 4 

Consider the options:

 Петли Змейка Варианты 0 0 0 – нет такого варианта 0 1 4 - из каждого из углов стартует змейка по вертикали 1 0 200 * 2 - все варианты одной петли 1 1 4 * ? - про этот случай дальше. 2 1 4 * ? - про этот случай дальше: 

Loop and snake. The minimum length of such a piece is 4. 96 left for distribution. How many ways can you make 96 of the two natural terms, counting zeros? 0+96, 1+95 .. 95+1, 96+0 = 97 options. Do not forget to multiply by 2 (the order of the snake and loop), and by 4, because symmetry. +776

In the case when there are 2 loops and a snake, the minimum length of such a construction is 5: ПZП . There are 95 positions left for distribution among the three elements. The task is reduced to the number of compositions 95 out of three terms, counting zeros, and taking into account the order. The formula for the number of compositions of the number n of k terms, including zeros:

 ( n + k - 1 ) скобки высотой две строки ( k - 1 ) 

Let the upper part N = n + k - 1 , and the lower M = k - 1 . Calculated as

  N! ----------- K! * (NK)! 

For 95 and 3 I got 4656 and multiplied by 4. +18624

 Петли Змейка Варианты 0 0 0 0 1 4 1 0 400 1 1 776 2 1 18624 -------------------- 19804 

Result: 19804 . And now lay out a simple, as binary numbers, a trivial solution, which probably is. )

Upd . looking at two independent other results @ pavel-mayorov and @vladd, corrected the error in himself - did not take into account first the order of the snake loop in the 1: 1 variant.

Something like this (did not check):

1. Place the unit in the upper left cell.
2. Record numbers are either a snake or a snake beginning, and then in a straight line to the end and back in the second row. I think this can be a formula.
3. For reasons of symmetry, multiply the answer to 4.
4. To multiply by 2 and subtract 4 is what began with a snake, and ended with a non-degenerate ring, if you go along it in the opposite direction.
5. Add 2 * 196 as rings in two directions with any cell except the corner.

This answer is incorrect, did not take into account options for such a plan:

 2 1 6 7 8 3 4 5 10 9 

Thank you @PavelMayorov for finding this case.

6. Add 2 * 96 designs of the above view.