All Questions
Tagged with combinatorics recreational-mathematics
628
questions
3
votes
1
answer
154
views
Minimum number of subsets required to satisfy a condition
Consider the set $[n]=\{1,2,\cdots,n\}$, and consider a family of subsets of this set, satisfying the following condition:
$$\forall \ i,j,k \in[n], i\ne j,j\ne k,i\ne k$$there exists a subset $A$ in ...
- 1,508
0
votes
0
answers
141
views
How to calculate the number of ways to arrange $x$ items in $y$ different containers, with each container have different size
Example:
There are $3$ containers, with capacity $4, 2,$ and $3$ items, respectively. How many way to arrange $6$ items on those containers?
Answer:
container size $= 4, 2, 3$
number of items to be ...
- 35
13
votes
2
answers
330
views
What is the fractal dimension of the image given by a combinatorial sequence about permutation cycles?
OEIS sequence A186759 is a triangle read by rows:
$T(n,k)$ is the number of permutations of $\{1,2,\dots,n\}$ having $k$ nonincreasing cycles or fixed points,
where a cycle $(b_1\ b_2\ \cdots\ b_m)$ ...
- 5,072
5
votes
1
answer
261
views
How many time do we need to shuffle two decks red and blue to get back to initial colors?
Question
Let's say:
I have two decks of $n$ cards each (a blue and a red decks), I am not interested in card faces, just in colors of card backs;
Each time I shuffle perfectly ($n$ cards in each hand,...
- 510
10
votes
2
answers
481
views
Which rectangles can be tiled with L-trominos, when only two orientations are allowed?
This is a question that I got after reading this: https://www.cut-the-knot.org/Curriculum/Games/LminoRect.shtml. (This link already gave me the same result as theorem 1.1 of the article https://www....
1
vote
1
answer
106
views
how many white squares does a $2022 \times 2021$ block have?
An infinite checkerboard is coloured black and white so that every $2\times 3$ block has exactly two white squares. Prove (or disprove) that every $2022\times 2021$ block has the same number of white ...
- 2,031
6
votes
1
answer
128
views
Prove there exist numbers $a_i, b_j$ so that $x_{ij}=a_i + b_j$ for all $1\le i,j\le n$ if any full tour costs the same
In a country with $n$ towns the cost of travel from the $i$-th town to the $j$-th town is $x_{ij}$. Suppose the total cost of any route passing through each town exactly once and ending at its ...
- 1,137
3
votes
4
answers
273
views
Bug jumping problem
In the real axis, there is a bug standing at coordinate $x=1$. At each step, from the position $x=a$, the bug can jump to either $x=a+2$ or $x=\frac{a}{2}$. How many positions in total are there (...
- 199
0
votes
0
answers
74
views
find all positive integers n for which there exists a certain $n\times n$ table where each entry is I,M, or O
Find all positive integers $n$ for which we can fill in the entries of an $n\times n$ table with the following properties:
Each entry can be one of $I,M,O$;
In each row and each column, the letters $...
- 1,137
2
votes
2
answers
372
views
The number of four-digit numbers that have distinct digits and are divisible by $99$
We try to find the number of four-digit numbers that have distinct digits and are divisible by $99$.
Let a number be $N = abcd$, then we have $9| N$ and $11|N$.
Thus $9| a+b+c+d$ and $a+c \equiv b+d \...
- 12.7k
2
votes
0
answers
152
views
$8$-coin problem with $3$ balance scales ($1$ broken) and its generalization
You've $8$ identical-looking coins. All the coins weigh the same but $1$ coin is lighter than the rest. You're given $3$ double-pan balance scales. $2$ of the scales work, but the $3$rd is broken and ...
0
votes
3
answers
85
views
Distributing $4$ indistinguishable black marbles and $6$ distinguishable coloured marbles into $5$ distinguishable boxes.
Prove that there are exactly $8100$ different ways of distributing $4$ indistinguishable black marbles and $6$ distinguishable coloured marbles ( none of them black) into $5$ distinguishable boxes in ...
- 12.7k
0
votes
0
answers
34
views
Expected maximum occupation number for randomly distributed objects [duplicate]
Suppose you have $M$ distinguishable objects distributed amongst $N$ distinguishable boxes. Can you calculate the expected maximum occupation number $E_\text{max}(N,M)$? (in other words, the expected ...
- 2,339
0
votes
0
answers
57
views
Looking for resources to better learn pigeonhole principle and other combinatorical arguments
While I claim to understand the premise of the pigeonhole principle (if $n > k$ then inserting $n$ elements into $k$ boxes results some boxes containing at least two items), I am still quite bad at ...
- 1,221
2
votes
1
answer
103
views
A game of identifying real coins and weighing them.
Here is my problem as follows.
There are 2 counterfeit coins among 5 coins that look
identical. Both counterfeit coins have the same weight and the other
three real coins have the same weight. The ...
- 375