All Questions
Tagged with combinatorics algorithms
118
questions
15
votes
2
answers
1k
views
Domination problem with sets
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:
(1) $|S_i|\leq 3,i=1,2,...,k$
(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,...
- 90.7k
14
votes
2
answers
5k
views
For what coinage systems does a greedy algorithm not work in providing change?
For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.
However, for a coinage system with 12 cent coins, a greedy ...
- 3,445
13
votes
3
answers
2k
views
Deducing correct answers from multiple choice exams
I am looking for an algorithmic way to solve the following problem.
Problem
Say we are given a multiple choice test with 100 questions, 4 answers per question (exactly one of those four being ...
- 346
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
9
votes
2
answers
6k
views
Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal
Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same.
I tried a bunch of equations but ...
- 193
9
votes
2
answers
738
views
Connect $n$ white and $n$ black points
$n$ black and $n$ white points are drawn on plane, so that no three of them lay on one line. How to prove that we can connect each white point to some black point by straight segment so that no two ...
- 4,793
9
votes
3
answers
535
views
What is the largest possible number of moves that can be taken to color the whole grid?
Consider a $10\times 10$ grid. On every move, we color $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is ...
- 90.7k
8
votes
1
answer
1k
views
Multivariate Faà di Bruno's formula
I'm attempting to implement a computer algebra function using the combinatoric version of Faà di Bruno's formula presented by Michael Hardy in Combinatorics of Partial Derivatives that "collapses" ...
- 131
8
votes
2
answers
1k
views
Reorder adjacency matrices of regular graphs so they are the same
Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$.
$A_x$ ...
- 499
8
votes
1
answer
2k
views
Is there a simple algorithm to generate unlabeled graphs?
While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
- 1,431
7
votes
2
answers
3k
views
Given $2n$ points in the plane, prove we can connect them with $n$ nonintersecting segments
Given $2n$ points in the plane such that no three points lie on one line. Prove that it is possible to draw $n$ segments such that each segment connects a pair of these points and no two segments ...
- 1,418
7
votes
1
answer
830
views
Alice and Bob make all numbers to zero game
Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn.
In a turn :
A player selects one of the integers, divides it ...
- 235
7
votes
1
answer
902
views
Enumerating all antichains in a finite poset
I have some reasonably small finite posets (on less than 20 points) and would like to iterate over all "downsets" in the poset, where a downset is a set closed under ≤ (so if x in X, and y ≤ x, then y ...
- 55.9k
7
votes
1
answer
3k
views
Traveling salesman problem: a worst case scenario
For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
- 133
6
votes
2
answers
3k
views
Jugs of Water Puzzle: Minimum Number of Operations
PUZZLE. Given two water jugs with capacities $a, b \in \mathbb{N}$, the goal is to measure exactly $c$ units of water only performing the following operations:
fill one of the jugs to it's capacity ...
- 341