When an integer is divided by \(3\), there are only three possibilities for the remainder: \(0\), \(1\), or \(2\). Therefore, each of these integers is of the form \(3k\), \(3k+1\) or \(3k+2\) for some non-negative integer \(k\). If we don’t have three integers each of a different form, then the five integers have two possible forms and so there must at least three integers of the same form.
If we have three integers of the same form, then the sum of these three integers is \[3k_1+3k_2+3k_3= 3(k_1+k_2+k_3)\] or \[3k_1+1+3k_2+1+3k_3+1=3(k_1+k_2+k_3+1)\] or \[3k_1+2+3k_2+2+3k_3+2= 3(k_1+k_2+k_3+2)\]
If we have three integers all of different form, then the sum of these three integers is \[3k_1 + 3k_2+1+3k_3+2 = 3(k_1+k_2+k_3+1)\]
In all cases, these sums are divisible by \(3\) and so we can always choose three of the five integers such that their sum is divisible by \(3\).
There are \(7! = 7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1\) permutations of \(1\),\(2\),\(3\),\(4\),\(5\),\(6\),\(7\), because there are \(7\) choices for \(a_1\), then \(6\) choices for \(a_2\), and so on.
We determine the average value of \(a_1 -a_2 +a_3 -a_4 +a_5 -a_6 +a_7\) over all of these permutations by determining the sum of all \(7!\) values of this expression and dividing by \(7!\).
To determine the sum of all \(7!\) values, we determine the sum of the values of \(a_1\) in each of these expressions and call this total \(s_1\), the sum of the values of \(a_2\) in each of these expressions and call this total \(s_2\), and so on.
The sum of the \(7!\) values of the original expression must equal \(s_1 -s_2 +s_3 -s_4 +s_5 -s_6 +s_7\). This uses the fact that, when adding, the order in which we add the same set of numbers does not matter.
By symmetry, the sums of the values of \(a_1, a_2, a_3, a_4, a_5, a_6, a_7\) will all be equal. That is, \(s_1 =s_2 =s_3 =s_4 =s_5 =s_6 =s_7\).
This means that the desired average value equals \[\dfrac{s_1 -s_2 +s_3 -s_4 +s_5 -s_6 +s_7}{7!} = \dfrac{(s_1 +s_3 +s_5 +s_7)-(s_2 +s_4 +s_6)}{7!} = \dfrac{4s_1 -3s_1}{7!} = \dfrac{s_1}{7!}\] So we need to determine the value of \(s_1\).
Now \(a_1\) can equal each of \(1\),\(2\),\(3\),\(4\),\(5\),\(6\),\(7\).
If \(a_1 = 1\), there are \(6!\) combinations of values for \(a_2\), \(a_3\), \(a_4\), \(a_5\), \(a_6\), \(a_7\), since there are still \(6\) choices for \(a_2\), 5 for \(a_3\), and so on.
Similarly, there are \(6!\) combinations with \(a_1\) equal to each of \(2\), \(3\), \(4\), \(5\), \(6\), \(7\).
Thus, \(s+1 = 1\cdot 6!+2\cdot 6!+3\cdot 6!+4\cdot 6!+5\cdot 6!+6\cdot6!+7\cdot6! = 6!(1+2+3+4+5+6+7) = 28(6!)\). Therefore, the average value of the expression is \(\dfrac{28(6!)}{7!} = \dfrac{28(6!)}{7(6!)} = \dfrac{28}{7} = 4\).
We consider choosing the three numbers all at once.
We list the possible sets of three numbers that can be chosen:
\(\{1,2,3\}\)
\(\{1,2,4\}\)
\(\{1,2,5\}\)
\(\{1,3,4\}\)
\(\{1,3,5\}\)
\(\{1,4,5\}\)
\(\{2,3,4\}\)
\(\{2,3,5\}\)
\(\{2,4,5\}\)
\(\{3,4,5\}\)
We have listed each in increasing order because once the numbers are chosen, we arrange them in increasing order.
There are \(10\) sets of three numbers that can be chosen.
Of these \(10\) sets, the \(4\) sequences \(1\),\(2\),\(3\) and \(1\),\(3\),\(5\) and \(2\),\(3\),\(4\) and \(3\),\(4\),\(5\) are arithmetic sequences.
Therefore, the probability that the resulting sequence is an arithmetic sequence is \(\frac{4}{10}\) or \(\frac{2}{5}\).
There are five odd digits: \(1\), \(3\), \(5\), \(7\), \(9\).
We consider the positive integers less than \(1000\) in three sets: those with one digit, those with two digits, and those with three digits.
There are \(5\) positive one-digit integers with one odd digit (namely \(1\), \(3\), \(5\), \(7\), \(9\)).
Consider the two-digit positive integers with only odd digits. Such an integer has the form \(XY\) where \(X\) and \(Y\) are digits. There are five possibilities for each of \(X\) and \(Y\) (since each must be odd). Therefore, there are \(5\times 5 = 25\) two-digit positive integers with only odd digits.
Consider the three-digit positive integers with only odd digits. Such an integer has the form \(XYZ\) where \(X\), \(Y\) and \(Z\) are digits. There are five possibilities for each of \(X\), \(Y\) and \(Z\) (since each must be odd). Therefore, there are \(5\times 5 \times 5= 125\) three-digit positive integers with only odd digits.
In total, there are \(5+25+125=155\) positive integers less than \(1000\) with only odd digits.
We make a table of the \(36\) possible combinations of rolls and the resulting sums:
| \(\boldsymbol{2}\) | \(\boldsymbol{3}\) | \(\boldsymbol{5}\) | \(\boldsymbol{7}\) | \(\boldsymbol{11}\) | \(\boldsymbol{13}\) | |
|---|---|---|---|---|---|---|
| \(\boldsymbol{2}\) | \(4\) | \(5\) | \(7\) | \(9\) | \(13\) | \(15\) |
| \(\boldsymbol{3}\) | \(5\) | \(6\) | \(8\) | \(10\) | \(14\) | \(16\) |
| \(\boldsymbol{5}\) | \(7\) | \(8\) | \(10\) | \(12\) | \(16\) | \(18\) |
| \(\boldsymbol{7}\) | \(9\) | \(10\) | \(12\) | \(14\) | \(18\) | \(20\) |
| \(\boldsymbol{11}\) | \(13\) | \(14\) | \(16\) | \(18\) | \(22\) | \(24\) |
| \(\boldsymbol{13}\) | \(15\) | \(16\) | \(18\) | \(20\) | \(24\) | \(26\) |
Of the \(36\) entries in the table, \(6\) are prime numbers (two entries each of \(5\), \(7\) and \(13\)). Therefore, the probability that the sum is a prime number is \(\frac{6}{36}\) or \(\frac{1}{6}\).
(Note that each sum is at least \(4\) and so must be odd to be prime. Since odd plus odd equals even, then the only possibilities that really need to be checked are even plus odd and odd plus even, that is, the first row and first column of the table.)
Solution 1
There are two possibilities: either each player wins three games or one player wins more games than the other.
Since the probability that each player wins three games is \(\frac{5}{16}\), the probability that any one player wins more games than the other is \(1 - \dfrac{5}{16}=\dfrac{11}{16}\).
Since each of Blaise and Pierre is equally likely to win any given game, each must be equally likely to win more games than the other.
Therefore, the probability that Blaise wins more games than Pierre is \(\dfrac{1}{2}\times\dfrac{11}{16}=\dfrac{11}{32}\).
Solution 2
We consider the results of the \(6\) games as a sequence of \(6\) Bs or Ps, with each letter a B if Blaise wins the corresponding game or P if Pierre wins.
Since the two players are equally skilled, the probability that each wins a given game is \(\frac{1}{2}\). This means that the probability of each letter being a B is \(\frac{1}{2}\) and the probability of each letter being a P is also \(\frac{1}{2}\).
Since each sequence consists of \(6\) letters, the probability of a particular sequence occurring is \(\left(\dfrac{1}{2}\right)^6=\dfrac{1}{64}\), because each of the letters is specified.
Since they play \(6\) games in total, the probability that Blaise wins more games than Pierre is the sum of the probabilities that Blaise wins \(4\) games, that Blaise wins \(5\) games, and that Blaise wins \(6\) games.
If Blaise wins \(6\) games, then the sequence consists of \(6\) Bs. The probability of this is \(\frac{1}{64}\), since there is only one way to arrange \(6\) Bs.
If Blaise wins \(5\) games, then the sequence consists of \(5\) Bs and \(1\) P. The probability of this is \(6 \times \dfrac{1}{64} = \dfrac{6}{64}\), since there are \(6\) possible positions in the list for the \(1\) P (eg. PBBBBB, BPBBBB, BBPBBB, BBBPBB, BBBBPB, BBBBBP).
The probability that Blaise wins \(4\) games is \(\binom{6}{2} \times \dfrac{1}{64} = \dfrac{15}{64}\), since there are \(\binom{6}{2}=15\) ways for \(4\) Bs and \(2\) Ps to be arranged.
Therefore, the probability that Blaise wins more games than Pierre is \(\dfrac{1}{64}+\dfrac{6}{64}+\dfrac{15}{64}=\dfrac{22}{64}=\dfrac{11}{32}\).
Solution 1
Suppose that the bag contains \(g\) gold balls. We assume that Feridun reaches into the bag and removes the two balls one after the other.
There are \(40\) possible balls that he could remove first and then \(39\) balls that he could remove second. In total, there are \(40(39)\) pairs of balls that he could choose in this way.
If he removes \(2\) gold balls, then there are \(g\) possible balls that he could remove first and then \(g-1\) balls that he could remove second. In total, there are \(g(g-1)\) pairs of gold balls that he could remove.
We are told that the probability of removing \(2\) gold balls is \(\dfrac{5}{12}\). Since there are \(40(39)\) total pairs of balls that can be chosen and \(g(g-1)\) pairs of gold balls that can be chosen in this way, we have \(\dfrac{g(g-1)}{40(39)}=\dfrac{5}{12}\) which is equivalent to \(g(g-1) = \dfrac{5}{12}(40)(39) = 650\).
Therefore, \(g^2 - g - 650 = 0\) or \((g-26)(g+25) = 0\), and so \(g=26\) or \(g=-25\). Since \(g>0\), we have \(g=26\), so there are \(26\) gold balls in the bag.
Solution 2
Suppose that the bag contains \(g\) gold balls. We assume that Feridun reaches into the bag and removes the two balls together.
Since there are \(40\) balls in the bag, there are \(\displaystyle{40 \choose 2}\) pairs of balls that he could choose in this way.
Since there are \(g\) gold balls in the bag, there are \(\displaystyle{g \choose 2}\) pairs of gold balls that he could choose in this way.
We are told that the probability of removing \(2\) gold balls is \(\dfrac{5}{12}\). Since there are \(\displaystyle{40 \choose 2}\) pairs in total that can be chosen and \(\displaystyle{g \choose 2}\) pairs of gold balls that can be chosen in this way, we have \(\dfrac{\displaystyle{g \choose 2}}{\displaystyle{40 \choose 2}}=\dfrac{5}{12}\) which is equivalent to \(\displaystyle{g \choose 2} = \dfrac{5}{12}\displaystyle{40 \choose 2}\). Since \(\displaystyle{n \choose 2} = \dfrac{n(n-1)}{2}\), this equation is equivalent to \(\dfrac{g(g-1)}{2} = \dfrac{5}{12}\cdot \dfrac{40(39)}{2} = 325\).
Therefore, \(g(g-1)=650\) or \(g^2 - g - 650 = 0\) or \((g-26)(g+25) = 0\), and so \(g=26\) or \(g=-25\). Since \(g>0\), we have \(g=26\), so there are \(26\) gold balls in the bag.
The number of integers between \(100\) and \(999\) inclusive is \(999-100+1=900\).
An integer \(n\) in this range has three digits, say \(a\), \(b\) and \(c\), with the hundreds digit equal to \(a\). Note that \(0\leq b \leq 9\) and \(0\leq c \leq 9\) and \(1 \leq a \leq 9\).
To have \(a+b+c=24\), then the possible triples for \(a\),\(b\),\(c\) in some order are \(9\),\(9\),\(6\); \(9\),\(8\),\(7\); \(8\),\(8\),\(8\). (There cannot be three \(9\)’s. If there are two \(9\)’s, the the other digit equals \(6\). If there is one \(9\), the second and third digits add to \(15\) but are both less than \(9\), so must equal \(8\) and \(7\). If there are zero \(9\)’s, the maximum for each digit is \(8\), and so each digit must be \(8\) in order for the sum of all three to equal \(24\).)
If the digits are \(9\), \(9\) and \(6\), there are \(3\) arrangements: \(996\), \(969\), \(699\).
If the digits are \(9\), \(8\) and \(7\), there are \(6\) arrangements: \(987\), \(978\), \(897\), \(879\), \(798\), \(789\).
If the digits are \(8\), \(8\) and \(8\), there is only \(1\) arrangement: \(888\).
Therefore, there are \(3+6+1=10\) integers \(n\) in the range \(100\) to \(999\) with the sum of the digits of \(n\) equal to \(24\).
The required probability equals the number of possible values of \(n\) with the sum of digits equal to \(24\) divided by the total number of integers in the range, or \(\dfrac{10}{900}=\dfrac{1}{90}\).
Suppose that Billy removes the ball numbered \(x\) from his bag and that Crystal removes the ball numbered \(y\) from her bag.
Then \(b=1+2+3+4+5+6+7+8+9-x=45-x\).
Also, \(c=1+2+3+4+5+6+7+8+9-y=45-y\).
Hence, \(b-c=(45-x)-(45-y)=y-x\).
Since \(1\leq x \leq 9\) and \(1 \leq y \leq 9\), we have \(-8 \leq y-x \leq 8\). (This is because \(y-x\) is maximized when \(y\) is largest (that is, \(y=9\)) and \(x\) is smallest (that is, \(x=1\)), so \(y-x \leq 9 - 1 = 8\). Similarly, \(y-x \geq -8\).)
Since \(b-c=y-x\) is between \(-8\) and \(8\), for it to be a multiple of \(4\), \(b-c=y-x\) must be \(-8\), \(-4\), \(0\), \(4\), or \(8\).
Since each of Billy and Crystal chooses \(1\) ball from \(9\) balls and each ball is equally likely to be chosen, the probability of any specific ball being chosen from one of their bags is \(\frac{1}{9}\). Thus, the probability of any specific pair of balls being chosen (one from each bag) is \(\dfrac{1}{9} \times \dfrac{1}{9}= \dfrac{1}{81}\).
Therefore, to compute the desired probability, we must count the number of pairs \((x,y)\) where \(y-x\) is \(-8\), \(-4\), \(0\), \(4\), \(8\), and multiply this result by \(\frac{1}{81}\).
Method 1
If \(y-x=-8\), then \((x,y)\) must be \((9,1)\).
If \(y-x=8\), then \((x,y)\) must be \((1,9)\).
If \(y-x=-4\), then \((x,y)\) can be \((5,1)\), \((6,2)\), \((7,3)\), \((8,4)\), \((9,5)\).
If \(y-x=4\), then \((x,y)\) can be \((1,5)\), \((2,6)\), \((3,7)\), \((4,8)\), \((5,9)\).
If \(y-x=0\), then \((x,y)\) can be \((1,1)\), \((2,2)\), \((3,3)\), \((4,4)\), \((5,5)\), \((6,6)\), \((7,7)\), \((8,8)\), \((9,9)\).
There are thus \(21\) pairs \((x,y)\) that work, so the desired
probability is \(\dfrac{21}{81}=\dfrac{7}{27}\).
Method 2
If \(x=9\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(9\), \(5\)
or \(1\).
If \(x=8\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(8\) or \(4\).
If \(x=7\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(7\) or \(3\).
If \(x=6\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(6\) or \(2\).
If \(x=5\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(9\), \(5\)
or \(1\).
If \(x=4\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(8\) or \(4\).
If \(x=3\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(7\) or \(3\).
If \(x=2\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(6\) or \(2\).
If \(x=1\), then for \(y-x\) to be a multiple of \(4\), \(y\) must be \(9\), \(5\)
or \(1\).
There are thus \(21\) pairs \((x,y)\) that work, so the desired
probability is \(\dfrac{21}{81}=\dfrac{7}{27}\).
If she tosses \(3\) heads on the first toss, then she has no coins to toss on the second toss, so she cannot toss exactly \(1\) head.
If she tosses \(2\), \(1\) or \(0\) heads on the first toss, then she has at least one coin to toss on the second toss, so it is possible for her to toss exactly \(1\) head on the second toss.
The following possibilities exist:
She tosses \(2\) heads out of \(3\) coins on the first toss and she tosses \(1\) head out of \(1\) coin on the second toss
She tosses \(1\) head out of \(3\) coins on the first toss and she tosses \(1\) head out of \(2\) coins on the second toss
She tosses \(0\) heads out of \(3\) coins on the first toss and she tosses \(1\) head out of \(3\) coins on the second toss
We calculate the various probabilities.
If \(3\) coins are tossed, there are \(8\) equally likely possibilities: HHH, HHT, HTH, THH, TTH, THT, HTT, TTT. Each of these possibilities has probability \(\left(\dfrac{1}{2}\right)^3 = \dfrac{1}{8}\). Therefore,
the probability of tossing \(0\) heads out of \(3\) coins is \(\frac{1}{8}\)
the probability of tossing \(1\) head out of \(3\) coins is \(\frac{3}{8}\)
the probability of tossing \(2\) heads out of \(3\) coins is \(\frac{3}{8}\)
the probability of tossing \(3\) heads out of \(3\) coins is \(\frac{1}{8}\)
If \(2\) coins are tossed, there are \(4\) equally likely possibilities: HH, HT, TH, TT. Each of these possibilities has probability \(\left(\dfrac{1}{2}\right)^2 = \dfrac{1}{4}\). Therefore, the probability of tossing \(1\) head out of \(2\) coins is \(\dfrac{2}{4}=\dfrac{1}{2}\).
If \(1\) coin is tossed, the probability of tossing \(1\) head is \(\frac{1}{2}\).
To summarize, the possibilities are
She tosses \(2\) heads out of \(3\) coins on the first toss (with probability \(\frac{3}{8}\)) and she tosses \(1\) head out of \(1\) coin on the second toss (with probability \(\frac{1}{2}\))
She tosses \(1\) head out of \(3\) coins on the first toss (with probability \(\frac{3}{8}\)) and she tosses \(1\) head out of \(2\) coins on the second toss (with probability \(\frac{1}{2}\))
She tosses \(0\) heads out of \(3\) coins on the first toss (with probability \(\frac{1}{8}\)) and she tosses \(1\) head out of \(3\) coins on the second toss (with probability \(\frac{3}{8}\))
Therefore, the overall probability is \(\frac{3}{8}\cdot \frac{1}{2} + \frac{3}{8} \cdot \frac{1}{2} + \frac{1}{8}\cdot \frac{3}{8} = \frac{27}{64}\).
Let \(P(10)\) be the probability the product of the numbers on the two balls chosen is divisible by \(10\).
Since there are \(10\) balls in each bag, there are \(10 \cdot 10 = 100\) pairs of balls that can be chosen.
Let \(a\) be the number on the first ball chosen and \(b\) be the number on the second ball chosen. To determine \(P(10)\), we count the number of pairs \((a,b)\) for which \(ab\) is divisible by \(10\). If the number of pairs is \(m\), then \(P(10) = \dfrac{m}{100}\).
For \(ab\) to be divisible by \(10\), at least one of \(a\) and \(b\) must be a multiple of \(5\) and at least one of \(a\) and \(b\) must be even.
If \(a=10\) or \(b=10\), then the pair \((a,b)\) gives a product \(ab\) divisible by \(10\). In this case, we obtain the \(19\) pairs \[(a,b)=(1,10),(2,10),\ldots,(9,10),(10,10),(10,9),\ldots,(10,2),(10,1)\] If neither \(a\) nor \(b\) equals \(10\), then either \(a=5\) or \(b=5\) in order for \(a\) or \(b\) to be divisible by \(5\). In this case, the other of \(a\) and \(b\) must be even and not equal to \(10\). (We have already counted the pairs where \(a=10\) or \(b=10\).) In this case, we obtain the \(8\) pairs \[(a,b)=(5,2),(5,4),(5,6),(5,8),(2,5),(4,5),(6,5),(8,5)\] From our work above, there are no additional pairs for which \(ab\) is divisible by \(10\).
Thus, there are \(19+8=27\) pairs \((a,b)\) for which \(ab\) is divisible by \(10\), which means that \(P(10) = \dfrac{27}{100}\). (We note that we could have made a \(10\) by \(10\) table that listed all possible combinations of \(a\) and \(b\) and their product, from which we could obtain \(P(10)\).)
There are \(2^{10} = 1024\) strings of ten letters, each of which is \(A\) or \(B\), because there are \(2\) choices for each of the \(10\) positions in the string.
We determine the number of these strings that do not include the "substring" \(ABBA\) (that is, that do not include consecutive letters \(ABBA\)) by counting the number of strings that do include the substring \(ABBA\) and subtracting this total from \(1024\).
If a string includes the substring \(ABBA\), there are \(7\) possible positions in which this substring could start \[(ABBAxxxxxx,\, xABBAxxxxx,\, \ldots,\, xxxxxxABBA).\] There are \(2\) choices for each of the remaining \(6\) letters in such a string, so there are \(7\cdot 2^6 = 448\) occurrences of the substring \(ABBA\) among the \(1024\) strings.
This does not mean that there are \(448\) strings that contain the substring \(ABBA\). Since \(ABBA\) can appear multiple times in a single string, this total will count some strings more than once. (For example, the string \(ABBAAAABBA\) is included in both the first and seventh of these categories, so this string is counted twice.)
So we must "correct"this total of \(448\) by accounting for the strings in which \(ABBA\) occurs more than once.
Since two substrings of \(ABBA\) can overlap in \(0\) letters (for example, \(ABBAABBAxx\)) or in \(1\) letter (for example, \(ABBABBAxxx\)), the maximum number of times that the substring \(ABBA\) can appear is \(3\), and there is only one such string: \(ABBABBABBA\).
If a string contains two copies of \(ABBA\) that overlap, then it must be of one of the following forms: \[ABBABBAxxx, \quad xABBABBAxx, \quad xxABBABBAx, \quad xxxABBABBA\] Since there are \(4\) choices for the starting position of \(ABBABBA\) and \(2\) choices for each of the three unknown letters, then there are \(4 \cdot 2^3 = 32\) occurrences of \(ABBABBA\) among all of these strings.
But the string \(ABBABBABBA\) is counted in each of the first and last categories, so we subtract \(2\) occurrences from this total to obtain \(30\), the total number of strings of ten letters that included exactly two overlapping copies of \(ABBA\). (We’ll count the string \(ABBABBABBA\) later.)
If a string contains exactly two substrings of \(ABBA\) and these do not overlap, then it must be of one of the following forms: \[ABBAABBAxx, \quad ABBAxABBAx, \quad ABBAxxABBA,\]\[xABBAABBAx, \quad xABBAxABBA, \quad xxABBAABBA\] Since there are \(6\) such forms and \(2\) choices for each of the \(2\) unknown letters in each case, there appear to be \(6 \cdot 2^2 = 24\) such strings.
This total includes the string \(ABBABBABBA\) in the third category, so we subtract \(1\) from this total to obtain \(23\), the total number of strings of ten letters that include exactly two copies of \(ABBA\) which do not overlap.
So there are \(30\) strings that contain exactly two overlapping substrings \(ABBA\), \(23\) strings that contain exactly two non-overlapping substrings \(ABBA\), and \(1\) string that contains exactly three substrings \(ABBA\).
To get the total number of strings with one or more substrings \(ABBA\) we take the total number of occurrences of \(ABBA\) (\(448\)), subtract the number of strings with exactly two substrings \(ABBA\) (since these were included twice in the original count), and subtract two times the number of strings with exactly three substrings \(ABBA\) (since these were included three times in the original count).
Therefore, there are \(448 - 23 - 30 - 2\cdot 1 = 393\) strings that include at least one substring \(ABBA\), and so there are \(1024-393 = 631\) strings of ten letters that do not include the substring \(ABBA\).
The Eden sequences from \(\{1,2,3,4,5\}\) are
\(1\)
\(3\)
\(5\)
\(1,2\)
\(1,4\)
\(3,4\)
\(1,2,3\)
\(1,2,5\)
\(1,4,5\)
\(3,4,5\)
\(1,2,3,4\)
\(1,2,3,4,5\)
There are \(12\) such sequences.
We present a brief justification of why these are all of the sequences.
An Eden sequence of length \(1\) consists of a single odd integer. The possible choices are \(1\) and \(3\) and \(5\).
An Eden sequence of length \(2\) consists of an odd integer followed by a larger even integer. Since the only possible even integers here are \(2\) and \(4\), the possible sequences are \(1, 2\) and \(1, 4\) and \(3, 4\).
An Eden sequence of length \(3\) starts with an Eden sequence of length \(2\) and appends (that is, adds to the end) a larger odd integer. Starting with \(1,2\), we form \(1,2,3\) and \(1,2,5\). Starting with \(1,4\), we form \(1,4,5\). Starting with \(3,4\), we form \(3,4,5\).
An Eden sequence of length \(4\) starts with an Eden sequence of length \(3\) and appends a larger even integer. Since \(2\) and \(4\) are the only possible even integers, the only possible sequence here is \(1,2,3,4\).
An Eden sequence of length \(5\) from \(\{1,2,3,4,5\}\) must include all \(5\) elements, so is \(1,2,3,4,5\).
Throughout this problem, we represent the states of the \(n\) plates as a string of \(0\)’s and \(1\)’s (called a binary string) of length \(n\) of the form \(p_1p_2\cdots p_n\), with the \(r\)th digit from the left (namely \(p_r\)) equal to \(1\) if plate \(r\) contains a gift and equal to \(0\) if plate \(r\) does not. We call a binary string of length \(n\) allowable if it satisfies the requirements – that is, if no two adjacent digits both equal \(1\). Note that digit \(p_n\) is also "adjacent" to digit \(p_1\), so we cannot have \(p_1=p_n=1\).
Suppose that \(p_1=1\). Then \(p_2=p_7=0\), so the string is of the form \(10p_3p_4p_5p_60\).
Since \(k=3\), we know that \(2\) of \(p_3\), \(p_4\), \(p_5\), \(p_6\) equal \(1\), but in such a way that no two adjacent digits are both \(1\). The possible strings in this case are \(1010100\), \(1010010\) and \(1001010\).
Suppose that \(p_1=0\). Then \(p_2\) can equal \(1\) or \(0\).
If \(p_2=1\), then \(p_3=0\) as well. This means that the string is of the form \(010p_4p_5p_6p_7\), which is the same as the general string in the first case, but shifted by \(1\) position around the circle, so there are again \(3\) possibilities.
If \(p_2=0\), then the string is of the form \(00p_3p_4p_5p_6p_7\) and \(3\) of the digits \(p_3\), \(p_4\), \(p_5\), \(p_6\), \(p_7\) equal \(1\) in such a way that no \(2\) adjacent digits equal \(1\). There is only \(1\) way in which this can happen: \(0010101\).
Overall, this gives \(7\) possible configurations, so \(f(7,3)=7\).
Solution 1
An allowable string \(p_1p_2\cdots p_{n-1}p_n\) has \((p_1,p_n)=(1,0)\), \((0,1)\), or \((0,0)\).
Define \(g(n,k,1,0)\) to be the number of allowable strings of length \(n\), containing \(k\) 1’s, and with \((p_1,p_n)=(1,0)\). We define \(g(n,k,0,1)\) and \(g(n,k,0,0)\) in a similar manner.
Note that \(f(n,k)=g(n,k,1,0)+g(n,k,0,1)+g(n,k,0,0)\).
Consider the strings counted by \(g(n,k,0,1)\). Since \(p_n=1\), we know that \(p_{n-1}=0\). Since \(p_1=0\), the digit \(p_2\) can equal \(0\) or \(1\).
We remove the first and last digits of these strings. We obtain strings \(p_2p_3\cdots p_{n-2}p_{n-1}\) that is strings of length \(n-2\) containing \(k-1\) 1’s.
Since \(p_{n-1}=0\), the first and last digits of these strings are not both \(1\). Also, since the original strings did not contain two consecutive 1’s, these new strings does not either.
Therefore, \(p_2p_3\cdots p_{n-2}p_{n-1}\) are allowable strings of length \(n-2\) containing \(k-1\) 1’s, with \(p_{n-1}=0\) and \(p_2=1\) or \(p_2=0\).
The number of such strings with \(p_2=1\) and \(p_{n-1}=0\) is \(g(n-2,k-1,1,0)\) and the number of such strings with \(p_2=0\) and \(p_{n-1}=0\) is \(g(n-2,k-1,0,0)\). Thus, \(g(n,k,0,1)=g(n-2,k-1,1,0)+g(n-2,k-1,0,0)\).
Consider the strings counted by \(g(n,k,0,0)\). Since \(p_1=0\) and \(p_n=0\), we can remove \(p_n\) to obtain strings \(p_1p_2\cdots p_{n-1}\) of length \(n-1\) containing \(k\) 1’s. These strings are allowable since \(p_1=0\) and the original strings were allowable. Note that we have \(p_1=0\) and \(p_{n-1}\) is either \(0\) or \(1\).
So the strings \(p_1p_2\cdots p_{n-1}\) are allowable strings of length \(n-1\) containing \(k\) 1’s, starting with \(0\), and ending with \(0\) or \(1\).
The number of such strings with \(p_1=0\) and \(p_{n-1}=0\) is \(g(n-1,k,0,0)\) and the number of such strings with \(p_1=0\) and \(p_{n-1}=1\) is \(g(n-1,k,0,1)\). Thus, \(g(n,k,0,0)=g(n-1,k,0,0)+g(n-1,k,0,1)\).
Consider the strings counted by \(g(n,k,1,0)\). Here, \(p_1=1\) and \(p_n=0\). Thus, \(p_{n-1}\) can equal \(0\) or \(1\). We consider these two sets separately.
If \(p_{n-1}=0\), then the string \(p_1p_2\cdots p_{n-1}\) is an allowable string of length \(n-1\), containing \(k\) 1’s, beginning with \(1\) and ending with \(0\). Therefore, the number of strings counted by \(g(n,k,1,0)\) with \(p_{n-1}=0\) is equal to \(g(n-1,k,1,0)\).
If \(p_{n-1}=1\), then the string \(p_2p_3\cdots p_{n-1}\) is of length \(n-2\), begins with \(0\) and ends with \(1\). Also, it contains \(k-1\) 1’s (having removed the original leading \(1\)) and is allowable since the original string was. Therefore, the number of strings counted by \(g(n,k,1,0)\) with \(p_{n-1}=1\) is equal to \(g(n-2,k-1,0,1)\).
Therefore, \[\begin{align*} f(n,k) & = g(n,k,1,0)+g(n,k,0,1)+g(n,k,0,0)\\ & = (g(n-1,k,1,0)+g(n-2,k-1,0,1))\\ & \qquad + (g(n-2,k-1,1,0)+g(n-2,k-1,0,0))\\ & \qquad + (g(n-1,k,0,0)+g(n-1,k,0,1))\\ & = (g(n-1,k,1,0)+g(n-1,k,0,1)+g(n-1,k,0,0))\\ & \qquad +(g(n-2,k-1,0,1)+g(n-2,k-1,1,0)+g(n-2,k-1,0,0))\\ & = f(n-1,k)+f(n-2,k-1)\end{align*}\] as required.
Solution 2
We develop an explicit formula for \(f(n,k)\) by building these strings.
Consider the allowable strings of length \(n\) that include \(k\) \(1\)’s. Either \(p_n=0\) or \(p_n=1\).
Consider first the case when \(p_n=0\). Here, \(p_1\) can equal \(0\) or \(1\). These strings are all of the form \(p_1p_2p_3 \cdots p_{n-1}0\). In this case, since a \(1\) is always followed by a \(0\) and the strings end with \(0\), we can build these strings using blocks of the form \(10\) and \(0\). Any combination of these blocks will be an allowable string, as each \(1\) will always be both preceded and followed by a \(0\). Thus, these strings can all be built using \(k\) \(10\) blocks and \(n-2k\) \(0\) blocks. This gives \(k\) \(1\)’s and \(k+(n-2k)=n-k\) \(0\)’s. Note that any string built with these blocks will be allowable and will end with a \(0\), and any such allowable string can be built in this way. The number of ways of arranging \(k\) blocks of one kind and \(n-2k\) blocks of another kind is \(\binom{k+(n-2k)}{k}\), which simplifies to \(\binom{n-k}{k}\).
Consider next the case when \(p_n=1\). Here, we must have \(p_{n-1}=p_1=0\), since these are the two digits adjacent to \(p_n\). Thus, these strings are all of the form \(0p_2p_3 \cdots 01\).
Consider the strings formed by removing the first and last digits. These strings are allowable, are of length \(n-2\), include \(k-1\) 1’s, end with \(0\), and can begin with \(0\) or \(1\). Again, since a \(1\) is always followed by a \(0\) and the strings end with \(0\), we can build these strings using blocks of the form \(10\) and \(0\). Any combination of these blocks will be an allowable string, as each \(1\) will always be both preceded and followed by a \(0\). Translating our method of counting from the first case, there are \(\binom{(n-2)-(k-1)}{k-1}\) or \(\binom{n-k-1}{k-1}\) such strings.
Thus, \(f(n,k)=\binom{n-k}{k} + \binom{n-k-1}{k-1}\) such strings.
To prove the desired fact, we will use the fact that \(\binom{m}{r}=\binom{m-1}{r}+\binom{m-1}{r-1}\), which we prove at the end. Now \[\begin{align*} &f(n-1,k)+f(n-2,k-1)\\ & = \binom{(n-1)-k}{k} + \binom{(n-1)-k-1}{k-1} \\ & \qquad + \binom{(n-2)-(k-1)}{k-1} + \binom{(n-2)-(k-1)-1}{(k-1)-1}\\ & = \binom{n-k-1}{k} + \binom{n-k-2}{k-1} + \binom{n-k-1}{k-1} + \binom{n-k-2}{k-2} \\ & = \binom{n-k-1}{k} + \binom{n-k-1}{k-1} + \binom{n-k-2}{k-1} + \binom{n-k-2}{k-2}\\ & = \binom{n-k}{k} + \binom{n-k-1}{k-1} & \text{(using the identity above)}\\ & = f(n,k)\end{align*}\] as required.
To prove the identity, we expand the terms on the right side: \[\begin{align*} \binom{m-1}{r}+\binom{m-1}{r-1} & = \frac{(m-1)!}{r!(m-r-1)!} + \frac{(m-1)!}{(r-1)!(m-r)!}\\ & = \frac{(m-1)!(m-r)}{r!(m-r-1)!(m-r)} + \frac{r(m-1)!}{r(r-1)!(m-r)!}\\ & = \frac{(m-1)!(m-r)}{r!(m-r)!} + \frac{r(m-1)!}{r!(m-r)!}\\ & = \frac{(m-1)!(m-r+r)}{r!(m-r)!}\\ & = \frac{(m-1)!m}{r!(m-r)!}\\ & = \frac{m!}{r!(m-r)!}\\ & = \binom{m}{r}\end{align*}\] as required.