Tag Info

New answers tagged

1

If I understand correctly a set $S$ is of common representatives if every subset of $\{1,2\dots n\}$ that has $k$ elements has an element in common with $S$. A set $S$ is of common representatives if and only if $S$ has $n-k+1$ elements or more. How many elements have $n-k+1$ subsets? $\sum\limits_{j=n-k+1}^n\binom{n}{j}$. If you only want those of ...


0

You are counting twice some of the outcomes. When you said that you fix one dice in "2" and you count all possible outcomes of the two remaining dices, what happen if you get another "2"? As an example consider the following configuration: when you first fix "2" as the first outcome, you get $\color{blue}{2},2,3$. Now, when you moved the fixed "2" to the ...


2

The appropriate model has the five dice distinguishable. A more familiar example is tossing two coins. A model that treats two heads, two tails, and one of each as equally likely gives answers that do not match reality. There are thus $6^5$ equally likely outcomes. We now need to count the favourables. We divide into cases. (i) All dice show the same ...


0

The 252 options are not equally likely. One option has all dice rolling 1 - the probability is $(1/6)^5$. Another option has one 1, one 2, one 3, one 4 and one 5. But there are 120 ways this can happen, from 12345, 12354, 12435 and so on, depending on the value of die 1, which has 5 choices, and so on. So the probability of getting all numbers 1 to 5 is ...


0

Each boy should get G number of candies and each girl should get B number of candies. This would ensure that sum of the candies received by boys and girls is equal.


0

Hint: If you had a function $c(m,x,t)$ which described the number of ways of distributing $m$ candies among $x$ people so nobody received more than $t$ (but they could receive zero) then the answer would be $$\sum_{m=\max(B,G)}^{N\min(B,G)}\; c(m-B,B,N-1)c(m-G,G,N-1)$$ It is possible to find a recurrence for $c(m,x,t)$, but it is slower than similar ...


3

We need to choose a non-empty subset $S_1$ from $\{a,\ldots,z\}$, a non-empty subset $S_2$ from $\{A,\ldots,Z\}$ and a non-empty subset $S_3$ from $\{0,\ldots,9\}$. Each combination of those subsets will give a unique (for that day, as order and repetition are not counted) different and valid password. So I get $(2^{26}-1)(2^{26}-1)(2^{10}-1)$ as the ...


3

There are $2^{26}-1$ options for capitals, $2^{26}-1$ options for lower-case and $2^{10}-1$ options for numbers. Multiply them together.


2

Generalization: any number of $1$s and $-1$s are written in a circle in any order, and the same steps are performed. We claim that the number of positive numbers written down has the same parity as the number of pairs of consecutive $1$s in the original circle. (For example, if there are four $1$s in a row flanked by $-1$s, that counts as three pairs of ...


0

An upper bound for $m$ is $3n-3$. Let $A=\{k+1,k+2,k+3\dots k+n\}$, $B$ is what is required-$\{k+1,k+2,k+3\dots k+n,2k+3,2k+4,2k+5\dots 2k+2n-1\}$ We need to make $k$ large enough that $4k+7 \gt 2k+2n-1$ or $k \gt n-4$


1

If $A$ is such a subset of $S_1 \cup \dotsb \cup S_t$, then $|A\cap S_i|$ is zero or one. If it is one, how many possibilities for $A\cap S_i$ are there? And does $S_i$'s contribution to $A$ affect $S_j$'s, for $j \ne i$? Edit: I am suggesting the following bijection. Letting $\binom{S}{k}$ denote the set of all size-$k$ subsets of some set $S$, we have ...


2

For each $S_i$, there are $a_i + 1$ actions that we can take: we can choose exactly one of the $a_i$ elements in $S_i$, or we can choose no elements at all. Making this choice for each $S_i$ will yield a unique subset of $S_1 \cup \cdots \cup S_t$ with the desired property. Thus, there are exactly $(a_1 + 1) \cdots (a_t + 1)$ such subsets. You could also ...


0

I'm doing a bad job of writing this out but I will try one more time. Ok so a regular problem you have 20 teams and you want to see how many non repeating combinations of 5 you can make so you would simply do 20! over 5!(20-5)! and the answer would be 15,504. Now what is different about what I am asking from this problem above is that once I chose my first ...


0

The probability that Betsy wins at attempt #$1$ is $\frac25$ The probability that Betsy wins at attempt #$2$ is $\frac35\cdot\frac35\cdot\frac25$ The probability that Betsy wins at attempt #$n$ is $(\frac35)^{2n}\cdot\frac25$ The probability that Betsy wins at some point is $\sum\limits_{n=0}^{\infty}(\frac35)^{2n}\cdot\frac25$ ...


0

I always try to promote the Polya Enumeration Theorem because it has many applications from simple to very sophisticated, and with this in mind I would like to apply it here. Once you have placed the three white flowers there are three slots for the $6m$ red ones, with every slot holding some number of red flowers including the case of zero red flowers. The ...


1

The Betsy wins under these outcomes. $T,\space HHT,\space HHHHT ,\space HHHHHHT$ etc. Those chances are $(\frac{2}{5}), (\frac{3}{5})(\frac{3}{5})(\frac{2}{5}), (\frac{3}{5})(\frac{3}{5})(\frac{3}{5})(\frac{3}{5})(\frac{2}{5})$ So you can set that up as a summation that is a geometric decreasing summation that is solvable. That geometric series comes to ...


1

Let $p$ be the probability that Betsy wins the game. We check some cases. If Betsy flips tails on her first move, then she wins and the game ends; this happens with probability $2/5$. Otherwise, Katie gets a chance to play; this happens with probability $3/5$. If Katie gets a chance to play, she wins with probability $2/5$, or resets the game with ...


2

We solve a simpler problem first. How many ways are there to arrange $n$ objects so that $k$ are visible when seen from the left? Denote this number by $f_k(n)$, then clearly $f_k(k)=1$ and $f_1(n)=(n-1)!$ since exactly one of the objects can be covered. After this we obtain $f_{k+1}(n+1)=f_k(n)+(n)f_{k+1}(n)$. To see this take a configuration with $n+1$ ...


0

If I am understanding your question correctly, you wish to take $2n$ teams, pair them up, and from among the winners pick some subset of the winners for some special reason such as playing in a charity event. By means of a small example: 2 games, 4 teams ($ABCD$). I expect you are interested in not only which two teams are the winners, but also who it is ...


2

Let me see if I get this straight. There are $20$ teams arranged in $10$ pairs. If team $i$ is paired with team $j$, then the two teams are playing a game with each other, and clearly, only one will win. You want to choose $5$ out of the $20$ original teams in the tournament that will win. You are interested in picking $5$ teams in the beginning of the ...


0

Just for the record, the first step can be in any of four directions, but subsequent steps cannot reverse the previous step (and may not be able to take some other steps). So, ignoring the bracketed text, there is an upper bound of $4 \cdot 3^{k-1}$. Taking account of the bracketed text, the number of paths of length $k$, for small $k$ starting with $k=0$, ...


2

The proof shall be by strong induction over the number of elements of $A$. So we assume it has been proven for sets with $n$ elements or less. now notice if we can prove it when the gcd of all the $n$ integers is $1$ we can use this to prove it when the numbers are not relatively prime by dividing all the numbers by the gcd, producing the appropriate ...


0

Every variety of coffee has 7 possible combinations, so there are 7 possible combinations per variety. There are 400 varieties, for a grand total of 7*400=2800 possible combinations.


0

First you choose $10$ teams out of $20$ to play each other, and then you multiply that with the number of ways you can choose $5$ teams out of $10$ as winners (the actual games are really irrelevant when you are looking at all the possible outcomes).


0

Imagine you wanted to list out all of the combinations. You want to make sure that you don't leave anything out, so you decide to do it in a systematic way by alphabetizing the type of coffee and the methods of preparation. Then you start listing: Aardvark Coffee, black Aardvark Coffee, cream only ... (4 more ways, and then) ... Aardvark Coffee, sugar only ...


0

Yes you are mistaken.Here you are not choosing n and k.It is like each variety of coffee (400) multiplied by 7 as all varieties of coffee are included.Combinations are not involved here in this case. So your answer will be 2800.


1

You can choose one of the $400$ varieties of coffee, and then independent from that you choose one of $7$ ways to prepare it. Hence the total number is $7 \times 400 = 2800$.


1

The spaces in red can be filled arbitrarily and it is still possible, I recommend you fill them with zeros.(I assume we use PEMDAS). At the end I ended up having to use some of the red spots to fix stuff, the top left corner was really usefull because the 332 becomes a zero for that row.


1

My answer would be $\frac{1}{3}\left(\binom{6m+2}{2}-1\right)+1$. $\binom{6m+2}{2}$ is the number of ways of writing $6m$ as the sum of three non-negative integers. We count the one case where all the values are the same seperately. That yields one garland. The other cases, the equations: $$6m=a+b+c=b+c+a=c+a+b$$ are all the same garland, so we have to ...


1

First I will dramatically overcount. Then I will overcompensate for my overcounting. Then I will compensate for my overcompensation to reach the final answer. Imagine the garland as a fixed circle, with a total of $3+6m$ positions for flowers. Then the number of possible garlands is simply the number of ways to choose the $3$ positions of the white ...


1

How many positive or nonzero integers p,q,r such that $p+q+r=24$ How many boxes of a dozen donuts(ice cream cones of 3 scoops) can be made with 5 varieties


1

Suppose $S_1,\ldots,S_k$ is such a partition. For each $i$, since $\bigcup S_i \neq A$, there is some element $\alpha_i$ that all sets in $S_i$ miss. Consider now the subset $T = \{\alpha_1,\ldots,\alpha_k\}$, and an arbitrary $U \supseteq T$ of size $k$. None of the families $S_i$ contain $U$, hence $S_1,\ldots,S_k$ is not a partition.


1

While your linear program is a valid formulation of the max flow problem, there is another formulation which makes it easier to identify the dual as the min cut problem. Let $(G,u,s,t)$ be a network with capacities $u: E(G) \rightarrow \mathbf{R}^+$, source vertex $s$ and sink vertex $t$. Let $P$ be the set of all simple $(s,t)$-paths in $G$. Suppose we ...


2

The summand, being a product of a binomial coefficient and something to the power of the iterand, looks like a hypergeometric function. In fact, symbolic algebra reveals that it is equal to $$ \left(1-\alpha\right)^{-n-1}-\alpha^{K+1}\binom{K+n+1}{K+1}{}_{2}F_{1}\left(1,K+n+2;K+2;\alpha\right). $$ Naturally, the trouble term is the hypergeometric ...


0

If your graph has $4$ edges, it must be a tree (a tree is a graph with no cycles). To see this, notice that if it had a $5$-cycle it would have $5$ edges, if it had a $4$-cycle it would have no edge connecting to the vertex outside the cycle, and if it had a $3$-cycle it would be disconnected, either because the $4$th edge connects the two other vertices and ...


0

The diagram would be like For an edge to be placed remember that you must choose $2$ vertices and be careful about bijection, by that i mean that if you do not label the vertices this two graphs (see below) are identical. Edit: As commented, because they are just a few, you can iterate all the ways (without order i.e. $2+2+2+1+1=2+1+2+2+1=\ldots ...


0

For $4$ edges: $${\rm X}\qquad {\rm W}\qquad \vdash$$


2

Edit: Due to Brian's comment, I corrected my answer. Suppose we select $c$ groups, and index them $1$ throught $c$. Let $A_i$ be the collection of sets taken from these groups, of size $r$ not containing an element from the $i$-th group. Then we want to find: $$|A_1^C\cap\cdots\cap A_c^C|=|(A_1\cup\cdots\cup A_c)^C|=\binom{cn}{r}-|A_1\cup\cdots\cup A_c|$$ ...


2

Several commenters say you’ve misquoted a contest problem. But regardless, you asked a question that has an answer, and the answer is no. Call the bits of the original sequence $b_i$, so the original word is $b_1b_2\dots b_{2015}$. A transposition $b_i\leftrightarrow b_j$ turns the sequence into the sequence $b_{\tau(1)}b_{\tau(2)}\dots b_{{\tau(2015)}}$, ...


2

Assume that the bits are given to you already sorted (This problem is not harder). label the bits $b_1,b_2\dots b_{2015}$ where $b_1\leq b_2\dots \leq b_{2015}$ So that the sequence is $b_1b_2\dots b_{2015}$ To make a move the mathematician must select position $A$ and position $B$,so that if $A$ is $1$ and $B$ is zero they swap, and nothing happens ...


12

For your question, the answer is no. The output string is a known permutation of the input string. If we could say two given bits were equal at the end, we could reverse the permutation and say two given bits were equal at the beginning, which we cannot.


7

You have translated the problem incorrectly. If A has an electron and B does not, then the electron jumps from A to B. This is completely different from just swapping two bits! The swap only happens when Bit A is 1, and bit B is 0, and you can designate which bit is A and which bit is B. For that, seems like a bubble sort type of approach will do (just ...


0

Wonder why nobody answered but the result is $$ \binom{x_2}{{1\over2}(x_2+k_1)}-\binom{x_2}{{1\over2}(x_2-k_1+2k_2)}, $$ where $x_2=2n$ but in this form $x_2$ can be odd too. It is an equivalent to the Bertrand's ballot problem -- just offset to the lattice origin.


0

A small contribution, in addition to the excellent answers already posted above. $$\begin{align} \binom n2 + \binom {n-1}2 &=\binom n2 + \frac{n-2}{n}\binom n2\\ &=\left(1+\frac{n-2}n\right)\binom n2\\ &=\frac{2(n-1)}n \cdot\frac{n(n-1)}2\\ &=(n-1)^2\qquad \blacksquare \end{align}$$


0

$$\large\begin{align} \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} &=\frac 1{2^{k-1}}\sum_{j=k}^n \binom jk\\ &=\frac 1{2^{k-1}}\binom{n+1}{k+1}\qquad \blacksquare \end{align}$$ NB - the summation can be taken from $j=k$ instead of from $j=0$ because $\binom jk=0$ for $j<k$.


1

Note (added later): I just discovered that I have essentially reproduced Henning Makholm's solution at the site he linked to in his comment, all the way down to the colors red and green. I'm leaving this answer up for convenience, at least for now. I swear I didn't peek before I posted! End of note. Here's a protocol for assigning Secret Santas that I ...


0

If every instance of problem $A$ is polynomial-time reducible to some instance of problem $B$, that means that problem $B$ is more general (and thus harder) than problem $A$. This is the intuitive idea between polynomial-time reductions and NP-complete proofs. As such, reducing a given problem to a known NP-hard problem does not show that the original ...


0

We will stick to the hypergraph iterpretation of the problem. Let $\xi_i$ - indicator random variable. $$\xi_i = \begin{cases} 1, & \text{i-th hyperedge contains < s colours}\\ 0, & otherwise \end{cases}$$ Then, $\cup_{i=1}^m \xi_i$ is a variable which describe chance of least one hyper edge to have $< s$ colours and ...


0

Pick first $n-l$ items without any restriction in $n-l+k-1 \choose k-1$ ways and then choose remaining $l$ elements each from a different category in $k \choose l $ ways. Thus , the answer is ${n-l+k-1 \choose k-1}*{k \choose l }$.


2

Hint: Think every relation as a binary square matrix of size 4 whose rows and columns are marked with characters $a,b,c,d$. If $a$-th row and $c$-th column is marked 1 then $(a,b) \in R$ otherwise not. Try to observe the properties of such a matrix if $R$ is reflexive, symmetric or antisymmetric .



Top 50 recent answers are included