All Questions
Tagged with combinatorics algorithms
117
questions
5
votes
1
answer
957
views
A generalization of Kirkman's schoolgirl problem
A friend of mine asked me this question. "I have $3n$ elements, and I want to know which is the maximum number of triplets $(a,b,c)$ so that no two triplets have more than one element in common".
The ...
- 9,944
5
votes
2
answers
1k
views
Santa is secretly deranged! or, how to hand-generate assignments for a gift exchange?
Consider a standard Secret Santa/gift exchange game draw. We have a pool of $n$ people, each of whom is supposed to be assigned another member of the pool to find a gift for, without the recipient ...
- 38.2k
5
votes
1
answer
2k
views
Searching a Young tableau
An $n \times n$ Young tableau is an $n \times n$ matrix of distinct integers, with each row and each column sorted in increasing order.
Now, we are given an $n \times n$ Young tableau $T$ and an ...
- 3,315
5
votes
2
answers
473
views
Coin weighing to find similar-weight sets
There are $n$ coins. You have a scale that, between two sets of coins, tells you which set is heavier, or if they are equal. What is the worst-case minimum number of weighings after which you can ...
- 7,194
4
votes
0
answers
95
views
partitions of finite set in same-size parts having at most one element in common
Given $g \ge 2$, $k \ge 1$ and a population of $p = kg$ workers, I'm trying to figure out the longest series of work shifts such that:
during each shift, all workers work in $k$ teams of g people;
...
- 257
4
votes
0
answers
310
views
Find the number of simple labeled graphs which have no isolated vertices
Find the number of simple labeled graphs on n vertices which have no isolated vertices? Compute the result for n=13
Total number of simple labeled graphs = $2^{n \choose 2}$.
How to remove vertices ...
- 860
4
votes
3
answers
9k
views
Efficient algorithm to find all unique combinations of set given duplicates
The number of combinations for a 4 choose 2 is 6. But what if I have a set in which 2 of the elements are the same? Of course I could do a unique check for each item but this is too computationally ...
- 145
4
votes
2
answers
195
views
Finding counterfeit coins
Suppose I have $N$ rare coins, of which $M \le N$ are counterfeits. I am blind. I ask an oracle who charges me a penny to tell me in yes/no answers whether there is a counterfeit in any group I show ...
- 555
4
votes
2
answers
2k
views
How do I prove a combinatorial statement about the change-making problem when using the greedy algorithm?
Let $D$ be set of denominations and $m$ the largest element of $D$. We say that $c$ is a counterexample if the greedy algorithm gives an answer different from the optimal one.
Now, apparently, if for ...
- 175
4
votes
2
answers
1k
views
Algorithm to uniquely determine a number using two adjacent digits
(Russia)
Arutyun and Amayak perform a magic trick as follows. A spectator writes down on a board a sequence of $N$ (decimal) digits. Amayak covers two adjacent digits by a black disc. Then Arutyun ...
- 3,914
4
votes
0
answers
80
views
Combinatorics of sets
Let us take an $n \in \mathbb{N}$ . Consider $S=${${\text{1,2,3,}\cdots \text{n}}$} .
Call a subset of $S$ to be X-sum-friendly if the sum of the elements of this subset is $X$ where $X \in \mathbb{...
- 63
4
votes
1
answer
1k
views
Find all distinct binary de Bruijn sequences
Messing around with numbers has lead me to the following problem, which I am struggling with. (No, not a homework question, just a problem I've thought up myself):
A binary de Bruijn sequence of order ...
- 151
3
votes
1
answer
808
views
number of derangements
In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses.
A derangement of n numbers is a ...
- 315
3
votes
1
answer
161
views
How to solve a given combinatorial problem?
Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
- 33
3
votes
1
answer
362
views
Searching Algorithm among 2 color balls.
You have $2^k + 1$ white and $2^k - 1$ black balls. Each group of balls have exactly one radioactive ball. You have a device which measures group of balls (quantity and color doesn't matter) and says ...
- 127