130

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. ...


113

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 ...


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 ...


93

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 ...


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

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, ...


56

Perhaps a little duality argument can help to provide some intuition. Given a bag of $n$ balls, consider these two tasks: choose $k$ balls inside the bag, and remove them from the bag choose $n-k$ balls inside the bag, and remove all the others from the bag Intuition suggests that these tasks are essentially the same: choosing which $k$ balls we remove ...


52

Look at what the operations $+$ and $\times$ do to the binary expansion of a number: $\times$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged; if the final digit is $0$, then $+$ increases the number of $1$'s by one, but doesn't change the length; if the final digit is $1$, then $+$ doesn't increase the total ...


51

$8$ people. Each experiences handshakes with $6$ people. There are $6\times 8=48$ experiences of handshakes. Each handshake is experienced by two people so there $48$ experiences means $48\div 2=24$ handshakes.


48

Claim: if $a_1,...,a_n$ are the $n$ numbers on the board then after n steps we shall be left with $(1+a_1)...(1+a_n)-1$. Proof: induct on $n$. Case $n=1$ is true, so assume the proposition holds for a fixed $n$ and any $a_1$,...$a_n$. Consider now $n+1$ numbers $a_1$,...,$a_{n+1}$. Suppose that at the first step we choose $a_1$ and $a_2$. We will be left ...


45

Another way to think of Sorin's observation, without appealing to induction explicitly: Suppose your original numbers (both the original 155 numbers and later results) are written in white chalk. Now above each white number write that number plus one, in red chalk. Write new red companions to each new white number, and erase the red numbers when their white ...


42

Your identity is correct. I don't know a reference offhand, but here is a proof. The right side, $\binom{N+2j+1}{2j+1}$, is the number of bitstrings of length $N+2j+1$ consisting of $N$ zeroes and $2j+1$ ones. The sum on the left counts the same set of bitstrings. Namely, for $0\le k\le N$, the term $\binom{k+j}j\binom{N-k+j}j$ is the number of those ...


37

YES, it is possible! You mustn't cut a piece in half, because eventually you have to cut one of them, and then you violate the requirement. So in fact, you must never have two equal parts. Make the first cut so that the condition is not violated, say $60:40$. From now on, assume that the ratio of biggest over smallest is strictly less than $2$ in a ...


36

If you're looking for something like a set which may have repeated elements, standard terms are multiset or bag. See multiset on wikipedia.


35

You can imagine doing this as writing a sequence, say $$3453228156467781$$ What does it mean? It means first put sock on leg $3$ and and on 4-th move put shoe on leg $3$ and so on. So for each leg you must choose a pair in this sequence. On smaller number in this pair put a sock and the other shoe. So we have $${16\choose 2}{14\choose 2}....{4\choose 2}{2\...


34

In combinatorics answering “and” style questions is easy because it is a multiplication. This is easy since you can remove common factors between denominators and numerators, and use the binomial/choice function. Also any time a 1 or 0 comes up the operation becomes trivial. However asking "or" style questions is difficult since you have to add the numbers ...


33

Yes, there is enough information. Clearly the overlap between whiskey drinkers and gin drinkers is at least $30\%$, being exactly $30\%$ iff $40\%$ drink whiskey but not gin, and $30\%$ drink gin but not whiskey. Similarly at least $70\%$ drink both tea and coffee. Since nobody drinks all four, the number who drink both whiskey and gin is exactly $30\%$, and ...


33

When wondering why (or if) something is wrong, a general approach is to make the numbers as small as you can while still maintaining the error but so that you can brute-force the answer. So let's try an alphabet with one vowel A and one consonant B. (Note that this way you can never prove that something is correct, but it's a valuable tool for finding some ...


31

Well, if there are an even number of $1$'s and $-1$'s, then the property holds, so that's $$\binom{6}{0}+ \binom{6}{2}+ \binom{6}{4}+ \binom{6}{6}=32$$ And then there’s the case that they’re all zero. Thus, there are $33$ total cases.


31

Suppose the spouses were allowed to shake each other's hands. That would give you $\binom{8}{2} = 28$ handshakes. Since there are four couples, four of these handshakes are illegal. We can remove those to get the $24$ legal handshakes.


30

Take the number of all three letter words, $26^3$, and subtract from it the number that have only consonants, $21^3$. Your second method does not address all possible sequences of vowels, such as vowel-consonant-vowel or vowel-vowel-consonant or consonant-vowel-vowel...


28

$$\color{red}{\binom {20}{19}} +\color{orange}{\binom {19}{16} +{\binom {16}{14}}}+ \color{green}{\binom {14}{12} +\binom {12}{7}}+ \color{blue}{\binom {7}{6}+ \binom {6}{5}}+ \color{purple}{\binom {5}{3}+\binom {3}{1}}+ \color{magenta}{\binom {1}{0}} =\color{red}{2019}$$


27

Let $x$ be the 4-digit number ending in digit not equal to 9 with the sum of digits equal to $s$. If you increase the last digit by one, the number becomes $x+1$ and the sum of digits becomes $s+1$. You can easily prove that: $$\frac xs>\frac{x+1}{s+1}$$ This is true because $x>s$. So to reduce the ratio as much as possible, the last digit has to be ...


26

Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not ...


26

If the maximum number of fish caught is $m$, then the total number of fish caught is no more than $m+(m-1)+...+(m-6)$. So there is one fisherman that caught at least 18 fish. Repeat this process for the second and third highest number of fish caught and you should be good. I should add that this is a common proof technique in combinatorics and graph theory. ...


26

The Pigeonhole Principle is really the statement that for finite sets $S,T$ with $|S|>|T|$, there is no injective mapping from $S$ to $T$. Proceed by induction on $|T|$. For $|T|=1$, $|S|\ge 2$ by hypothesis; there is one map from $S$ to $T$ and it is not one-to-one. Now suppose true for sets with $n$ elements and that $|T|=n+1$ (and $|S|>n+1$), and ...


25

Hint: consider what "Nobody drinks all four beverages" means in terms of the four groups People who don't drink tea People who don't drink coffee People who don't drink whiskey People who don't drink gin and then see how big each of those groups are.


25

Use symmetry. Let us write $P_1$ as the probability that the thirteenth spade comes before the thirteenth diamond, and let $P_2$ be the probability that the thirteenth diamond comes before the thirteenth spade. Clearly, one of these must occur, and they can't both occur. Thus, we have that $$P_1+P_2=1$$ Furthermore, since suits are arbitrary, we may ...


24

The question is rather badly posed. "The first white ball" sounds as if it refers to the first white ball drawn, but apparently it's intended to refer to the white ball with the number $1$. There's indeed a much simpler way to show that the probability of drawing the white ball with the number $1$ before all black balls is $\frac1{21}$. Consider the $21$ ...


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