Hot answers tagged

43

Q: How do you avoid having three people with birthdays in the same month while making your group of people as large as possible? A: By having two in each month. That makes $24$ people. So in which month was the $25$th one born?


41

Your question is a straightforward application of the pigeonhole principle. In its simplest form, applied to the context of your question, the pigeonhole principle states that for $m = 12$ months, if there are $n \ge 13$ people in a group, then there is guaranteed to be a month in which at least two people's birthdays occur. This makes intuitive sense: if ...


12

A group of twenty-four people can fail to satisfy the request (how?). What if you ask another person to join the group?


3

Let the 21 numbers be $x_1<x_2<\ldots <x_{21}$. It is not possible to have $x_{k+2}\ge 2x_k+1$ (or equivalently $x_{k+2}+1\ge 2(x_k+1)$) for all $k$ as that would lead to $2047 \ge x_{21}+1\ge 2^{10}(x_1+1)\ge 2^{11}=2048$. Thus we find $k$ such that $x_{k+2}\le 2x_k$. With $b:=x_k$, $a:=x_{k+1}$, $c:=x_{k+2}\le 2b$, we have $$ bc\le ...


2

You have $50$ baskets, and each basket contains between $1$ and $24$ apples. I assume no basket contains $0$ apples since you said "$50$ baskets containing apples". Then you can take out 48 baskets and place $1$ apple in two of them, $2$ apples in two of them etc. until you have 48 baskets and for every number between $1$ and $24$ there are exactly two ...


2

$G:= \mathbb Z +r\mathbb Z \subset \mathbb R$ is a subgroup of $\mathbb R$. Because $r$ is irrational $G$ is a free abelian group of rank two. In particular it is not cyclic and therefore not discrete (the discrete subgroups of $\mathbb R$ are just the cyclic ones). A non-discrete subgroup of $\mathbb R$ is dense in $\mathbb R$. So you find elements in ...


1

Note that for any three positive integers $a,b,c$, if $2^k\leqslant b<a<c<2^{k+1}$ for some $k\in\mathbb{Z}_{>0}$, then $$bc<ac<a\cdot 2^{k+1}=2a\cdot 2^k\leqslant 2a\cdot a=2a^2,$$ and $$bc>ba\geqslant 2^ka=\frac{1}{2}\cdot 2^{k+1}a>\frac{1}{2}\cdot a\cdot a=\frac{1}{2}a^2.$$ Thus, $2^k\leqslant b<a<c<2^{k+1}$ for some ...


1

Let set $S$ be the set of integers from $1$ to $2046$, we split $S$ to $S_i$s like this: $$S_1=\{1,2,3\}\\S_i=\{s\in\mathbb{Z}\,|\,2^{i}\le s\lt2^{i+1}\}\quad (2\le i\lt10)\\ S_{10}=\{1024,1025,\dots,2046\}$$ So we have $10$ sets in total, by Pigeonhole principle there's a set which has at least $\lceil\frac{21}{10}\rceil=3$ elements from those $21$ chosen ...


1

Your oversight is that $q$ gets arbitrarily large; the heuristic analysis would conclude $q \epsilon \approx \infty \cdot 0$, which tells you nothing. In fact, I believe it can be shown that the set of possibilities for $|qr - [qr]|$ will actually be dense in $[0, 1/2]$. To make this argument work, it isn't enough for $p/q$ to be close to $r$: it has to be ...


1

Let's say we have $26=5\cdot 5+1$ students but suppose that no $6$ students get the same grade. Then at for each grade there are at most $5$ students getting that particular grade. But then that means there are at most $5\cdot 5$ students all together, which is a contradiction.


1

Consider the general case, where $A=\{1, 2, 3, \dots, k\}$ for any positive integer, where $k$ is not restricted to be of the form $3n+1$ (however, so that I can write $\left\lfloor\frac{k}{3}\right\rfloor$ later, I will restrict $k\geq 3$). I will show by induction that there is no subset $B$ of $A$ where no three distinct elements of $B$ sum to another ...



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