For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

181
votes
3answers
8k views

How many fours are needed to represent numbers up to $N$?

The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols. For example, $165=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) \...
178
votes
17answers
31k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
142
votes
3answers
26k views

Why can a Venn diagram for 4+ sets not be constructed using circles?

This page gives a few examples of Venn diagrams for 4 sets. Some examples: Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete $4$-...
118
votes
9answers
15k views

There are apparently $3072$ ways to draw this flower. But why?

This picture was in my friend's math book: Below the picture it says: There are $3072$ ways to draw this flower, starting from the center of the petals, without lifting the pen. I know ...
90
votes
1answer
2k views

Is there a characterization of groups with the property $\forall N\unlhd G,\:\exists H\leq G\text{ s.t. }H\cong G/N$?

A common mistake for beginning group theory students is the belief that a quotient of a group $G$ is necessarily isomorphic to a subgroup of $G$. Is there a characterization of the groups in which ...
79
votes
5answers
4k views

Cutting sticks puzzle

This was asked on sci.math ages ago, and never got a satisfactory answer. Given a number of sticks of integral length $ \ge n$ whose lengths add to $n(n+1)/2$. Can these always be broken (by ...
72
votes
2answers
3k views

Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol ...
71
votes
9answers
7k views

100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
71
votes
0answers
3k views

Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in random order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
64
votes
3answers
8k views

Mathematical research of Pokémon

In competitive Pokémon-play, two players pick a team of six Pokémon out of the 718 available. These are picked independently, that is, player $A$ is unaware of player $B$'s choice of Pokémon. Some ...
61
votes
2answers
4k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is $...
60
votes
2answers
6k views

Can 18 consecutive integers be separated into two groups,such that their product is equal?

Can $18$ consecutive positive integers be separated into two groups, such that their product is equal? We cannot leave out any number and neither we can take any number more than once. My work: ...
59
votes
8answers
33k views

Probability that random moves in the game 2048 will win

I have recently played the game 2048, created by Gabriele Cirulli, which is fun. I suggest trying if you have not. But my brother posed this question to me about the game: If he were to write a ...
59
votes
1answer
3k views

Quadratic reciprocity via generalized Fibonacci numbers?

This is a pet idea of mine which I thought I'd share. Fix a prime $q$ congruent to $1 \bmod 4$ and define a sequence $F_n$ by $F_0 = 0, F_1 = 1$, and $\displaystyle F_{n+2} = F_{n+1} + \frac{q-1}{4} ...
59
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
55
votes
19answers
17k views

Good Book On Combinatorics

What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
52
votes
10answers
23k views

Taking Seats on a Plane

This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless Imagine there are a 100 people in line to ...
49
votes
14answers
10k views

Why is it that if I count years from 2011 to 2014 as intervals I get 3 years, but if I count each year separately I get 4 years?

I'm not a very smart man. I'm trying to count how many years I've been working at my new job. I started in May 2011. If I count the years separately, I get that I've worked 4 years - 2011 (year 1), ...
48
votes
4answers
2k views

How many 7-note musical scales are possible within the 12-note system?

This combinatorial question has a musical motivation, which I provide below using as little musical jargon as I can. But first, I'll present a purely mathematical formulation for those not interested ...
48
votes
3answers
1k views

Alice and Bob matrix problem.

Alice and Bob play the following game with an $n*n$ matrix, where $n$ is odd. Alice fills in one of the entries of the matrix with a real number. then Bob fills one. Then Alice and so on so forth ...
47
votes
2answers
4k views

Identity for convolution of central binomial coefficients: $\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
46
votes
4answers
4k views

Do circles divide the plane into more regions than lines?

In this post it is mentioned that $n$ straight lines can divide the plane into a maximum number of $(n^{2}+n+2)/2$ different regions. What happens if we use circles instead of lines? That is, what ...
46
votes
2answers
2k views

How do the Catalan numbers turn up here?

The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an ...
43
votes
7answers
31k views

What is the math behind the game Spot It?

I just purchased the game Spot It. As per this site, the structure of the game is as follows: Game has 55 round playing cards. Each card has eight randomly placed symbols. There are a total of 50 ...
42
votes
2answers
2k views

A zero sum subset of a sum-full set

I had seen this problem a long time back and wasn't able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here. Apparently, this problem is from a ...
41
votes
7answers
5k views

How many scientists can survive?

Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are. The aliens made 101 headbands, numbered from 1 to 101. On the contest day, they throw ...
41
votes
4answers
9k views

Probability for the length of the longest run in $n$ Bernoulli trials

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
41
votes
7answers
963 views

Problems regarding $\{x_n \}$ defined by $x_1=1$; $x_n$ is the smallest distinct natural number such that $x_1+…+x_n$ is divisible by $n$.

Let me denote a sequence of distinct natural numbers by $x_n$ whose terms are determined as follows: $x_1$ is $1$ and $x_2$ is the smallest distinct natural number $n$ such that $x_1+x_2$ is divisible ...
41
votes
2answers
839 views

Counting trails in a triangular grid

A triangular grid has $N$ vertices, labeled from 1 to $N$. Two vertices $i$ and $j$ are adjacent if and only if $|i-j|=1$ or $|i-j|=2$. See the figure below for the case $N = 7$. How many trails ...
41
votes
4answers
1k views

Combinatorics Problem: Box Riddle

A huge group of people live a bizarre box based existence. Every day, everyone changes the box that they're in, and every day they share their box with exactly one person, and never share a box with ...
40
votes
5answers
874 views

Closed form for $\prod_{n=1}^\infty\sqrt[2^n]{\frac{\Gamma(2^n+\frac{1}{2})}{\Gamma(2^n)}}$

Is there a closed form for the following infinite product? $$\prod_{n=1}^\infty\sqrt[2^n]{\frac{\Gamma(2^n+\frac{1}{2})}{\Gamma(2^n)}}$$
40
votes
5answers
2k views

What structure does the alternating group preserve?

A common way to define a group is as the group of structure-preserving transformations on some structured set. For example, the symmetric group on a set $X$ preserves no structure: or, in other words,...
39
votes
3answers
527 views

Is $\lfloor n!/e\rfloor$ always even for $n\in\mathbb N$?

I checked several thousand natural numbers and observed that $\lfloor n!/e\rfloor$ seems to always be an even number. Is it indeed true for all $n\in\mathbb N$? How can we prove it? Are there any ...
39
votes
7answers
42k views

How many triangles

I saw this riddle today, it asks how many triangles are in this picture . I don't know how to solve this (without counting directly), though I guess it has something to do with some recurrence. ...
39
votes
3answers
2k views

Solutions to $\binom{n}{5} = 2 \binom{m}{5}$

In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says: On National Public Radio, the Weekend Edition program posed the following probability problem: Given a certain number of ...
38
votes
6answers
823 views

You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following. The professor is writing about how fast binomial coefficients grow. So, suppose you had 2 minutes to save ...
38
votes
1answer
822 views

What is that curve that appears when I use $\ln$ on Pascal's triangle?

I made a little program that generates Pascal triangles as images : I first tried it associating to each pixel a color whose intensity was proportional to the number in the Pascal triangle The ...
37
votes
2answers
2k views

Is there a clever solution to this elementary probability/combinatorics problem?

My friend was asked the following problem in an interview a while back, and it has a nice answer, leading me to believe that there is an equally nice solution. Suppose that there are 42 bags, ...
37
votes
3answers
3k views

What is the shortest string that contains all permutations of an alphabet?

What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$? I thought of this problem while reading a open problem on shortest ...
37
votes
3answers
1k views

Putting many disks in the unit square

Consider a square of side equal to $1$. Prove that we can place inside the square a finite number of disjoint circles, with different radii of the form $1/k$ with $k$ a positive integer, such that the ...
37
votes
2answers
3k views

Minesweeper - Chance of one-click win

I'd like to know if it's possible to calculate the odds of winning a game of Minesweeper (on easy difficulty) in a single click. This page documents a bug that occurs if you do so, and they calculate ...
34
votes
8answers
2k views

Show that a generalized knight can return to its original position only after an even number of moves

Source: German Mathematical Olympiad Problem: On an arbitrarily large chessboard, a generalized knight moves by jumping p squares in one direction and q squares in a perpendicular direction, p, q ...
34
votes
5answers
4k views

Prove that the 25 people can be seated in this way

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table. Prove that the 25 people can be seated such that, if A and B are two different people with ...
34
votes
4answers
2k views

Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

Let $\varphi(n)$ be Euler's totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$. Challenge: Prove $$\sum_{k=1}^n \left\lfloor \frac{n}{k} \right\...
34
votes
5answers
3k views

The 9 Billion Names of God

TLDR; I go on a math adventure and get overwhelmed :) Some background: My maths isn't great (I can't read notation) but I'm a competent programmer and reasonable problem solver. I've done the first ...
34
votes
3answers
2k views

Guaranteed Checkmate with Rooks in High-Dimensional Chess

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb Z^n$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
34
votes
3answers
1k views

A combinatorial proof of $n^n(n+2)^{n+1}>(n+1)^{2n+1}$?

The statement is simply that the sequence $\left(1+\frac{1}{n}\right)^n$ is increasing. Since the numbers $n^m$ have quite natural combinatorial interpretations, it makes me wonder if a ...
34
votes
1answer
2k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
34
votes
4answers
859 views

Strange Patience Game

I read about this game as a kid, but my maths was never up to solving it: The score starts at zero. Take a shuffled pack of cards and keep dealing face up until you reach the first Ace, at which the ...
34
votes
3answers
530 views

Guessing a subset of $\{1,…,N\}$

I pick a random subset $S$ of $\{1,\ldots,N\}$, and you have to guess what it is. After each guess $G$, I tell you the number of elements in $G \cap S$. How many guesses do you need?