There is a standard deck of $52$ cards without jokers. The deck consists of four suits(diamond, club, heart, spade) which include thirteen cards in each. For each suit, all thirteen cards are ranked from “$2$” to “$A$” (i.e. $2, 3,\ldots , Q, K, A$). A pair of cards is called a “straight flush” if these two cards belong to the same suit and their ranks are adjacent. Additionally, "$A$" and "$2$" are considered to be adjacent (i.e. "A" is also considered as "$1$"). For example, spade $A$ and spade $2$ form a “straight flush”; diamond $10$ and diamond $Q$ are not a “straight flush” pair. Determine how many ways of picking thirteen cards out of the deck such that all ranks are included but no “straight flush” exists in them.
Problem
Source: China south east mathematical olympiad 2006 day1 problem 3
Tags: algorithm, geometry, geometric transformation, combinatorics unsolved, combinatorics
05.07.2013 07:21
$3^{13}-3.$
05.07.2013 15:32
Are Ace and King adjacent? (Your wording says that it is not so, but just clarifying.)
06.07.2013 07:28
chaotic_iak wrote: Are Ace and King adjacent? (Your wording says that it is not so, but just clarifying.) ace is considered as "1", thus it's adjacent to "K" and "2".
06.07.2013 10:36
Then the answer is $4 \cdot 3^{12}$. Pick any suit for the Ace; now, in order from 2 to King, pick any suit that is not the suit picked for the previous rank. This guarantees that no straight flush is formed. Additionally, any such hand with all ranks but no straight flushes can be formed in this way, and it's easy to see that every valid hand is generated by exactly one way, so the number of ways to complete our algorithm above is equal to the number of valid hands. We have $4$ choices for the first rank (Ace) and $3$ choices for every next rank; multiply them all.
07.07.2013 14:48
chaotic_iak wrote: Then the answer is $4 \cdot 3^{12}$. Pick any suit for the Ace; now, in order from 2 to King, pick any suit that is not the suit picked for the previous rank. This guarantees that no straight flush is formed. Additionally, any such hand with all ranks but no straight flushes can be formed in this way, and it's easy to see that every valid hand is generated by exactly one way, so the number of ways to complete our algorithm above is equal to the number of valid hands. We have $4$ choices for the first rank (Ace) and $3$ choices for every next rank; multiply them all. Sorry, when i recheck the official solution, i realize that i have made a mistake in my translation. Indeed, "A" should be adjacent to both "K" and "2" in accord with the purpose of the author of this problem. That's to say, every rank is adjacent to other two ranks, thereore all ranks actually form a cycle. Current translation has been revised properly.
23.07.2013 16:40
Let us generalize the problem as follow: given $n\ge 3$, four sequences $A=(a_1,a_2,\cdots ,a_n), B=(b_1,b_2,\cdots ,b_n),C=(c_1,c_2,\cdots ,c_n),$ $D=(d_1,d_2,\cdots ,d_n)$, let $x_n$ denote the number of ways of picking $n$ terms out of the $4$ sequences such that the following conditions are satisfied: (i) all subscripts of $1,2,\cdots ,n$ appear once. (ii) any two of those $n$ terms do not belong to the same sequence if their subscripts are adjacent.(subscript $1$ and subscript $n$ are considered to be adjacent as well) Now we find the expression for $x_n$. Let us divide a circle into $n$ sectors which are labeled with $1,2,\cdots ,n$ orderly. We use four colors to represent sequences $A,B,C,D$ respectively. When a term with its subscript equal to $i$ is picked out from a sequence, we color the sector that is labeled with $i$ in the color corresponding to the sequence. A way of pick out $n$ terms satisfying the conditions is equivalent to a way of coloring all sectors in four colors such that adjacent sectors are in different colors. That is, there are $x_n$ ways of coloring all sectors in four colors such that adjacent sectors are in different colors. We easily have $x_1=4, x_2=12$ and a recurrence formula: $x_n+x_{n-1}=4\cdot 3^{n-1} (n\ge 3) \cdots$ (1) We rewrite (1) as follow: $(-1)^nx_n-(-1)^{n-1}x_{n-1}=-4\cdot (-3)^{n-1}$ Then we have: $(-1)^{n-1}x_{n-1}-(-1)^{n-2}x_{n-2}=-4\cdot (-3)^{n-2}$ $\vdots$ $(-1)^3x_3-(-1)^{2}x_{2}=-4\cdot (-3)^{2}$ $(-1)^2x_2=-4\cdot (-3)$ Summing up all the equations yields $(-1)^nx_n=(-3)^n+3$, thus $x_n=3^n+3\cdot (-1)^n (n\ge 2)$. So in the case of this problem, $x_{13}=3^{13}-3$.