# Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially 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.

7,362 questions
1k views

### Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
2k views

### Mondrian Art Problem Upper Bound for defect

Divide a square of side $n$ into any number of non-congruent rectangles. If all the sides are integers, what is the smallest possible difference in area between the largest and smallest rectangles? ...
1k views

### How to find a total order with constrained comparisons

There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task? As ...
476 views

### Can Erdős-Turán $\frac{5}{8}$ theorem be generalised that way?

Suppose for an arbitrary group word $w$ ower the alphabet of $n$ symbols $\mathfrak{U_w}$ is a variety of all groups $G$, that satisfy an identity $\forall a_1, … , a_n \in G$ $w(a_1, … , a_n) = e$. ...
1k views

968 views

581 views

### When can we quit a game of War?

Consider the game of War. (The rules are below.) It would be nice to be able to end the game early. Suppose, for example, one player has 50 of the 52 cards. It is very likely that he's going to win. ...
303 views

274 views

### Maximum number of regions of a sphere partitioned by $\binom{n}{3}$ planes from $n$ points

We can place $n\in\mathbb{N}$ points on the surface of a sphere in a configuration so as to maximize the answer. A plane is defined by $3$ points. We create all $\binom{n}{3}$ planes from the $n$ ...
176 views

134 views

### Generating function for number of $r$-disjoint subsets each of size $k$

Fix $n, k$. Then $$C^{n,k}_r =\frac{1}{r!} \binom{n}{\underbrace{k, \ldots, k}_{\text{r times}}, n-rk} = \frac{n!}{r!(k!)^r(n - kr)!}$$ is the number of ways to form $r$ disjoint subsets each of ...
157 views

### Prove that $10 \times 10$ grid filled with positive integers contains two elements sharing a side such that their difference is at least $6$.

I have a $10 \times 10$ grid filled with different positive integers and want to prove that some two numbers sharing a side in a grid differ by at least $6$. My solution is: Let $m$ be the smallest ...
133 views

### A combinatorial proof by tesselation of the plane.

Some days ago the following problem was posed in the site: given a set of $N$ points in the plane such that for each pair of points $p,q$ we have $\lVert p-q\rVert >1$, prove there is a subset of ...
176 views

### Given $100$ coplanar points, no $3$ collinear, then at most $70$ percent triangles formed using these points are acute-angled

(IMO-$1970$) Given $100$ coplanar points, no $3$ collinear, prove that at most $70$ percent of the triangles formed using these points are acute-angled. I know that one solution proceeds by showing ...
101 views

### Number of paths of a certain type in a triangular array

Consider the $X_n$ set of finite integer sequences $(x_1, \ldots, x_{n})$ of length $n$ for which $x_1 = 0$ and $|x_k - x_{k+1}| = 1$ for each $k \in \{1, \cdots, n-1 \}$. Obviously $|X_n| = 2^{n-1}$. ...
236 views

### Check whether a polynomial ideal is prime in the power series ring

I would like to know whether the ideal $I = \langle y^{2}(y^{2}-x^{2}) + w^{7}, y^{2}(y^{4}-x^{4}) + z^{7}\rangle$ is prime in $\mathbb{C}[[x,y,z,w]]$, the ring of formal power series in the ...
### How many different paths to reach $(p,q,r)$ from $(0,0,0)$ without intersection
Problem: In $\mathbb{Z}^3$ starting from $(0,0,0)$ we try to reach $(p,q,r)$ with a sequence of moves. In each step we make a move from a point to another point under following conditions: You can ...