Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Tag Info

Hot answers tagged combinatorics

197

First you have to draw the petals. There are $4!=24$ ways to choose the order of the petals and $2^4=16$ ways to choose the direction you go around each petal. Then you go down the stem to the leaves. There are $2! \cdot 2^2=8$ ways to draw the leaves. Finally you draw the lower stem. $24 \cdot 16 \cdot 8=3072$

176

The question is very easy to answer without computing probabilities. Every combination with six different numbers contains exactly one six. There are then additional combinations which contain exactly one six - e.g. $111116$. So the probability of exactly one six is greater.

132

If you add up the percentages, they come out to $300\%$. This means that the average number of beverages per person is $3$. No one drinks more than that, so no one can drink less than that, either. Since everyone drinks exactly three beverages, everyone has exactly one beverage that they don't drink. So no one doesn't drink both whiskey and gin, i.e. ...

115

$$\frac{(2n)!}{n! 2^{n}} = \frac{\prod\limits_{k=1}^{2n} k}{\prod\limits_{k=1}^{n} (2k)} = \prod_{k=1}^{n} (2k-1) \in \Bbb{Z}.$$

114

Here's an argument which extends to $n$ real numbers quite nicely! We can start by noting that $$x_1 (x_2x_3x_4x_5x_6) = x_1^2$$ And by commutativity, we get $x_i^2 = x_j^2$ which implies that all the magnitudes are equal. Now if $L$ is the magnitude, we also must have $L = L^5$, and from this we conclude that $L=0$ or $1$. Now we just have to go through ...

113

At the beginning you could go 8 different ways, then you could go 6 different ways, then you could go 4 and 2 different ways but in the down of the picture you could go at first 4 different ways and 2 at the end. $8\cdot6\cdot4\cdot2\cdot4\cdot2 = 3072$

109

This is impossible. At most one of the integers can be divisible by $19$. If there is such an integer, then one group will contain it and the other one will not. The first product is then divisible by $19$ whereas the second is not (since $19$ is prime) --- a contradiction. So if this possible, the remainders of the numbers after division by $19$ must be ...

104

No, it is not. If we assume that $P_1,P_2,\ldots,P_{26}$ are $26$ distinct points inside the given rectangle, such that $d(P_i,P_j)\geq 5\,cm$ for any $i\neq j$, we may consider $\Gamma_1,\Gamma_2,\ldots,\Gamma_{26}$ as the circles centered at $P_1,P_2,\ldots,P_{26}$ with radius $2.5\,cm$. We have that such circles are disjoint and fit inside a $25\,cm \... 103 Let's work with the lowest four numbers instead of the other suggestions. Supposing there is a counterexample, then the lowest four must add to at least$51$(else the highest three add to$50$or more). Since$14+13+12+11=50$the lowest four numbers would have to include one number at least equal to$15$to get a total as big as$51$. Then the greatest ... 99 If everyone knows everyone, then you are done. Otherwise choose two people, A and B say, who don't know each other. These two people are part of$23$triples. In each of these triples, either A knows the third person, or B knows the third person. Thus one of A or B knows (at least)$12$people. 97 Jack D'Aurizio's answer is nice, but I think the following is probably the solution intended by whoever posed the puzzle: Note that$26=5^2+1$. So perhaps we can divide our$20\times15$rectangle into$5^2$pieces, apply the pigeonhole principle, and be done. That would require that our pieces each have diameter at most 5. Well, what's the most obvious way ... 96 Here is a way of rewriting your original argument that should convince your friend: Let$A,B,C,D\subset\{1,2,\dots,100\}$be the four sets, with$|A|=85$,$|B|=80$,$|C|=75$,$|D|=70$. Then we want the minimum size of$A\cap B\cap C\cap D$. Combining the fact that $$|A\cap B\cap C\cap D|=100-|A^c\cup B^c\cup C^c\cup D^c|$$ where$A^c$refers to$A$... 94 Case I: If$p+q$is odd, then the knight's square changes colour after each move, so we are done. Case II: If$p$and$q$are both odd, then the$x$-coordinate changes by an odd number after every move, so it is odd after an odd number of moves. So the$x$-coordinate can be zero only after an even number of moves. Case III: If$p$and$q$are both even, we ... 94 When you phrase it in plain English, the answer isn't necessarily totally clear. It might seem reasonable to argue that there are$0$ways of choosing$0$things from$n$, since choosing$0$things isn't really a choice. However, when mathematicians talk about "the number of ways to choose$0$from$n$," we mean something a bit more specific. A few ways of ... 92 Combinatorics certainly can be rigourous but is not usually presented that way because doing it that way is: longer (obviously) less clear because the rigour can obscure the key ideas boring because once you know intuitively that something works you lose interest in a rigourous argument For example, compare the following two proofs that the binomial ... 89 If you don't add 1, then you're saying "take the first 201 customers, but then exclude the first 149 ones." That would give you the number of customers in the list from 150-201. The way I think of it is this: The number of customers from #149 to #201 is$201-148=53$, because it's the first 148 customers we're trying to exclude. Does that help? 86 So many long answers! But really it's quite simple. Mathematically, the expected number of brothers is the same for men and women. In real life, we can expect men to have slightly more brothers than women. Mathematically: Assume, as the question puts it, that "in each family, the sex of each member is independent of the sexes of the other members". This ... 79 Edit, 5/24/16: After some thought I don't particularly like this answer anymore; please take a look at my second answer below instead. Here's a simple version of the question. Suppose there is exactly one family which has$n$children, of which$k$are male with some probability$p_k$. When this happens, the men each have$k-1$brothers, while the women ... 78 It depends on how they're verified. If you provide both username and password, and the computer tells you "yes" or "no", then there are$62^{100}$possible combinations: each of the$62^{50}$possible usernames can be paired with each of the$62^{50}$possible passwords to get$62^{50} * 62^{50} = 62^{100}$possible username/password combinations. If, on ... 69 Given a Fibonacci number$n$, let$m$be the next Fibonacci number. The Fibonacci sequence has the property that for any three consecutive elements$r,s,t$, we have$rt=s^2\pm 1$(proof is by induction, which you might like to try$-$the choice of signs alternates). And we know that the previous Fibonacci number is$m-n$. So we have $$m(m-n)=n^2\pm 1$$ This ... 66 For a short analogy: I was born in 1986, so I am 27 now. But I have lived in four different decades (the 80s, the 90s, the 00s and the 10s). This is not the same as forty years. In the same way, you worked in four different years, but not for four years. 63 We are given the fact that there are$12$questions, that$6$have the correct answer "yes" and$6$have the correct answer "no." There are$\binom{12}{6} = 924$different sequences of$6$"yes" answers and$6$"no" answers. If we know nothing that will give us a better chance of answering any question correctly than sheer luck, the most reasonable ... 62 If you add up all the injuries, there is a total of 310 sustained. That means 100 soldiers lost 3 limbs, with 10 remaining injuries. Therefore, 10 soldiers must have sustained an additional injury, thus losing all 4 limbs. The manner in which you've argued your answer seems to me, logical, and correct. 61 Suppose you want to choose a subset. For each element, you have two choices: either you put it in your subset, or you don't; and these choices are all independent. Remark: this works also for the empty set. An empty set has exactly one subset, namely the empty set. And the fact that$2^0=1$reflects the fact that there is only one way to pick no elements at ... 61 In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.) However, a modification of your strategy (to choose the timeslots with the highest totals) ... 61 It is worth noting that to count properly with the second approach, you would have to write $$3 \cdot 5 \cdot 21^2 + 3 \cdot 5^2 \cdot 21 + 5^3 = 8315.$$ The first term counts all cases where there is exactly one vowel, and there are three positions for the location of this vowel. The second term counts all cases where there are exactly two vowels, and ... 60 This is an example of the so-called fence post problem. It goes like this: Suppose you are building a fence with rails suspended between fence posts. The fence might look like this: $$|=|=|=|=|=|$$ where$|$denotes a post, and$=$denotes a rail. If each rail is 10 feet long, how many posts do you need to make a fence 50 feet long? The answer is that ... 60 TLDR:$a_n=\log_2(1+1/n)$works, and is the only smooth solution. This problem hints at a deeper mathematical question, as follows. As has been observed by Pongrácz, there is a great deal of possible variation in solutions to this problem. I would like to find a "best" solution, where the sequence of pieces is somehow as evenly distributed as possible, ... 58 Obviously if$m<n$, there are no function from$\Bbb A$onto$\Bbb B$, so assume that$m\ge n$. We’ll use an inclusion-exclusion argument. There are$n^m$functions of all kinds from$\Bbb A$to$\Bbb B$. If$b\in\Bbb B$, there are$(n-1)^m$functions from$\Bbb A$to$\Bbb B\setminus\{b\}$, i.e., functions whose ranges do not include$b\$. We need to ...

58

I think I will argue that Cut the Knot is correct. The distribution of sizes of families is not specified. Let's do some examples. Suppose all families have size 1. Then every boy has no brothers and every girl has no brothers. (So we certainly cannot conclude girls have more brothers than boys independently of the distribution of family sizes.) ...

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