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.

Filter by
Sorted by
Tagged with
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 ...
Katinka Lima's user avatar
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\} \...
Ariel Yael's user avatar
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 ...
SurThePickle's user avatar
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 ...
Tom 's user avatar
  • 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}, ...
Matthew Barber's user avatar
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, ...
Spinor8's user avatar
  • 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..(...
Peter McGavin's user avatar
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 ...
SKJens's user avatar
  • 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$...
hyportnex's user avatar
  • 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{...
meler's user avatar
  • 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 ...
Mathews Boban's user avatar
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\...
caffeinemachine's user avatar
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 ( ...
Sunaina Pati's user avatar
  • 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 ...
weux082690's user avatar
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....
user1161147's user avatar
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 ...
Araceli's user avatar
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\},\{...
Ook's user avatar
  • 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 ...
apirogov's user avatar
  • 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 ...
Ook's user avatar
  • 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 ...
Parsa IQT's user avatar
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 ...
user967210's user avatar
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 ...
letsmakemuffinstogether's user avatar
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$ ...
Thomas Blok's user avatar
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 ...
Jason K Lai's user avatar
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 ...
Bob Powers's user avatar
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 ...
B. Peet's user avatar
  • 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)? ...
George's user avatar
  • 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$...
yoyo's user avatar
  • 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 ...
Constantin Economides's user avatar
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 ...
Naiim's user avatar
  • 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 ...
The Amplitwist's user avatar
-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 ...
Raros's user avatar
  • 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$ $\...
mathhello's user avatar
  • 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) ...
Aeryk's user avatar
  • 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 ...
Amanda's user avatar
  • 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$ ...
user avatar
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, ...
Werner's user avatar
  • 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. ...
jimvb13's user avatar
  • 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 $...
ritwik's user avatar
  • 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 ...
Laslas's user avatar
  • 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....
user1153980's user avatar
  • 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 ...
Rincewind's user avatar
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 ...
yoyo's user avatar
  • 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,...
Tom Rossi's user avatar
  • 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 ...
jamaicanworm's user avatar
  • 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 ...
Daniel Dostal's user avatar
-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 ...
ProblemDestroyer's user avatar
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 ...
John Samples's user avatar
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 ...
lioness99a's user avatar
  • 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 ...
Tom's user avatar
  • 153

1
2 3 4 5
8