Tag Info

Hot answers tagged

4

There is a book called "Proofs that Really Count: The Art of Combinatorial Proof" by Arthur T. Benjamin and Jennifer J. Quinn, which might be of interest to you.


4

Jack D'Aurizio's answer works very well, but I see another way to solve it using chromatic polynomials. I understand that this is not the way your book wants you to solve it, but I'm posting it here for future reference: Draw a graph with five vertices with edges connecting the vertices that cannot receive the same color. (The edges are AC, AD, BD, BE, and ...


3

If a single colour appears more than once, it must appear at two consecutive vertices and nowhere else, hence the possible colourings fulfilling the constraints are: $T_0$: $ABCDE$; $T_1$: $AABCD$ and cyclic shifts; $T_2$: $AABBC$ and cyclic shifts. There are $7\cdot 6\cdot 5\cdot 4\cdot 3 = 2520$ colourings in $T_0$, $5\cdot(7\cdot 6\cdot 5\cdot ...


3

Let $A_i$ denote the number of times number $i$ appears (each number is equally likely to appear) and $\mathcal{A}$ be the set of all possible combinations of $a\equiv(a_1,\dots,a_K)$ s.t. $\sum_{k=1}^Ka_k=N$ and each $a_k\ge 0$. Then for $a\in \mathcal{A}$ ...


2

There are $7$ ways to color vertex $A$, split in two cases: Case $1$: $D$ and $C$ have the same color, there are $6$ ways to pick that color, after this, vertices $E$ and $B$ must be distinct and must not have the color of $D$ and $C$, there are $6\cdot 5$ ways to do this, $7\cdot6\cdot6\cdot5=1260$ total. Case $2$: $D$ and $C$ have different colors, ...


2

There are indeed $24$ ways to return to $(0,0)$ if we move in all four directions, but we can also get there moving only north and south or only east and west. Each possibility gives us $\binom{4}{2}=6$ options. Hence there are $24+12=36$ ways to return to $(0,0)$ in $4$ moves. On the other hand there are $4^4$ possible movement sequences. Final answer is ...


2

By saying we are "arranging" the books on a shelf, the order usually matters. So my calculations assume that the order of the books matters. To do this, first we choose the math books, which can be done in ${7 \choose 3}$ ways. Then we choose the history books, which can be done in ${4 \choose 2}$ ways. Then we choose the fiction books, which can be done in ...


2

In how many ways can two distinct subsets of the set A of k (k≥3) elements be selected so that they have exactly two common elements? Choose two elements for intersection: $$\binom k2=\frac{k(k-1)}2$$ Rest two elements have 3 choices: $A-B,B-A,(A\cup B)'$ and minus for one case where all go to $(A\cup B)'$ because then $A=B$: $$3^{k-2}-1$$ Since we ...


2

You are assuming that all the elements of $A$ have to be in one subset or the other, which is not required. After you put the two elements in both $P$ and $Q$, each element can go in $P$, in $Q$, or neither independently. That gives a factor $3$ for each of the $k-2$ remaining elements. You divide by $2$ because you are double counting-each assignment of ...


2

I believe the bounty should go to Tad, who developed the mathematical approach. I tried to improve on it but couldn't, so instead I coded it a whole lot faster :-). Here's the code. It uses a special bit encoding for efficient arithmetic with vectors over $\mathbb F_3$. On my MacBook, it takes half a minute to test a candidate with $31$ weighings and two ...


1

The problem states that "Given that a maximum of 3 substitutes may be used". This means that from your $2*5*5*3$ you need to subtract the number of possible teams with all 4 substitutes used. If all 4 substitutes are used, there are 4 ways to choose the other 3 defenders out of 4 non-substitutes, 4 ways to choose the other 3 midfielders out of the 4 ...


1

You can also use Inclusion–exclusion principle. Without the restriction $x_i\neq 3$ you have $$\binom{10+5-1}{10}$$ solutions. Now you need to check how many bad cases you have. Denote the set of all solutions with $x_i=3$ by $A_i$. Your bad cases are $$A_1\cup A_2\cup A_3\cup A_4\cup A_5.$$ Can you take it from here?


1

Let's begin by rewriting the formula with a shift from $n$ and $m$ to $n+1$ and $m+1$, so that the expression to prove is $${n\choose m} = {n+1\choose m+1}-{n+1\choose m+2}+{n+1\choose m+3}-\cdots+(-1)^{n-m}{n+1\choose n+1}$$ Now picture a class with $n$ students and a teacher. Each term on the right is of the form ${n+1\choose k}$, which counts the ...


1

Let $v_1,\ldots,v_n$ be the variables and $\phi(v_1,\ldots,v_n)$ an expression in these using only $\land$ and $\lor$ as connectives. Then we can rewrite this as $$\phi(v_1,\ldots,v_n)\iff v_n\land\phi_1(v_1,\ldots,v_{n-1})\lor \phi_2(v_1,\ldots,v_{n-1})$$ so that we can represent an expression in $n$ variables as a pair of expressions in $n-1$ variables. ...


1

You are really asking how many different boolean functions of $n$ variables can be constructed using $\land$ and $\lor$. Assuming you don't allow empty expressions (always true or always false), this is OEIS sequence A007153.


1

Going north at the first step, there is 9 possible paths NSNS, NSEW, NSSN, NSWE, NEWS, NESW, NWES, NWSE, NNSS So in total there is 4*9 = 36 possible paths to get back at the origin after 4 hop


1

I can get rid of the explicit appeal to probability by showing combinatorially that $f\upharpoonright\big(\Bbb Q\cap(0,1]\big)$ is monotone non-decreasing and then extending the result to $f\upharpoonright[0,1]$ by continuity. Note, though, that at bottom it’s really the same basic argument. Let $c$ be an integer greater than $1$, and let $g\le c$ be a ...


1

I don't know if this counts as an elegant solution in your book, but I think it's cute. Let's say the "frequency state" of a deck is the number of cards of each face value remaining. A full deck, for example, has the frequency state "4 aces, 4 twos, 4 threes...," while an empty deck has the frequency state "0 aces, 0 twos, 0 threes...." There are $5^{13}$ ...


1

Each point has probability $1-(1-1/N)^N$ of being drawn. (This goes to $1-1/\mathrm e$ for $N\to\infty$.) Thus by linearity of expectation, the expected number of points drawn is $N\left(1-(1-1/N)^N\right)$.



Only top voted, non community-wiki answers of a minimum length are eligible