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.
257
questions
6
votes
3answers
104 views
How many combinations of groups are there where no member of a group has been with another member before?
I found this hard to word in the title, so let me give an example.
I have 16 students, and I want to split them up into 4 groups of 4. However, I want to make sure that every time I have a new ...
-1
votes
0answers
36 views
How can I split $36$ people into $6$ teams of $6$ on $6$ different occasions so that no one person is with the same person twice? [closed]
I have $36$ people that need to be split into $6$ groups on $6$ different tasks but don't want any people to be together twice. I am stuck with the manual splitting...
1
vote
1answer
47 views
Counting subsets of fixed size which differ by more than one element.
The board game Dominion is randomized at the start of play to allow players to purchase from 10 different piles, each pile chosen at random from 26 different choices. This number (26) has increased ...
1
vote
1answer
78 views
Group Testing Problems Where the Number of Defectives is Given By a Probability Distribution
I was looking at Wolves and Sheep and had an interesting thought.
The original problem says that out of $100$ sheep, it is known that there are $5$ wolves and they want to minimize the number of tests ...
2
votes
1answer
63 views
Calculating edge cover for this Hypergraph?
Let $D= \{a_1,a_2,...,a_n\}$ be a set of constants. For any subset of $D$ of cardinality $3$, we define another set (we call it hyper-edge) containing all $3 \choose 2$ pair-wise combinations (we call ...
1
vote
1answer
77 views
Making $100$ ordered lists with the numbers $1 - n$ $5$ times such that no two lists are the same at more than one index.
What is the minimum $n$ such that it is possible to make at least $100$ ordered lists with the numbers $1-n$ (can repeat numbers) of length $5$ with the property that any two ordered lists are the ...
5
votes
1answer
75 views
Number of combinations with small intersection
I have set $S$ of $n$ elements. I want to understand, in how many ways can I choose $n/2$ elements - let each such choice be set $S_i$ - such that no two choices have more than $n/4$ elements in ...
0
votes
1answer
69 views
Combinations of X elements taken Y at a time with each combination not sharing more than Z element with another
Good evening,
As the title explains, I am looking for an algorithm (I'd implement it in Python) to generate all of the combinations for a given basket of X stocks taken Y at a time (order is not ...
4
votes
1answer
100 views
Tournament bracket for a 4-player game and 13 players in total
We have a tournament in which 13 players participate, and matches are played in groups of 4 players (i.e. it's a 4-player game).
There are 13 rounds in total, each player skips one round, and the ...
4
votes
1answer
100 views
Everyone is passed everything exactly once, but never from the same person
Say 4 or more people are sitting around a table. Each has a sheet of paper. Devise an algorithm to pass these papers between these people that guarantees:
Each person passes and signs every piece of ...
15
votes
2answers
333 views
“Math Lotto” Tickets - finding the minimum winning set
"Math lotto" is played as follows: a player marks six squares on a 6x6
square. Then six "losing squares" are drawn. A player wins if none of the losing squares
are marked on his ...
1
vote
1answer
33 views
Understanding the Steiner triple system
I am learning what Steiner systems are and I stumboled upon this Wolfram Mathworld source: https://mathworld.wolfram.com/SteinerTripleSystem.html.
I understand that $k = 3$ means that there are ...
2
votes
0answers
37 views
Enumerating separating subcollections of a set
Let $S$ be a (finite) set, and let $C \subseteq 2^S$ be a collection of subsets of $S$. We say that a subcollection $C' \subseteq C$ is separating if for any two elements of $S$ there exists a subset ...
1
vote
1answer
52 views
How many blocks can be made of a subset of S in a Steiner system
Assume a Steiner system with parameters $t, k, n$, i.e., $S(t,k,n)$. By definition, the system is an $n$-element set $S$ together with a set of $k$-element subsets of $S$ (called blocks) such that ...
17
votes
1answer
347 views
How many meetings would it take for 12 people to meet in 4 groups of 3 until they met everyone?
I have a group of 12 people that I would like to meet in four groups of three each month. How many minimum months would it take such that each person has been in at least one group with every other ...
0
votes
0answers
42 views
A round of introductions: A graph problem?
There is an introductory session for $n$ people. And to allow some conversation, we split the group into $k$ groups of similar sizes $s$. This is repeated until each person shared a group with ...
2
votes
1answer
56 views
System of distinct representatives and chessboards
I encountered the following problem, which was presented in the context of the topic of SDRs (system of distinct representatives) - I am able to solve the problem, but I make no use of a SDR, and I am ...
0
votes
1answer
24 views
How to show that a list of sets with the parameters (4,2,1) is A VALID BLOCK DESIGN?
I have to determine whether or not the list of sets with the parameters v=4, b=6, r=3, k=2 and $\lambda$ = 1 is a valid block design. Now my first thought was to ensure that these parameters satisfy ...
4
votes
1answer
59 views
Self-orthogonal Latin squares
A Latin square $A$ is called self-orthogonal if $A$ and $A^{T}$ are orthogonal Latin squares.
Use the elements of $\;\mathbb{Z}_v$ as the names of the rows and columns of your Latin square. Let $\...
0
votes
1answer
37 views
Combinatorial design summation identities.
Let $\mathcal{D}$ be a $(v,k,\lambda)$-design and $B\in \mathcal{D}$ an arbitary block. Let $y_i$ be the number of block which have exactly $i$ common elements with $B$, $(i < k)$. Prove that:
$$\...
2
votes
0answers
27 views
Resolvable $(10,2,1)$-design
I need to construct a resolvable $(10,2,1)$-design and it's parallel classes. The design itself is easy to construct but I don't know how to construct the parallel classes. I know that since $r=9$ (...
1
vote
1answer
23 views
Minimal number of objects, each containing $n$ features, s.t. in the set of all objects each feature is represented at least $k$ times.
Can anyone please help frame this problem theoretically and/or guide me to its solution?
I think it might be partly related to 'set cover' type of problems, but the requirements are a bit different.
...
0
votes
0answers
30 views
Equivalent statements regarding combinatorial designs
Assume that $2\leq k <v$ and $\lambda>0$ and let $S=\{1,2,...,v\}$. We know that $A_1,A_2,...,A_b$ are subsets of $S$ for which $|A_i|=k,\; \forall i$. Prove that if any two of the three ...
0
votes
1answer
45 views
Finding sets that satisfy intersection cardinalities
Let's say I have a set of elements $V$. I can use all subsets of $V$ of size $k$ to satisfy intersection conditions.
Example:
$V = \{ 1, 2, 3, 4, 5\}$, $k = 3$.
$|B_1 \cap B_2|=2$,$|B_2 \cap B_3|=2$,$|...
0
votes
0answers
70 views
Maximum number of edges on a uniform hypergraph
I need to find the maximum number of hyperedges that can be drawn in a hypergraph, such that,
There are $8$ vertices.
Every edge contains exactly $4$ vertices.
Every edge should have exactly $2$ ...
6
votes
1answer
240 views
Steiner(5,6,12) system: symmetrical split into four or six
I am making a pack of Steiner(5,6,12) cards, and intend to make it available to others.
The plan is that there will be 143 cards, 2Ā¼ā³Ć3Ā½ā³ ā 57mmĆ89mm, comprising: the 132 Steiner cards; one or two ...
5
votes
1answer
103 views
Guessing colored hats without repetition
This entire question is inspired by Problem $12082$ of the Problems and Solutions section of the American Mathematical Monthly (see the May $2020$ issue for the solution to said problem). First, I ...
2
votes
1answer
79 views
Largest set $B$ such that $|A\cap (B-B)|=p$
In a preprint I was reading the following was claimed without proof:
Let $A$ be a subset of $[n]:=\{1,2,\dots n\}$ where $|A|<\frac{n}{k}$ for some integer $k$. Then there exists a set $B\subset [...
1
vote
0answers
31 views
$2$-$(v, \{3,4\},1)$-Designs
Let $t$, $\lambda$, $v$ be positive integers and let $K$ be a set of positive integers.
A $t$-$(v,K,\lambda)$-design is a pair $(X,\scr{B})$ such that
$X$ is a set (of so-called vertices) of ...
1
vote
0answers
49 views
Partitioning crown graphs into girth 6 diameter 3 subgraphs / packing of graphs representing finite projective planes
I came up with this original conjecture several years ago, and the formal wording below about a year afterwards.
My conjecture:
For all primes $P$, there exists a $P$-color edge coloring of the $2(P^...
2
votes
1answer
64 views
Collection of subset generating every pairs of elements
I'm looking forward to a construction with the following property:
Given a set S of n elements, find a small/the smallest collection of subsets of S of size k such that for every pair of elements a, ...
0
votes
0answers
43 views
Dual of a Symmetric Design
I'm struggling with the following problem regarding designs:
Let D be a $(v,k,\lambda)$ symmetric design with point set $\Omega$ and set of block $\mathcal{B}$. That is $|\mathcal{B}|=v$.
The dual ...
0
votes
1answer
154 views
Bingo 90 Strip Generator (UK Version)
The rules of the Bingo UK Game:
there are 90 bingo balls.
A bingo ticket consists of 9 columns and 3 rows. For each ticket:
A row contains exactly five numbers and four blanks.
A column consists ...
2
votes
2answers
56 views
Permuting 9 people such that all people are grouped with each other the nearest number of times
So I'm working on a problem which involves 9 agents which will be separated as follows. Each round, one of the agents will be put into a group on their own, ie. they will "sit out", whilst the other 8 ...
1
vote
1answer
40 views
How to construct a self orthogonal Latin square of order 5
I have been unable to find an elegant method of constructing self orthogonal Latin squares. However, I came across this question: construct a self orthogonal Latin square of order 5 using the fact ...
0
votes
0answers
20 views
Prove that the elements on the main diagonal of a SOLS (self-orthogonal Latin square) of order n form a transversal.
Prove that the elements on the main diagonal of a SOLS (self-orthogonal Latin square) of order n form a transversal.
I tried to start this question by considering the following definitions:
Two ...
1
vote
1answer
24 views
Sit $16$ people $4$ at a time so each pair sits exactly once [closed]
There are $16$ people who are asked to sit down on $4$ chairs. Every person has to sit with $3$ others.
Is it possible for every pair of people to sit with each other exactly once?
Now I have ...
1
vote
1answer
20 views
Intersecting Problem on Finite Projective Plane
We define a projective plane of order $q$ as a $(q+1)$-uniform family of subsets of a set $X$ where $|X|=q^2+q+1$ such that there is exactly one line passes every two distinct points.
Here we are ...
2
votes
3answers
42 views
Find which columns of a matrix are linear combination of the others
Consider the example where I have a matrix $\mathbf{D}$ in $-1/1$ coding with $5$ columns,
$$D = \begin{bmatrix}-1&-1&-1&1&1\\1&-1&-1&-1&1\\-1&1&-1&-1&-...
1
vote
1answer
123 views
Prove that there are no idempotent, commutative quasigroups of even order.
I'm trying to prove this using a counting argument - Meaning of counting argument?
I understand one can proved this for Latin Squares, as done in this post -Idempotent and commutative Latin squares ...
0
votes
0answers
44 views
combinatorial block design
Suppose that $(X, B)$ is a $2-(v, k, \lambda)$ design. For $x \in X$, let $r_x$ be the number
of blocks in $B$ containing $x$. Show that
$r_x(k ā 1) = Ī»(v ā 1)$. Secondly, deduce that $r_x$ is ...
0
votes
0answers
97 views
Pairing Combinations of an 8-player/team round-robin
I potentially want to write code for a 8-player/team round-robin tool that allows you to use any combination of schedule (e.g. select from various drop downs). The problem is I don't understand one ...
1
vote
0answers
84 views
Specific balanced block designs
My colleague is investigating the following problem.
For a given natural number $n$ construct a specific balanced block design, namely, a family $\mathcal D$ consisting of $n$-element subsets of a ...
3
votes
2answers
100 views
Filling an $8\times 8$ grid with the numbers $1$ to $64$ such that every $3\times 3$ subsquare has a sum less than $256$
Can you help me construct an $8 \times 8$ square filled with numbers from 1 to 64 (each cell has a different number obviously) such that every $3 \times 3$ subsquare has sum of numbers less than $256$?...
3
votes
1answer
241 views
The least average number of Corona virus tests
Suppose in a finite population (of size $n$), all configuration of individuals infected with the Corona virus (numbering $2^n$) are equally likely.
Consider the coronavirus testing procedure where ...
2
votes
1answer
117 views
Show that any $n \times n$ array based on $\{1,2,..,n\}$ is a Latin Square if and only if it is simultaneously orthogonal to R and C.
I've been reading Design Theory by Zhe-Xian Wan, but I have been stuck on where to begin with this question - Page 95, Exercises 4.7, Question 4.1.
Could someone please give me a hint?
Let
\begin{...
2
votes
2answers
105 views
How do you find a $(21,5,1)$-difference set in $(\mathbb{Z}_{21}, +)$?
How do you find a $(21,5,1)$-difference set in $(\mathbb{Z}_{21}, +)$?
I already know the answer which is $\{0,1,6,8,18\}$.
But How do you get that?
Obviously, if you subtract each elements by ...
1
vote
2answers
85 views
Show that there is no non-trivial solution for $x^2 + 2z^2 = 10y^2$
I need help with this to show that the result contradicts Bruck-Ryser-Chowla Theorem, which then implies that no biplane of order $10$ exists. At first I tried proving that no non-trivial solution ...
0
votes
0answers
24 views
Small question regarding Hadamard matrix of order $4m$
I am curious about something after reading stuff about Hadamard matrix conjecture.
What I understand is that all of the $4m$ rows are orthogonal.
Is it possible that for some $m$ such that the ...
0
votes
1answer
42 views
Cartesian product of two Steiner Triple Systems is a Steiner Triple system
Let [n] = {1,2,...,n}.
Suppose that ([n], T1) and ([m], T2) are STS on the sets [n] and [m] respectively. Let T be the set of triples {(i, r),(j, s),(k, t)} of elements in [n] Ć [m] that each ...
