Tag Info

Hot answers tagged

5

Suppose you describe the squares of the board $B$ using integer coordinates: $$ B = \{(x,y) \mid x,y \in \mathbb{N}\}. $$ Use the following map, which I will describe in steps: first map $$ (x,0),(x,1) \mapsto (x,0) \quad \forall x \geq 0; $$ this takes care of the first row, each square of which now has exactly $2$ frogs occupying it. Next map $$ ...


4

We are distributing $31$ identical candies among $5$ (non-identical) kids, with Kid $1$ getting at least $1$ candy, Kid $2$ getting at least $2$, and so on. Initially, give $0$ candies to Kid $1$, $1$ to Kid $2$, and so on up to $4$ to Kid $5$. That takes care of $10$ candies, leaving $21$. Then distribute the $21$ remaining candies among the kids, at ...


3

As ShreevatsaR pointed out it's sufficient to consider ordinary generating functions, since they already take into account that $3,4,3,4$ and $3,3,4,4$ are different. The first is coded as the coefficient of $x^3x^4x^3x^4$, while the second as the coefficient of $x^3x^3x^4x^4$ when considering the ogf $(x^1+\cdots+x^6)^4$. Therefore we get for the first ...


3

If no odd digits can be placed on odd places, you must fill all odd places with even digits. There are four odd places, and you've got four even digits ($2$, $2$, $4$, $4$), so they are just enough to fill the four odd slots. The number of ways to do so is $$n_{\text{odd places}} = \frac{4!}{2!\cdot 2!} = 6.$$ Now you have to fill the even places. Since ...


3

Your method is correct, there are 15170 solutions. It seems like your python script is doing something wrong at the end. I wrote a C++ program myself to confirm this: #include <stdio.h> int main() { int a,b,c,d,e,sum=0; for (a=0; a<10; a++) for (b=0; b<24; b++) for (c=0; c<24; c++) for (d=0; d<24; d++) for (e=0; ...


3

Differentiating the binomial expansion $$ (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k, $$ we obtain $$ n(1+x)^{n-1}=\sum_{k=0}^n k\binom{n}{k}x^{k-1} \quad\Longrightarrow\quad n2^{n-1}=\sum_{k=0}^n k\binom{n}{k} \tag{1} $$ and $$ n(n-1)(1+x)^{n-2}=\sum_{k=0}^n k(k-1)\binom{n}{k}x^{k-2} \Longrightarrow\ n(n-1)2^{n-2}=\sum_{k=0}^n k(k-1)\binom{n}{k}. \tag{2} $$ ...


3

It's easy to show that: $$\binom{n}{1}+\binom{n}{2}+\binom{n}{3}.....+\binom{n}{n} = 2^n$$ Using this, try to find the derivative of: $(1 + x)^n$ and write out the binomial expansion. Set $x = 1$ and you'll get: $$\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}.....n\binom{n}{n} = n*2^{n-1}$$


3

Consider permutations $w \in S_n$ and partition them according to the largest $k$ such that $w(k) \neq k$. (Note there is one permutation that is excluded from this partition, namely the identity permutation.) Let $A_k$ denote the above set of permutations. Then $w \in A_k$ is determined by choosing the value of $w(k)$, which must be one of the numbers ...


3

Here's a way to get the sum by obtaining the required generating function. As in my first answer, rewrite the sum as: $ \displaystyle \sum_{0 \le k \le n} \dfrac{(-1)^k }{n!\, 2^k}\dbinom{2\,k+1}{k}\, \dbinom{n}{n-k}\tag 1 $ Let $\displaystyle a_k=\dfrac{(-1)^k }{2^k}\dbinom{2\,k+1}{k} $ The generating function for $a_k$ is: $\displaystyle ...


3

The variance calculation is incorrect. Let random variables $X_1,X_2,X_3$ denote the results on the first roll, the second, and the third. The $X_i$ are independent. The variance of a sum of independent random variables is the sum of the variances. So our desired variance is $\text{Var}(X_1)$. To calculate the variance of $X_1$, we calculate ...


3

We find out how many $k\times k\times k$ cubes there are in the big cube. Put such a small cube at the bottom left-hand corner of the big cube. The bottom left-hand corner of the little cube can be put into $(n-k+1)\times(n-k+1)\times (n-k+1)$ positions. This is because that corner can be moved in any of the coordinate directions by any amount from $0$ to ...


3

The formula : $\vdash_T G_T \leftrightarrow \lnot \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ means : it is provable in $T$ the equivalence between the sentence $G_T$ and the sentence $\lnot \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ [see also this post]. Assume that we know what is a Formal system like First-order theory of ...


3

Are you allowed to use derivatives? From Wikipedia: "A twice differentiable function of one variable is convex on an interval if and only if its second derivative is non-negative there". Since the second derivative of $e^x$ is $e^x$, and $e^x > 0$ for all $x \in \Bbb R$, we have that $e^x$ is convex on any interval.


3

I'm not sure if your posted answer is correct, but here's one way to think about the problem. How many divisors are there where no prime occurs with maximal multiplicity? This is easy to compute as $\prod_m \alpha_m$ since you can choose exponents between $0$ and $\alpha_m-1$ for each prime divisor, each giving rise to a unique product for each choice. Then ...


2

We can assume $a_1 < a_2 < a_3 < \ldots <a_n$ without loss. Since $n\geq 3$, we have $a_n \geq 3$. Let us argue by induction on $m=a_n$. When $m=3$, we have $n=3, (a_1,a_2,a_3)=(1,2,3)$ and this case has already been treated by the OP. Now, suppose that $m>3$ and that the result is true for $m-1$. Let $a_1 < a_2 < a_3 < \ldots ...


2

Since the men need to be in asending order between themselves and they all have different heights, they can't swap position. Therefore it is only the location of men that is relevant. The same argument holds for women. So the problem comes down to align $m$ men and $w$ women. Note that once you know the position of, say, the women, then everything is fixed. ...


2

I think this suffices for $n=6$. Certainly not the most elegant solution, though. Proof of nonexistence for $n=6$. We shall use, as Will Jagy, the alphabet $X=\{a,b,c,d,e\}$. We shall call the desired family $S$ and the set of all the complements as $S'$. Clearly we cannot have more than one singleton, as if we did, say $\{a\}, \{b\}$, then ...


2

This is a rewording of a standard Stars and Bars problem. We have $n$ candies, and want to distribute them among $k$ kids, with every kid getting at least one candy. Or if you prefer equations to kids and candies, it is the number of solutions $(x_1,x_2,\dots,x_k)$ of the equation $x_1+x_2+\cdots+x_k=n$ in positive integers. The number of ways to do this ...


2

1) Divide five cases $\bullet \quad x_1=0, x_2\ge 1, x_3=0, x_4\ge 1, x_5\ge 0$ then $\quad 0+x_2+0+x_4+(x_5+1)=46\quad $ number of solutions as $\displaystyle {45\choose 2}=990$ $\bullet \quad x_1=0, x_2\ge 1, x_3\ge 1, x_4\ge 0, x_5\ge 0$ then $\quad 0+x_2+x_3+(x_4+1)+(x_5+1)=47\quad $ number of solutions as $\displaystyle {46\choose 3}=15180$ ...


2

Suppose you have a coin that has probability $p$ of coming up heads, and you toss it up to $m+1$ times, stopping when you see a tail. On the one hand, the probability that you saw a tail at all (before you ran out of tosses) is the sum over all the different ways in which this might happen. The probability of seeing a tail after $i$ heads is $p^i (1-p)$, ...


2

The easiest and most elegant way to find a formula for this is to show you an equivalent problem. This is the case of indistinguishable objects in distinguishable boxes. Rather than thinking that a Skittle is a particular color, let's have identical beads be placed in one of $5$ boxes, and depending on which box it is in determines its color of the Skittle. ...


2

This is a hypergeometric distribution, not a binomial distribution. So if you want no defective balls, see below. You choose $10$ working balls from the $25$ working balls, and no balls from the defective title. $$ \dfrac{ \binom{25}{10} * \binom{5}{0} }{ \binom{30}{10} }$$ For (b), just take $1 - P(X \leq 1)$. So how many ways do you get $0$ defective ...


2

A and C) If you have $n$ different mailboxes, let $x_i$ be the number of envelopes in the box $i$. The number of ways you can put $m$ identical envelopes in $n$ boxes is the number of solutions to following equation: $$ x_1+x_2+...+x_n=m $$ If $x_i>0$, the number of ways is $\binom{m-1}{n-1}$, otherwise if $x_i\geq 0$, the number of ways is ...


2

Your answer to C is wrong. First, you assumed that there's exactly one x and one y in the code, whereas the problem doesn't state so. Second, x can occur on every position in the code, same for y. For example, there are 26*26 codes where two first letters are "xy" and 26*26 codes where "xy" are the 3rd and 4th letters, respectively. Got A and B right.


2

We have by the upper summation formula for binomial coefficients: $$\sum_{i=2}^{n}\binom{i}{2}=\sum_{0\leq i \leq n}\binom{i}{2}=\binom{n+1}{3}=\frac{n(n-1)(n+1)}{6}$$ We can prove this identity fairly simply: $$\sum_{0\leq i \leq n}\binom{i}{m}=\sum_{0 \leq m+i \leq n}\binom{m+i}{m}=\sum_{0 \leq i \leq ...


2

Write out the terms individually: $$ \begin{align} \text{LHS} &= 1 + 3 + 6 + 10 + 15 + \cdots + \dfrac{n(n-1)}{2}\\ &= \sum_{i = 1}^{1}{i} + \sum_{i = 1}^{2}{i} + \cdots + \sum_{i = 1}^{n - 1}{i}\\ &= \sum_{i = 1}^{n - 1}{\sum_{j = 1}^{i}{i}}\\ &= \sum_{i = 1}^{n - 1}{\dfrac{i(i+1)}{2}}\\ &= \dfrac{(n + 1) n (n - 1)}{6} \end{align} $$


2

We only care about the last three digits obviously, so the possible sums of just those three die are $100a + 10b + c$, where $a$, $b$, and $c$ are all between $1$ and $6$, inclusive. We check the divisibility by taking this modulo $8$. If the result is equivalent to $0$, then it is divisible. Setting up the equivalence condition: $$ 100a+10b+c \equiv 0 ...


2

In a decagon, there are $10\choose2$ ways to pick pairs of vertices that are 1 side apart. Connecting these pairs gives pairs of parallel diagonals. But for each pair, only 5 of the other 9 pairs don't share a share a vertex or result in a diagonal that is just a side of the decagon, so there are $\frac59{10\choose2}$ ways here. Now we check pairs of ...


2

For the first case, you have 37 elements in all, but are excluding $z$, leaving 36. If both $x$ and $y$ are included, you get to choose only the other 34 elements, giving $2^{34}$ possible sets. If you decide to include $x$, by the same reasoning above you get $2^{35}$ subsets, if you include $y$ again $2^{35}$; but that counts the sets containing $x$ and ...


2

This problem has nothing to do with probability, but your idea of picking a king frog is useful. Starting with the king frog, enumerate both frogs and squares in a spiral (like the starting point for Ulam's spiral). Then simply have frogs 1 and 2 jump to square 1, frogs 3 and 4 jump to square 2, and so forth.



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