Ambitious Arrangements

Given the fact that no integer must be placed in between two larger integer, there are two cases for the location of the 2 1s:

Case1: The ends must be occupied by the 1s. In this case, there will be five remaining spaces. The spaces will be populated by the smaller numbers first. Each remaining number, with the exception of the number 6, will have 2 options which space it will occupy. Four numbers gets to have the choices, thus this case would yield: 2 2 2*2=16 possible arrangements.

Case 2: The 1s must be placed side by side. From here onward, we can consider 1 to be single number, say X. Thus we only need to arrange six numbers. Note also that X does not need to follow the rule about values of adjacent numbers since whatever number is placed adjacent to it, the rule will not be violated since X represents 2 1s. This case can be further divided into 3 subcases: Subcase 1: X is located on the 1st or 6th place. Following the logic employed in Case 1, when X is located on either the 1st or 6th position, there will be 16 ways to arrange the remaining 5 numbers. Thus, for this subcase, there are 2*16=32 possible arrangements.

Subcase 2: X is located on 2nd or 5th position. In this case, 1 number (except from X) will be isolated from others. We have 5 possible choices for this. Next, we proceed as we did in the previous cases. We need to place the remaining 4 numbers. We have 2 2 2=8 ways to do this. We can then say that there are 2 5 8=80 possible arrangements for this subcase.

Subcase 3: X is located on 3rd or 4th position. Here, the five higher numbers will be divided into groups of 2 and 3 numbers respectively. There would be 5C2 ways of selecting the group with 2 numbers. Note also that the positioning of this two numbers will never violate the rule for adjacent numbers. Thus, we have (5C2) (2)=10 2=20 ways of arranging numbers in this subcase so far. Now, we also have to arrange the remaining three numbers, and we have 2 2=4 ways of doing so. All in all, we have 2 20*4=160 possible arrangements for this subcase.

Adding all the possible arrangements for each subcase, we have 16+32+80+160=288 possible arrangements.

The problem asks us to count how many arrangments of the 7 almost unique integers there are such that no integer is immediately adjacent to two stricly larger integers. The fact that the integers are almost all unique, except for the two '1's, will assist us in solving this puzzle.

Consider the simplified problem of counting how many satisfiying sequences there are for N unique integers. We can count this simply by realizing the smallest integer must appear on the left or right of the sequence and that the remainer of the sequence corresponds to an arrangement of N - 1 unique integers. Therefore there are twice as many such arrangements of length N as there are for length N - 1 (for N > 1). Therefore there are $2^{N - 1}$ satisfiying arrangments of N unique integers for $N \ge 1$ .

Back to the original problem we now have to consider what happens with the pair of '1's. There are two cases: either the '1's are placed on the ends of the arrangement (i.e. 1 2 4 6 5 3 1) or the '1's are placed consecuritvely (i.e. 3,1,1,2,4,5,6).

The first case is simple to count. There are $2^4$ ways to arrange the middle 5 elements and we have forced the '1's to appear on the ends.

The second case is trickier. If the '1's appear on an end of the arrangment there are again $2^4$ ways to arrange the remaining 5 elements. When we split the elements up into two non-empty groups with M elements left of the '1's then there are ${5 \choose M} 2^{M-1} 2^{5-M-1} = 8 {5 \choose M}$ .

Therefore the total number of arrangements is $16 + 16 * 2 + 8 \displaystyle \sum_{M=1}^{4} {5 \choose M} = 288$ .

Let f(n) be the number of ways of arranging n distinct numbers with this property. This is a much simpler problem, as the lowest number must appear at either end, so it is easy to see that f(n) = 2 f(n-1) for n > 1, and that f(1) = 1, so f(n) = 2^{n-1} for positive n.

Back to the original problem: if the 1's are not adjacent then they must occur at the ends (else they are adjacent to two larger numbers). Thus all arrangements must fit one of the 7 templates: 1xxxxx1, 11xxxxx, x11xxxx, xx11xxx, xxx11xx, xxxx11x, xxxxx11.

Now a given completion of a template satisfies the adjacency condition iff each of the contiguous xxx strings within does, and f(n) tells us exactly how many ways there are to do so. In the simplest cases, 1xxxxx1, 11xxxxx and xxxxx11 we have f(5) = 16 ways to fill in the x's, for a total of 48.

In the other cases, the adjacent 1's split the string into two segments. For x11xxxx (and its mirror image xxxx11x), there are C(5,1) = 5 ways to divide {2,3,4,5,6} into sets of size 1 and 4, and f(1) f(4) = 8 ways to arrange each. This gives 2 5 8 = 80 more arrangements.

Similarly, the last mirror pair of template xx11xxx and xxx11xx partition {2,3,4,5,6} in C(5,2) = 10 ways, each of which can be arranged in f(2) f(3) = 8 ways. This adds another 2 8 10 = 160 arrangements, for a total of 288.

This problem can be approached by inductively considering the integers in descending order. This method is more straightforward in a slightly different version of the problem, where all the numbers are distinct. The original problem as stated eventually reduces to this case, so we begin by solving this problem.

Given the $n$ integers $a_1, \ldots, a_n$ in descending order, we will proceed by solving the problem for successive prefixes of the sequence. The answer to the problem on a prefix of length $n$ will be denoted as $S_n$ . The first prefix (of length 1) clearly has only one possible permutation: $a_1$ . Because no pair of neighbors exists, this arrangement is clearly valid. Therefore, $S_1 = 1$ .

We now inductively consider an arbitrary choice out of the $S_m$ valid arrangements of the prefix $a_1, \ldots, a_m$ . We know by assumption that $a_m+1 < a_i$ for all $i \le m$ (because we are considering the integers in descending order, and the integers are distinct). Therefore, placing $a_m+1$ anywhere in the middle of the list would result in an invalid arrangement, because both its neighbors would be greater. The only options are to place it at one of the two ends of the sequence. We thus have exactly 2 possible new arrangements for every existing arrangement; i.e., $S_m+1 = 2S_m$ .

We have inductively found a recurrence which is trivial to solve: $S_n = 2^{n-1}$ , for $n \le 1$ . We let $S_0 = 1$ , for later convenience. Having solved the problem for a set of distinct integers, we must now reduce the original problem to this one.

We first observe that the arrangement $1, a_1, \ldots, a_n, 1$ is valid iff the arrangement $a_1, \ldots, a_n$ is valid and all ${a_n}$ are greater than 1. Thus, the 16 valid arrangements of ${2, 3, 4, 5, 6}$ correspond to 16 valid arrangements of ${1, 1, 2, 3, 4, 5, 6}$ .

To find the rest of the valid arrangements, we must observe the following properties. First, if a 1 is not at an end of the list, then it must be adjacent to the other 1. Otherwise, the arrangement is guaranteed to be invalid. Furthermore, consider the arrangement $a_1, \ldots, a_m, 1, 1, b_1, \ldots, b_n$ . Both $a_m$ and $b_1$ are guaranteed not to violate the condition, because they are adjacent to and greater than 1. It is, therefore, correct to consider the arrangements of $\{a_m\}$ and $\{b_n\}$ as if they are separate sequences. This immediately leads to the following expression for the rest of the answers: $$\displaystyle \sum {i = 0}^5 {{{5}\choose{i}} S {i} S_{5-i}}$$

This summation can be interpreted as placing the two 1s at the $i^\textrm{th}$ position, choosing which $i$ integers will go before them and which $5-i$ integers will go after them, and then finding the number of valid orderings of each set of integers. To evaluate the expression, it is tempting to substitute the recurrence for $S_n$ ; however, because $S_0$ was defined differently (to permit this expression to take its simple form), we must be more careful. Given the small size of the problem, it is not challenging to expand the summation: $$\displaystyle {{5}\choose{0}} 2^4 + {{5}\choose{1}} 2^3 + {{5}\choose{2}} 2^3 + {{5}\choose{3}} 2^3 + {{5}\choose{4}} 2^3 + {{5}\choose{5}} 2^4$$

and evaluate to 272. Adding in the other 16 orderings we found previously, this yields $\textbf{288}$ valid orderings.

It's easy to see that, since $1$ is the smallest number and there are two $1$ 's. Then, the only possibilities we take $1$ should be neighboring each other, or each of them in the edge of number ( i meant, in the last and the first). Because, if they are not in our case there are 1 who not in the edge, and the neighboring is not $1$ , as we know that $2, 3, 4, 5, 6$ are greater than $1$ , so contradiction with our problem. Now, we divide into $4$ cases, that is :

Case $1$ : $\text{11 \_ \_ \_ \_ \_}$ or $\text{ \_ \_ \_ \_ \_ 11}$ . They are symmetric each other. So, we decline $\text{ \_ \_ \_ \_ \_ 11}$ , and then we multiply the result of this case by $2$ .

Then, there are four possibilities to take $2$ and $3$ that is $\text{1123\_ \_ \_}$ , $\text{112\_ \_ \_3}$ , $\text{113\_ \_ \_ 2}$ , or $\text{11\_ \_ \_ 23}$ . See that, the remain number is $4, 5, 6$ . Each of possibilities, $4$ should not in the center of blank position. So, there are $3! - 2! = 6 - 2 = 4$ . Where $2!$ is ways when $4$ in the center. So, total there are $2(4)(4) = 32$

Case $2$ : $\text{\_ 11 \_ \_ \_ \_}$ and $\text{\_ \_ \_ \_ 11 \_}$ . They are symmetric each other. So, we decline $\text{\_ \_ \_ \_ 11 \_}$ , and then we multiply the result of this case by $2$ .

See that $\text{a11 \_ \_ \_ \_}$ . There are $5$ possibilities for $a$ . Now, we remain $4$ numbers, that is $b < c < d < e$ . So, we must take $b$ into position :

$\text{a11b \_ \_ \_}$ or $\text{a11\_ \_ \_ b}$ . Then, $c$ should not in the center of blank position. As from the first case, we obtain $4$ ways. Then, total there are $2(5)(2)(4) = 80$

Case $3$ : $\text{\_ \_ 11 \_ \_ \_}$ and $\text{\_ \_ \_ 11 \_ \_}$ . They are symmetric each other. So, we decline $\text{\_ \_ \_ 11 \_ \_}$ , and then we multiply the result of this case by $2$ .

See that it can be written as $\text{ab11 \_ \_ \_}$ , because $b > 1$ . So, there are $5(4)$ to choose $a$ and $b$ . Also, it will remain $3$ numbers, that is $c < d < e$ . But, $c$ should not in the center of blank position. Then, there $4$ ways as from case $(1)$ So, total there are $2(5)(4)4 = 160$ .

Case $4$ : $\text{1 \_ \_ \_ \_ \_ 1}$ . There are $4$ possibilities to take $2$ and $3$ . That is $\text{123\_ \_ \_ 1}$ , $\text{12\_ \_ \_31}$ , $\text{13\_ \_ \_ 21}$ , or $\text{1\_ \_ \_ 231}$ . Each of possibilities, $4$ should not in the center of blank position. So, there are $3! - 2! = 6 - 2 = 4$ . Where $2!$ is ways when $4$ in the center. So, total there are $(4)(4) = 16$

So, from case $(1)$ to $(4)$ , we obtain total $= 32 + 80 + 160 + 16 = \boxed{288}$ arrangement

Se os números não podem ficar imediatamente entre dois vizinhos maiores, então quanto menor o número, maior será a restrição em relação ao lugar que ele pode ocupar. Nesse caso, cada número 1 só pode ficar nas extremidades ou lado a lado, por ser o menor dos dígitos.

a) Cada número 1 ocupa uma extremidade:

Teremos cinco posições internas para serem preenchidas com a mesma premissa anterior. De modo análogo, o número 2 só pode ocupar a segunda ou quinta posição. Como esses casos são simétricos, basta analisarmos apenas um deles e dobrar o resultado.

Na hipótese do número ser da forma 12 _ _ _ _ 1 , então o número 3 novamente só pode ocupar as posições extremas: terceira e quinta posição. Caso o número comece com 123, então o 4 só não pode ocupar a posição intermediária (dentre as restantes), assim temos 4 possibilidades. Analogamente, caso o número comece com 12 e termine com 31, então o 4 também só não poderá ocupar a posição intermediária (dentre as restantes), assim temos mais 4 possibilidades; totalizando 8 possibilidades.

Portanto, para o caso em que cada número 1 está nas posições extremas, temos 2.8 = 16 sequências.

b) Os números 1 estão lado a lado. (Vamos contar 11 como uma única "casa" e temos mais cinco "casas" restantes)

Nesse caso o problema é encaixar os outros números nas cinco posições restantes. Considerando a simetria do problema, só precisamos contar os casos em que o 11 está na primeira casa, segunda casa e terceira casa, pois as demais são simétricas a essas, respectivamente.

Na primeira situação: 11 _ _ _ _ _ temos um problema totalmente análogo ao inicial do caso (a) e, novamente, teremos 2.8 = 16 sequências.

Na segunda situação: _ 11 _ _ _ _ temos três possibilidades para o número 2 e as possibilidades são analogamente determinadas:

2 11 _ _ _ _ 8 possibilidades.

_ 11 2 _ _ _ 16 possibilidades

_ 11 _ _ _ 2 16 possibilidades

Totalizando 40 sequências possíveis.

Por fim, o terceiro caso: _ _ 11 _ _ _ que se desdobra em quatro análises:

2 _ 11 _ _ _ e _ 2 11 _ _ _ que são análogos: 16 sequências cada. _ _ 11 2 _ _ e _ _ 11 _ _ 2 que são análogos: 24 sequências cada.

Totalizando 2.24 + 2.16 = 80 sequências possíveis.

Portanto, considerando a simetria apontada para o caso (b) , temos:

1. ( 16 + 40 + 80 ) = 272 sequências possíveis.

Finalmente, somando as possibilidades dos casos (a) e (b), obtemos o número total de sequências que podem ser formadas:

N = 272 + 16 = 288 sequências possíveis.

Suppose these seven positions are numbered 1, 2, 3, 4, 5, 6, 7 from left to right. Now we can calculate number of arrangement in the following steps. Case I: Both 1’s are placed at position 1 and 2 Total number of ways of doing this = [4C0+4C1+4C2+4C3+4C4] = 16

Case II: Both 1’s are placed at position 6 and 7 Total number of ways of doing this = [4C0+4C1+4C2+4C3+4C4] = 16

Case III: Both 1’s are placed at position 1 and 7 Total number of ways of doing this = [4C0+4C1+4C2+4C3+4C4] = 16

Case IV: Both 1’s are placed at position 2 and 3 Total number of ways of doing this = 5C1*[3C0+3C1+3C2+3C3] = 40

Case V: Both 1’s are placed at position 3 and 4 Total number of ways of doing this = (5C2) Fact(2) [2C0+2C1+2C2] = 80

Case VI: Both 1’s are placed at position 4 and 5 Total number of ways of doing this = (5C2) Fact(2) [2C0+2C1+2C2] = 80

Case VII: Both 1’s are placed at position 5 and 6 Total number of ways of doing this = 5C1*[3C0+3C1+3C2+3C3] = 40

There are no other ways of arranging these numbers.

Therefore, total number of ways = 16+16+16+40+80+80+40=288

We first show that if we have $k$ distinct integers, there are $2^{k-1}$ ways to arrange them so that no integer is between 2 larger integers. This is true for $k = 1 , 2$ . For $k \geq 3$ , the smallest number must be on one of the two ends, and will be smaller than the number next to it. We remove the smallest number, and by induction we have $2^{k-2}$ ways to arrange the remaining numbers. So this gives $2^{k-1}$ ways to arrange $k$ distinct integers.

We consider how the 1s must be arranged. Since they cannot have two larger integers beside them, they must either be on the two ends, or adjacent to each other. When they are on the two ends, the other 5 integers must be arranged so that no integer is between two larger integers. There are $2^4= 16$ ways to do this. If the 1s are consecutive, we look at two possibilities, either they are in the first or last spot, or they are somewhere in the middle. If they are in the first or last spot, there will be $2^{4}$ ways to arrange the remaining numbers, for a total of $2^5 = 32$ ways, accounting for the two possibilities.

If the 1s are not in the first or last spot, there must be $n$ numbers before them and $5-n$ numbers after them, for some $1 \leq n \leq 4$ . There are $\binom{5}{n}$ ways to choose the numbers that go before the 1s, $2^{n-1}$ ways to arrange them, and $2^{5-n-1}$ ways to arrange the numbers after the 1s. This gives $\sum\limits_{n=1}^{4} \binom{5}{n} 2^{n-1}2^{4-n} = 8\sum\limits_{n=1}^{4}\binom{5}{n} = 8 (2^5 - 2) = 240$ .

So the total number of ways is $16 + 32 + 240 = 288$ .