Skip to main content

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
1 answer
41 views

Team Scheduling 8 Teams, 5 Pitches, 4 rounds no repeats

I have to schedule a tournament. I've spent days on this with a degree in physics, no further forward. Question There are 8 teams, there are 5 pitches, and there are only 4 rounds. All teams must ...
Andy Johnstone's user avatar
0 votes
0 answers
49 views

A combinatorial problem involving columns of matrix with entries 0 or 1

Let $n$ and $k$ be positive integers such that $k<n$. Let $M$ be a $m \times n$ matrix whose entries are $0$ or $1$, where $m=\binom{n}{k}.$ Suppose each row of $M$ has exactly $k$ number of $1's$. ...
Lavy's user avatar
  • 11
1 vote
0 answers
27 views

Non-computer-aided method to prove there is only one (9,3,1)-BIBD up to isomorphism?

I am working on a project to classify small BIBD up to isomorphism by hand. However, when I try to classify (9,3,1) BIBD up to isomorphism, there are about 20 situations to consider and I don't think ...
wer's user avatar
  • 399
10 votes
0 answers
181 views

Infinite chessboard coloring without tetris pieces

Suppose we have an infinitely large chessboard, and we recolor the squares using black and white colors. Now we want to color as many black squares as we can, without forming any tetris pieces. Which ...
cybcat's user avatar
  • 589
0 votes
1 answer
84 views

Largest collections of subsets [closed]

I need to find largest collection of subsets of $\{1,\ldots, 84\}$ such that each subset has size 5 and any two distinct subsets have exactly one element in common. Any help is appreciated, Thanks
Harsh's user avatar
  • 378
0 votes
2 answers
54 views

Generating a table such that every pair of integers (a,b) exists at least in a row

Suppose I want to generate a table that has $50$ rows and $6$ columns. Each entry in that table can be an integer from $1$ to $75$ inclusive. Can I do it such that every pair of integers $(a,b)$ ($1 \...
Popular Power's user avatar
4 votes
2 answers
61 views

Families of $4$-subsets with small intersection

Consider this MSE question which has following setup: We have a set $X$ with cardinality $= n$ and a family $\mathcal{F}$ of $4-$subsets of $X$ such that for two distinct $A, B \in \mathcal{F}$, $|A\...
user1001001's user avatar
  • 5,215
0 votes
0 answers
13 views

Matching in designs

For a graph, we have the notion of perfect matching and Hall theorem. Is there a variant for designs? Do we know under which conditions, there are some mutually disjoint blocks of a design which cover ...
khers's user avatar
  • 379
3 votes
1 answer
40 views

Distributing elements of a multi-set to triplets with certain properties possible?

Let $M$ be the multi-set which contains exactly $7$ copies of each positive integer from $1$ to $15$. That is, $M=${$1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,\ldots , 15,15,15,15,15,15,15$}. Is it ...
Stein Chen's user avatar
2 votes
1 answer
39 views

For which $N$ does a deck of $N$ cards admit a collection of "magic triples"?

This self-answered question was asked to give a place to post an answer to a question of general interest that was deleted after the answer was mostly composed. Of course, other answers are also ...
Travis Willse's user avatar
3 votes
0 answers
29 views

How to construct a collection of magic triples? [duplicate]

This problem was posted three days ago. In a deck of 81 cards (all different from each other), it is said that given any two cards, there is exactly one card that forms a "magic" triple ...
Azlif's user avatar
  • 2,257
4 votes
2 answers
538 views

Where did I go wrong in this deck combinatorial problem?

In a deck of 81 cards (all different from each other), it is said that given any two cards, there is exactly one card that forms a "magic" triple with them. How many magic triples are there? ...
excitedGoose's user avatar
2 votes
1 answer
28 views

Finite inversive planes and $PSL_2(q)$

Example 6.2.4 of Dixon and Mortimer's, Permutation groups introduces inversive planes as Stainer systems. The classical (real) inversive plane can be naturally understood as a one-point extension of ...
Antonio Montero's user avatar
4 votes
1 answer
134 views

Permutations of 10 players within 2 Badminton courts: Covering $10$-vertex complete graph $K_{10} $ by two disjoint $K_4$

I am facing this everyday problem and I wanted to actually see how to formalise and reason on. We have 10 players and two courts in our badminton matches. We define a shift to be an instance of ...
Ramit's user avatar
  • 125
0 votes
0 answers
49 views

How do we construct the finite hyperbolic plane with 13 points?

According to Wolfram MathWorld, there are 2 non-isomorphic Steiner systems of type S(2,3,13), 1 of which is a finite hyperbolic plane. The page on a hyperbolic plane gives the following definition: ...
Core Silverman's user avatar
0 votes
0 answers
45 views

Generate a schedule for doubles with rotating partners

So I want to set up a schedule of double matches: player A and B vs player C and D. I have a few constraints for setting it up: Each player plays exactly 4 times The scheme should be as fair as ...
T C Molenaar's user avatar
7 votes
2 answers
177 views

Practical engineering combinatorial-design optimization problem

I am a very experienced electrical engineer. I am kindly asking for help! There is a practical case in electrical engineering that leads to the following question. Combinations without repetition (n=...
gooblek's user avatar
  • 73
6 votes
2 answers
256 views

2 tables of 6 people: What's a schedule such that all pairs share a table for an equal amount of time?

The problem There are 2 tables seating 6 people each. With 12 people, how many arrangements (with all 12 people seated) are necessary so that every pair shares a table for the same number of ...
Tom Sirgedas's user avatar
  • 1,148
2 votes
0 answers
47 views

How to determine if a Steiner System contains a smaller Stiener System?

Is there a method for determining whether a Steiner system contains a subset of smaller Steiner systems? For example, consider the Steiner Triple System $S(2, 3, 9)$. A valid output of this could be ...
Carl Lennartson's user avatar
3 votes
1 answer
139 views

How to construct a Steiner system?

I am looking for a way to construct the blocks for the Steiner system $S(2, 6, 96)$. For example, a valid construction of the Steiner system $S(2, 3, 7)$ would be the following: ...
Carl Lennartson's user avatar
0 votes
0 answers
19 views

Block design variant

I recently played a tournament where teams of four competed against each other. There were nine players and nine rounds, so each player sat once. The goal was that each player play with and against ...
Zach H's user avatar
  • 903
1 vote
0 answers
15 views

How to mathematically prove the "transitive property of nested predictors"?

Note: I posted this question on the Stats.Stackexchange site a week ago, but I think it might be better here. It's about proving a theorem I came up with about experiment data set structures, ...
Chris Science's user avatar
0 votes
2 answers
110 views

Tournament organization that avoids repetitions

A card game is played individually in tables of 4 players. I want to organize a tournament for 24 people. Hence in each round the players are divided into 6 tables. I want organize the tables so that ...
Millonet1's user avatar
0 votes
0 answers
42 views

Bruck–Ryser–Chowla theorem for $(v,k,\lambda)$ - designs in matrix terms

Let $A$ be a matrix of some $(v,k,\lambda)$-design. If there is a $(v,k,\lambda)$ - design and $n = k -\lambda$ is odd then the equation $ z^2=nx^2+\left(-1\right)^{\frac{v-1}{2}}\lambda y$ has ...
Orel_Algebraist's user avatar
0 votes
1 answer
63 views

How many distinct combinations of 10 pairs from 20 elements is possible without repetition?

I would like to know how can I calculate how many possible groups of 10 exclusive pairs can I draw out of a permutation list of 20 elements. I'm able to calculate the 190 pairs from 20 elements, and ...
Danilo Lemes's user avatar
0 votes
1 answer
38 views

Constructing projective geometries

I'm currently reading through Hughes and Piper's textbook Design Theory and am stuck on a section on projective geometries (Chapter 1, pages 17-19). The authors begin with the following definitions ...
Tom's user avatar
  • 65
0 votes
0 answers
28 views

6 people playing 8 ball

We figured out how to play 15 games with 5 players but not six yet. 3 teams of 2, changing players each game. One team sits out each game. We need the team sequenced so it works out that everyone ...
Alan's user avatar
  • 1
0 votes
0 answers
42 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
135 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
94 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
304 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
61 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
71 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
89 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
158 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
116 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
  • 796
7 votes
1 answer
149 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
  • 175
1 vote
1 answer
78 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
84 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
3 votes
1 answer
366 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,135
3 votes
1 answer
88 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
1 answer
45 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
  • 211
2 votes
0 answers
73 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
  • 203
1 vote
0 answers
39 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
  • 211
2 votes
1 answer
136 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
121 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
189 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
121 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
244 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
136 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

1
2 3 4 5
8