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
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 ...

1
2 3 4 5 6