# Tag Info

18

Let $b$ be the number of boys, and $g$ the number of girls. For any boy $B$ and girl $G$ who know each other, write on a slip of paper "$B$ and $G$ know each other." We count the number of slips of paper in two different ways. Since every boy knows $r$ girls, there are $br$ slips of paper. Since every girl knows $r$ boys, there are $gr$ slips of paper. ...

8

Code heads as 1 and tails as 0, and the problem can be phrased in the following way: Flip a fair coin until you have exactly twice as many heads as tails, and then stop. The value of $|S_n|$ is the number of such sequences of coin flips that have length exactly $3n$. For this rephrased version, I asked the same question as the OP a couple of years ago on ...

7

Yes, you are correct on the first question. For the second, there are four positions, the first of which has $9$ possible values, (can't be zero), then the second position has 9 possible values it can take on (subtracting 1 from 10 possible values since it can't be the same number as the first position. Etc... $$9 \cdot 9\cdot 8 \cdot 7 = 4536$$

7

Since $0\leqslant \sin t\leqslant 1$ over $[0,\pi/2]$ we have that $$\int_0^{\pi/2}\sin^{2n+1}t dt\leqslant \int_0^{\pi/2}\sin^{2n}tdt\leqslant \int_0^{\pi/2}\sin^{2n-1}t dt$$ Now, it is not hard to show that if $I_k= \displaystyle\int_0^{\pi/2}\sin^{k}t$ then $I_k=\dfrac{k-1}{k}I_{k-2}$, by integrating by parts. Using $I_1=1$ and $I_0=\dfrac{\pi}2$, we ...

5

Your particular example of information being lost in multiplication or division is really the reason one studies ideals in ring theory, normal subgroups in group theory, and kernels in general. But I think prime ideals explain it best. The prime factorization of a number represents how much information was lost in creating it. A prime number only has one ...

5

You are asking, if I understand right, for how much information is lost during the mapping from two elements to another symbol indicating the relation. In your example, function division maps $a,b$ to $\frac ab$, which you choose $c$ to represent the relation of $a,b$. Unfortunately, we can say nothing on loss of information for that because essentially ...

4

This post illustrates why $\text{Tr}(A^k)$ gives the number of cycles of length $k$ in the graph with adjacency matrix $A$. We have to be careful since a cycle is not the same thing as a polygon. For example, we can make a 4-cycle by moving between two nodes only: XYXY is a 4-cycle, but not a quadrilateral. For triangles it turns out that this is not a ...

4

For $n=5$: $$\underbrace{5,4,3,2,1},\underbrace{10,9,8,7,6},\underbrace{15,14,13,12,11},\underbrace{20,19,18,17,17},\underbrace{25,24,23,22,21}$$ Any subsequence of $6$ of these numbers must contain two numbers from the same block and two numbers from different blocks. Two numbers from the same block must appear in decreasing order, while two from ...

4

HINT: A tournament is acyclic if and only if it’s transitive, which in turn is the case if and only if the score sequence (sequence of out-degrees of the vertices) is $\langle n-1,n-2,\ldots,2,1,0\rangle$. In other words, there’s a perfect ranking of the $n$ players, with an absolute winner who can beat each of the others, a second-place finisher who can ...

4

The $k$-th term on the left hand side counts the number of permutations of $\{1,\ldots,n+1\}$ whose last non-fixed-point is $k+1$. We choose one of the first $k$ to put in position $k+1$, then order the rest of the first $k+1$ in the first $k$ positions in any way we like. The right hand side counts all nonidentity permutations of $\{1,\ldots,n+1\}$ (those ...

4

Your first calculation $(a)$ is correct. For $(b)$: First, let's ensure that we select $2$ from each state. Order of selection doesn't matter, so we can fill six seats on the committee, two from each state, in the following number of ways: $$C(6,2)\cdot C(7,2)\cdot C(8,2)$$ That gives us six of seven committee members, with a pool of $21 - 6 = 15$ folks ...

4

You have $9$ letters, so if all letters would be different, the answer would be: $9!$. However, you have $2$ letter A, $2$ letter O, $4$ letter P and $1$ letter N. For each group, the order is not important, so there are $2!$ possibilities to interchange the letters A, $4!$ for the P's, etc. So the answer is $$\frac{9!}{2!\cdot2!\cdot4!\cdot1!}.$$

4

The number of sequence elements $\lambda_j$ that are less than some $x$ is at least $(2\sqrt{x/3}-1)^3$, by considering $\alpha_1,\alpha_2,\alpha_3\in[-\lfloor\sqrt{x/3}\rfloor,\lfloor\sqrt{x/3}\rfloor]$. Therefore $\lambda_{\lceil(2\sqrt{x/3}-1)^3\rceil} \le x$, which implies that $\lambda_j \le Cj^{2/3}$ for some constant $C>0$.

3

Here's a solution that uses basic Markov chain theory. Let's make the state zero a reflecting boundary i.e, from zero you jump to one with probability one. This is now an irreducible Markov chain. Direct calculation shows that $\pi_n={n+1\over 2 e\, n!}$ for $n\geq 0$ defines the unique invariant probability measure for the chain. Therefore, by general ...

3

Note that the relationships across gender form a bipartite graph $G$ with subgraphs $A$ (vertices are girls) and $B$ (vertices are boys). The graph is regular, that is all vertices have the same degree $r:=\deg{v}$. However, we also note that for every edge incident on a vertex on $B$, the other end of the edge is incident on $A$, since $G$ is bipartite. ...

3

You need to count the number of ways Jill can give at most three apples to Jack. So we need to count the one way Jill can give no apples to Jack, add to that the number of ways she can give one apple to Jack, and then add to that the number of ways she can give two apples to Jack, and then add to all of that the number of ways she can give three apples to ...

3

Start with $n$ numbered white balls. How many ways are there to choose $k$ of the balls, put them in a box, throw away some subset of the balls in the box, and end up with a box containing $k$ balls? There are $2^k\binom{n}k$ ways to pick $k$ of the balls, put them in the box, and then choose a subset of them to throw away. Now we’ll subtract the ...

3

Start with a string of $n$ zeroes. You want to divide it into $k$ blocks, so you have to insert $k-1$ markers separating the blocks. You can insert these into any $k-1$ of the slots between adjacent zeroes, so there are $\binom{n-1}{k-1}$ ways to insert the markers and break up the zeroes into $k$ blocks. Now replace each marker with a $1$; that ensures that ...

3

Assuming a royal straight is any AKQJT and you want to exclude them, this is a good candidate for the inclusion-exclusion principle Count all the straights, deduct the royal straights, deduct the straight flushes, note that you have deducted the royal flushes (suited AKQJT) twice, so add them back in once

3

As noted in the comments, $0112=1011+2101$, so the span of $T$ is simply the span of the set $\{1011,2101\}$. It’s easy to check that neither of these vectors is a multiple of the other, so this set is linearly independent, and the span of $T$ is the set of all vectors $$a\cdot1011+b\cdot2101$$ such that $a,b\in\Bbb Z_3$. For most purposes that’s a ...

3

Think of $e^{x+x^2/2}$ as $e^x\cdot e^{x^2/2}$: the series is $$\left(\sum_{n\ge 0}\frac1{n!}\left(\frac{x^2}2\right)^n\right)\left(\sum_{n\ge 0}\frac{x^n}{n!}\right)=\left(\sum_{n\ge 0}\frac{x^{2n}}{2^nn!}\right)\left(\sum_{n\ge 0}\frac{x^n}{n!}\right)\;,$$ in which the $x^n$ term is \begin{align*} \sum_{k=0}^{\lfloor ...

2

As you pointed out, since the ant gets zapped if it reaches $y=14$ with $x<24$, or reaches $x=25$ with $y<13$, there's only one place it can safely be after $37$ steps: $(24, 13)$. Moreover, if it reaches that location, it's safe for all subsequent steps. So, there are $2^{37}$ equally probable ways to choose the first $37$ steps, of which exactly ...

2

In $G(n,m)$, each edge $e$ has absolute probability $p=m{n\choose 2}^{-1}$ to be chosen. But, conditionally on some other edges being chosen, the probability that $e$ is chosen decreases. An extreme case is to condition on the event that $m$ other edges are chosen, then the conditional probability that $e$ is chosen drops to $0$. Another take: in $G(n,m)$, ...

2

Hint: there are six classes of preferences: Those who prefer A (to both B and C) and prefer B to C. Those who prefer A (to both B and C) and prefer C to B. Those who prefer B (to both A and C) and prefer A to C. Those who prefer B (to both A and C) and prefer C to A. Those who prefer C (to both A and B) and prefer A to B. Those who prefer C (to both A and ...

2

There are six possible preference orders for the candidates: $d$: A>B>C $e$: A>C>B $f$: B>A>C $g$: B>C>A $h$: C>A>B $i$: C>B>A From this, $a = d + e + f$, $b = f + g + i$, and $c = e + h + i$. $a + b +c = d + 2e + 2f + g + h + 2i \le 2(d + e + f + g + h + i) = 2(\text{# of voters})$. In scenario (3), $a + b + c = 204\%$, which is impossible.

2

This question has a definite answer, which is to use the Polya Enumeration Theorem, which is more powerful than Burnside and includes it as a special case. It will produce a multivariate generating function for all distributions of colors, from which you may extract the desired coefficient for a given configuration. You compute the cycle index of the face ...

2

If you were to consider a graph where each student is a vertex, and an edge from $a$ to $b$ means "a is willing to live with b", you're looking for two vertices $x,y$ with an edge going in each direction (one from $x$ to $y$ and one from $y$ to $x$). There are $\binom{40}{2} < 40*20$ such pairs of vertices. Can you take it from there?

2

Your first calculation overcounts, and your second undercounts. A five-card hand with at least one card in each suit must have two cards in one suit and one card in each of the other three suits. There are $4$ ways to pick the suit with two cards. Once it’s been picked, there are $\binom{13}2$ ways to pick two cards from it and $13^3$ ways to pick one card ...

2

This is true by induction on $n$ using the recurrence $\displaystyle {n+1 \brace k} = {n \brace k-1} + k{n \brace k}$. For $k=2$: $\displaystyle {n+1 \brace 2} = {n\brace 1} + 2{n \brace 2} \geq 1 + 2\binom{n}{2} \geq \binom{n+1}{2}$ by induction. For $k=n$, $\displaystyle {n\brace n} = 1 = \binom{n}{n}$. For other $k$, \$\displaystyle {n+1 \brace k} = {n ...

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