# Tagged Questions

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.

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

### Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
194 views

### Moving half of the nuts

An even number of nuts is divided into three nonempty piles. In each step, we are allowed to take half the nuts from a pile with an even number of nuts, and put them on another pile. Can we always ...
718 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 ...
618 views

112 views

### Covering pairs with permutations

Consider an $n \times n$ matrix $M_n$ with the following properties: Each row is a permutation of $A_n \equiv \{1, 2, ..., n\}$. Every ordered pair $(i,j)$, $i,j \in A_n$, $i \neq j$, appears as a ...
215 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. ...
281 views

95 views

128 views

### Minimal number of animals in a matching card game

I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The ...
113 views

### Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
84 views

Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. The support of a vector $v = (v_1,\ldots, v_n) \in \mathbb{K}^n$ is given by $\text{supp}(... 0answers 192 views ### How to maximize the number of operations in process In my research project I have encountered the following problem, concerning a tuple of words in the formal language$L=\{0,1\}^*$, with$\epsilon$denoting the empty word. If we are given an ordered ... 0answers 166 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 ... 0answers 89 views ### Has this subset-sum game been studied? Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between$1$and$9$. The first player who can make three of their ... 0answers 108 views ### Finding a separating family of subsets of$[n]$of size$n+1$. I have this friend who always tells me problems I can't solve. Here is the latest one. We are given a family$\mathcal F$of at least$2^{n-1}+1 $subsets$[n]$. We must prove that we can$\color{...
So, here is the problem: An ordinary deck of 52 playing cards is randomly divided into 4 piles of 13 cards each. Compute the probability that each pile has exactly 1 ace. My solution: \frac { {4 \...
Let $G$ denote the groups of $n\times n$ invertible matrices and $H$ be the subgroup of invertible upper triangular matrices. For $n=2$, by row reduction, or equivalently LU decomposition, it is ...