Questions tagged [combinatorial-designs]
For questions about Combinatorial design theory, a part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. The theory has applications in the area of the design of experiments.
352
questions
0
votes
0
answers
28
views
How many locks and keys: combinatorics problem [duplicate]
A village keep all their most precious belongings in a vault. The vault has a certain number of locks, each lock with an individual and specific key. The people in the village want to make sure that ...
1
vote
1
answer
93
views
Finding 35 sets of size 6 in $A=\{1,\ldots,70\}$ s.t. for each choice of 6 numbers in $A$ there's always a set with intersection of size at least 2
Look at $A=\{1,\ldots,70\}$. I want to find 35 sets, $s_{1},\ldots,s_{35}\subseteq A$, where $\forall i,\;\left|s_{i}\right|=6$, and for each choice of six numbers $\left\{ a_{1},\ldots,a_{6}\right\} \...
- 411
1
vote
1
answer
43
views
Subsets of three numbers from a set of n numbers such that no two subsets have a shared pair of numbers
I've had this problem for a long time. The problem goes as follows (it is a bit hard to say concisely): Let's say, for example, I have the numbers 1-9 (n=9) and am looking to arrange these numbers in ...
- 11
1
vote
2
answers
70
views
12 players in groups of 4 over 4 games - can they all play together?
12 players play 4 games. In each game they play in groups of four, and, within each four, they play as pairs. So, in 4 games each player must have 4 different partners, and should play with as many of ...
- 11
1
vote
0
answers
48
views
What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?
Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
4
votes
1
answer
57
views
List of 3 unique triplets from a group of 9 where every row is unique as well.
Say we have 9 people. Every week, they will form into groups of 3. The condition is that the triplet that is formed must never have been seen together before. So let's say for week 1, we have: ABC, ...
- 143
0
votes
2
answers
71
views
Combinatorial scheduling problem
In optimising a parallel computer program, I need to solve what looks like a simple combinatorial problem, but it's driving me nuts.
There are N*(N-1)/2 (i,j) tuples of all combinations of integer 0..(...
0
votes
1
answer
61
views
Generating groups without repetition
I got curious about this when making groups for a tournament. We have have 11 players, and the tournament consists of 4 rounds. In every round, there will be three groups. Two groups of 4 people, and ...
- 1
2
votes
2
answers
106
views
How to arrange numbers on grid to satisfy a minimum condition?
Take an $N \times M$ rectangular grid and arrange the integers from $1$ to $ N M$ so that all grid point gets an assignment without repetition, and let the integer number on location (grid point) $n,m$...
- 731
6
votes
1
answer
127
views
Minimizing the diagonal product of a special orthogonal matrix
For any $n > 1$, define $f: \textrm{SO}(n) \rightarrow \mathbb{R}$ as the diagonal product
$$f(A) = \prod_{i=1}^n A_{ii}$$
Based on some numerical experiments, it seems that
$$\min_{A \in \textrm{...
- 145
1
vote
1
answer
73
views
Existence of a Hadamard-like matrix
Question:
For all $n$ large enough, there exists a matrix $A \in [-1,1]^{n \times n}$ such that $A\cdot A$ is a diagonal matrix with each diagonal entry at least $\frac{n}{100}$.
Discussion:
When ...
- 531
1
vote
1
answer
78
views
A family of subsets each of size $r$ must witness decent size of intersection for some two members.
$\newcommand{\lrp}[1]{\left(#1\right)}$ $\newcommand{\R}{\mathbf R}$ $\newcommand{\lrb}[1]{\left[#1\right]}$
Problem (Iberoamerican Olympiad 2001). Let $n, r, k$ be positive integers and assume $k\...
- 18.1k
2
votes
0
answers
153
views
Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.
Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.
I got this problem from the double counting handout ( ...
- 4,105
0
votes
0
answers
38
views
Name for a family of sets where each pair can appear at most once
Suppose I have a set $B$ of size $n$, and I want to construct a family of subsets of size $k$ of $B$ which have the property that for any pair $a, b \in B$ of distinct elements there is at most one ...
- 958
3
votes
1
answer
68
views
Table Tennis Player Grouping Problem
I have changed the description of the problem in a different way.
Q: There are N points and all points must be connected by a line segment. But you can't just draw a line, you have to draw a triangle....
- 31
0
votes
0
answers
47
views
Geometric analogies for Kirkman's Schoolgirls
Of the seven solutions to Kirkman's Schoolgirl Problem, three have simple and elegant geometrical analogies. An answer to this question shows an analogy to solution I; similar ones exist for II and ...
- 1
0
votes
1
answer
41
views
Why can't these $STS(9)$'s have 8 blocks in common?
Take the following pair of balanced partial triple systems $(R,P_1)$, $(R,P_2)$. Where $R=\{1,2,3,4,5,6\}$ and:
$P_1=\{\{1,3,5\},\{1,4,6\},\{2,4,5\},\{2,3,6\}\}$
$P_2=\{\{1,4,5\},\{1,3,6\},\{2,4,6\},\{...
- 189
2
votes
0
answers
46
views
Some questions about resolvable group divisible designs
In the context of some other construction (which is irrelevant here), I was looking for a way to generate a collection "orthogonal partitions" on a set of nodes with a fixed and uniform set ...
- 193
0
votes
0
answers
35
views
Is there an (11,3,3)-BIBD with specific conditions?
Does there exist an $(11,3,3)-BIBD$ such that:
No element of $B$ is repeated where $B$ is the set of blocks.
There exists a subset $B'$ of $B$ such that any pair of elements of $\{1,2,...,11\}$ is in ...
- 189
2
votes
1
answer
66
views
Set of integers with unique differences
I have looked at the interesting Conway-Guy Sequence which possesses a neat property of having unique subset sums.
But I would like to find an integer set (which is optimally compact, ie has the ...
- 21
1
vote
1
answer
92
views
Partitions with pairwise small intersection [duplicate]
Let $n$ and $k$ be positive integers, such that $k$ is a divisor of $n$. I am interested in creating a sequence of partitions of $\{1,\dots,n\}$, like the one below. The rules are this:
Each row is a ...
- 571
1
vote
2
answers
81
views
Dinner party combinatorics (meeting each other once)
I am hosting a meet-and-greet dinner party but am having troubles with some elementary combinatorics. I got 20 people for a dinner party and they can only sit at tables in groups of 4. What is the ...
- 1,834
6
votes
2
answers
110
views
School Outing Combinatorial Design Problem
So this is an actual organization problem I am dealing with right now as a high school teacher. There is a school outing, with $8$ groups of students. At the venue there are $7$ stations, where $2$ ...
- 360
6
votes
2
answers
212
views
Combinatorics with multiple design rules (e.g. no more than X instances, no more than X contiguous instances, etc.)
I am struggling with a biochemistry question that when broken down is just a mathematics combinatorics problem. Hopefully this type of question is allowed on this Stack Exchange (apologies if it is ...
- 163
2
votes
1
answer
86
views
Binary labelling
I learned of this question from a man in England and I find it fascinating.
You have a number of portraits which are distinguished from each other by binary labels. For example, in each portrait the ...
- 249
0
votes
1
answer
63
views
Are there parameters such that a combinatorial $(n_s,m_t)$ configuration does not exist?
It is well known that given a $(n_s,m_t)$ configuration the following must hold:
$$ms=nt$$
$$s(t-1)+1\leq m$$
$$t(s-1)+1\leq n$$
However, for example, a $(43_7,43_7)$ configuration would be an order 6 ...
- 186
0
votes
1
answer
56
views
In a semi-regular polyhedron, why does a polygon with odd sides (e.g. a triangle) have to be surrounded by polygons of the same type (e.g. squares)? [closed]
In a semi-regular polyhedron with 4 faces meeting at each vertex, why does a polygon with an odd number of sides (such as a triangle) have to be surrounded by polygons of the same type (e.g. squares)?
...
- 1
3
votes
1
answer
65
views
Combinatorial decomposition of summands in product
Let
$$
X=\{(i_1,\ldots,i_{n-1}) : i_j\in[1,n]\}.
$$
Is there a "natural" way to decompose $X=\bigcup_kX_k$ such that for $x\in X_k$, no coordinate of $x$ is equal to $k$?
For example:
[$n=2$...
- 9,559
0
votes
1
answer
77
views
Question dealing with partitions of a set with N elements into classes with 2 elements
I stumbled upon a maths problem wich I need To solve for a current paper I am writing. Have you seen this before? Is it solved and more concretely is there an efficient algorithm for this problem? If ...
2
votes
0
answers
40
views
Can we characterize the “associate classes” of a unipotent quasi-commutative quasigroup as some combinatorial design?
$I_n$ is the $n \times n$ or order $n$ identity matrix, $J_n$ is the order $n$ matrix of all ones, and $n \in \mathbb{Z}^+$.
We define a Latin square $\mathcal{L_n}$ to be a set of $n$ permutation ...
- 317
1
vote
1
answer
72
views
Can there be more than $\log_2(n)$ mutually orthogonal $(\pm1)$-vectors $x$ in $\mathbb{R}^n$ such that $x_{2k-1} \neq x_{2k}$ for all $k$?
A Hadamard matrix of order $n$ is an $n \times n$ matrix with entries $\pm1$ such that any two rows are mutually orthogonal. Any Hadamard matrix must necessarily have order equal to $1$, $2$, or a ...
- 732
-1
votes
2
answers
63
views
Generate groups for multiple match rounds while minimizing the number of times two participants are in the same match [closed]
We are hosting an event with 100 participants.
$20$ Participants can participate in one Match.
$5$ Matches with $20$ Participants each will be called one Round. (Each participant is only playing one ...
- 1
3
votes
0
answers
64
views
Combinatorial design using finite field
Let $\mathcal{F} = \{A_1, \cdots, A_n\}$ be a family of sets with the following conditions.
For all $i$, $|A_i| = p^k+1$ where $p$ is prime and $k$ is an integer
If $i \neq j$, $|A_i \cap A_j| = 1$
$\...
- 678
4
votes
2
answers
151
views
Efficient way to rotate through partitions with subsets of size three
I'm looking to generalize the following problem and solution.
Problem 0: You have a group of $n$ people that need to all meet each other in pairs (e.g. maybe they have to all shake hands or something) ...
- 557
2
votes
1
answer
66
views
How many groups of people can we make with x number of overlaps?
Say I have 120 people and I want to put them into unique groups of 6 without replacement where nobody knows each other.
It would be at minimum 120/6 + (120/6)/6 = 20 + (3.33) = ~ 23 (My reasoning here ...
- 21
4
votes
1
answer
210
views
Bounding Turán numbers $t_3(11,5)$ and $t_3(16,7)$
I am looking to find the upper bound for Turán numbers $t_3(11,5)$ and $t_3(16,7)$. Here $t_r(n,m)$ denotes the smallest integer $k$ such that each $r$-uniform hyper graph on $n$ vertices with $k+1$ ...
user931598
1
vote
0
answers
70
views
Mathematical equation for pairing
There must be a mathematical answer for this…
We have a team of 10 people that needs to be divided into two teams, one made up of three, and a team of 7 for a two week duration.
After that two weeks, ...
- 111
7
votes
1
answer
168
views
Order 3 projective plane with playing cards
The projective space based on $\mathbb{F}_3$, the finite field with 3 elements (PP3), has 13 lines and 13 points, with every two lines meeting at one point and every two points determining a line. ...
- 643
2
votes
1
answer
91
views
How many distinct sets can be formed if each element can be present in at max r sets?
A set of subsets of the set $\{1,2,\ldots,n\}$ is to be created in the following way : for a certain integer $r$ such that $n \geq r$,
Each element of $\{1,2,3,\ldots,n\}$ can be present in at most $...
- 45
2
votes
1
answer
95
views
Need to split 2n teams into n different games with no team meeting another team or playing a game more than once
I've found multiple similar questions, but none answering this case, and I can't manage to extrapolate from the other answers. The closest I've found is this one.
Here is my problem:
I have 10 ...
- 23
1
vote
1
answer
57
views
Is there a name for arrangements of n sets consisting of unique single values for the intersection of each k of them?
For example the sets {1,2},{1,3} and {2,3} are such that each 2 of them intersect in unique values. This can be done for any n and k where n is the number of sets and k is the number of intersections....
- 1,023
1
vote
1
answer
38
views
For a Steiner system, how many blocks intersect exactly one position of a specific block?
Consider Steiner system $S(2,k,v)$ with $2 = t < k < v$, a family of $k$-subsets of finite set $S$ with $|S|=v$ such that each $t$-subset of $S$ is contained in exactly one block.
A paper I'm ...
- 51
4
votes
3
answers
103
views
maximal number of independent subsets (bitstrings with uniform distribution)?
Let $B=\{0,1\}^n$ be the set of length $n$ bit-strings with the uniform distribution, and let $\mathcal{F}=\{f:B\to \{0,1\}\}$ be the set of all binary functions on $B$.
What is the maximal size of an ...
- 9,559
4
votes
0
answers
38
views
Organizing Meetups Where People Meet Exactly Once [duplicate]
Okay, I've seen this question asked multiple ways, but I cannot get my head wrapped around it! With 9 people, I can have a schedule where each person participates in 4 meetings of 3 people per meeting,...
- 141
0
votes
1
answer
43
views
How to sort into X bins Y times with minimum overlap?
Let's say I'm hosting a series of dinner parties for a total of $N$ guests. Each night, there are $X$ tables, and we are meeting for a total of $Y$ nights.
I want to preassign the guests to tables ...
- 4,344
1
vote
0
answers
31
views
Latin square analogy - finding a balanced arrangement of elements
I've come across a practical problem in discrete mathematics, and I suspect that some clever mind knows a better solution than brute force.
Imagine that we are hosting a competition in which each of ...
- 121
-1
votes
1
answer
78
views
Showing that whether a construction is the maximum /minimum or not
16 friends decided to form clubs. Each club will have 4 members, and any two clubs may have at most two member in common. What is the greatest/least possible number of clubs they can form.
Got 7 ...
- 967
9
votes
1
answer
377
views
Coloring a Generalized Latin Square
Suppose we have an $n \times n$ array, and there is a decomposition $\mathcal{A}$ of its coordinates $a_{i,j}$ into sets $A_m$ as follows:
If $a_{i,j} \in A_m$, then $a_{j,i} \in A_m$. So they're ...
- 781
0
votes
1
answer
96
views
Real World Problem - Groups Visiting Various Stations
Context: This is a real world problem that I am trying to solve that I would appreciate some help with - I'm sure there's a Mathematical concept that will help me, but I'm struggling to remember back ...
- 4,945
5
votes
1
answer
72
views
Minimum swaps necessary for every person to meet every other person at every location
The setting:
There are 9 people.
There are 3 locations.
At any time, there are 3 people at each location.
People can only swap locations at the same time.
The goal:
Every person visits each ...
- 153