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.
45
questions
23
votes
3
answers
8k
views
How do you create projective plane out of a finite field?
I have heard and read unclear mentions of links between projective planes and finite fields.
Is it possible to construct a projective plane (or a Steiner system) starting out with a field? Could you, ...
- 2,590
46
votes
2
answers
2k
views
For which $n\in\Bbb N$ can we divide $\{1,2,3,...,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
For which $n\in \mathbb{N}$ can we divide the set $\{1,2,3,\ldots,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
Since $x_i+y_i=3z_i$ for each ...
- 90.1k
8
votes
3
answers
370
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 ...
- 83
4
votes
1
answer
255
views
For which $q$ there exists a Steiner system $S(2, q, q^2)$?
I encountered the title question answering this question. It is well-known (see, for instance [vdW, $\S$ 43]) when $q$ is a power of a prime number there exists a finite field of order $q$. In this ...
- 91k
22
votes
3
answers
845
views
How many rounds would it take to get each pair on the same team at least once, not using all possible teams?
I have a young group of kids ($30$) playing soccer and they need to be put into $6$ teams of $5$ players for each round of matches. All $6$ teams play at the same time on adjoining fields.
If I wanted ...
- 361
6
votes
1
answer
179
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 ...
- 63
4
votes
1
answer
502
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, ...
- 51
2
votes
2
answers
248
views
$n$ people form $k$ clubs. Each club has at least 3 people. every two club has exactly 1 member in common. Maximum number of $k$?
$n$ people form $k$ clubs. Each club has at least 3 people. every two club has $1$ and exactly $1$ member in common. What's the maximum number of $k$?
My thoughts: Similar to oddtown problem, I can ...
- 365
15
votes
2
answers
592
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 ...
- 3,406
10
votes
2
answers
5k
views
Is there a memorable solution to Kirkman's School Girl Problem?
Given a solution to Kirkman's School Girl Problem, it is of course easy enough to check that it actually is a solution. But how could you reconstruct it if you lost it? Is there a method or algorithm ...
- 417
9
votes
1
answer
1k
views
Partition a set into g groups, k different ways, such that no pair of elements is ever in the same group together more than M times
Over at Wolves and Sheep on puzzling.stackexchange.com, noedne's answer involves repeatedly partitioning a group of 99 sheep into a series of "test groups" such that
All but one sheep are tested ...
- 601
7
votes
1
answer
130
views
Building a 3D matrix of positive integers
I'm trying to build a 3D matrix made up of positive integers that has very specific properties.
The matrix dimensions are $N \times N \times (N+1)$ where $N$ is a positive integer. The matrix has two ...
- 121
6
votes
1
answer
446
views
How many different ways can the signs be chosen so that $\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+1$?
How many different ways
can the signs be chosen
so that
$\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+1$?
This is an extension of this question:
For what $n$ can $\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+...
- 108k
5
votes
2
answers
172
views
Combinatorial design related to scheduling group activities (everyone tries every activity, no pair is together twice)
Trying to solve this problem led me to consider the following generalization.
Let $g$ and $p$ be positive integers. Imagine that you own $g$ distinct board games, where each game requires exactly $p$ ...
- 76k
4
votes
0
answers
441
views
Split $\{1,2,...,3n\}$ into triples with $x+y=4z$
A similar question appeared last week.
For which $n\in\Bbb N$ can we divide $\{1,2,3,...,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
In this ...
- 50.9k
2
votes
2
answers
682
views
Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help:
We would like a general way of creating 'fair' cookie-baking ...
- 123
1
vote
2
answers
155
views
Split $\{1,...,3n\}$ into triples with $x+y=5z$ - no solutions?
Following on from Split $\{1,2,...,3n\}$ into triples with $x+y=4z$ and For which $n\in\Bbb N$ can we divide $\{1,2,3,...,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,...
- 50.9k
1
vote
1
answer
116
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 ...
- 743
0
votes
3
answers
817
views
10 events, 10 teams
I need help scheduling an event where there are 10 activities and 10 teams. Each team plays against another team for each activity. Each team must play each activity. Ideally, they would not play ...
- 27
16
votes
1
answer
832
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 ...
- 161
9
votes
1
answer
412
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 ...
- 213
6
votes
2
answers
487
views
Who conjectured that there are only finitely many biplanes, and why?
This question on MathOverflow motivates me to ask what the reasoning is behind the conjecture that there are only finitely many biplanes. More generally, it has been conjectured that for fixed $\...
- 18.2k
6
votes
3
answers
3k
views
Orthogonal Latin Square 6*6
I need to make remarks about Tarry's Proof for the nonexistence of 6x6 Latin Squares as part of my final exam for a class I'm in. Problem is, I can't find it ANYWHERE on the internet. I can only find ...
- 61
5
votes
1
answer
453
views
Number of combinations such that each pair of combinations has at most x elements in common?
I am doing research on the sense of smell and have a combinatorics problem:
I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
5
votes
1
answer
942
views
A generalization of Kirkman's schoolgirl problem
A friend of mine asked me this question. "I have $3n$ elements, and I want to know which is the maximum number of triplets $(a,b,c)$ so that no two triplets have more than one element in common".
The ...
- 9,774
4
votes
0
answers
218
views
Count the number of sets of subsets of (Steiner?) triples
Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions:
two triples shall have atmost one number in common
over all triples each ...
- 18.5k
4
votes
2
answers
155
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) ...
- 679
4
votes
2
answers
1k
views
Handshake/pigeonhole principle problem?
There a number of people in a party. Each person shakes hands with exactly 20 people. For each pair of people that shakes hands with each other, there is exactly 1 other person who shakes hands with ...
- 2,218
4
votes
1
answer
147
views
Steiner triple system with $\lambda \le 1$
What's the maximum number of 3-sized subsets of $[n]$ that can exist such that no two subsets contain more than one common element?
When $n \equiv 1,3 \mod 6$ then this is equivalent to a Steiner ...
- 247
4
votes
0
answers
95
views
partitions of finite set in same-size parts having at most one element in common
Given $g \ge 2$, $k \ge 1$ and a population of $p = kg$ workers, I'm trying to figure out the longest series of work shifts such that:
during each shift, all workers work in $k$ teams of g people;
...
- 257
2
votes
1
answer
135
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 ...
- 496
2
votes
2
answers
230
views
Counting squares in finite fields (Paley Design)
Consider the following construction due to Paley: Let $q$ be a prime power congruent to 3 modulo 4, and let $Q \subset \mathbb{F}_q$ be the set of nonzero squares (note that $-1 \notin Q$). Call $X = \...
- 7,397
2
votes
1
answer
125
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,789
2
votes
1
answer
899
views
Idempotent and commutative Latin squares of even order.
Definition: A Latin square is said to be idempotent iff $\forall i=1,\cdots, m,[(i,i)=i]$
Definition: A Latin square is said to be commutative iff $\forall i,j((i,j)=(j,i))$ such that $1\leq i,j\leq ...
- 1,768
2
votes
1
answer
493
views
unbalancing lights
I'm reading the following notes on unbalancing lights, http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf. The question i have is regarding the first page. Where it says
Consider a square $n \times ...
- 1,146
2
votes
1
answer
94
views
A strange scheduling for $K_{24}$.
This question came from a question asked earlier today linked here
The question implicitly asked how to make a schedule with his/her class of 24 students such that:
1) Everyday will consist of the ...
- 1,999
1
vote
1
answer
70
views
k-subsets with some pair containing every element
Let $[n] := {1,2, 3, \dots, n}$ and $k$ be some fixed positive number.
Whats is the smallest number $m$ so that $A_1, A_2, \dots, A_m$ are k-subsets(each of size k) of $[n]$ and for every $x \in [n]$ ...
- 1,033
1
vote
2
answers
89
views
Choosing sets of vectors on a complex sphere
Consider a complex $t$ dimensional unit sphere.
Can we have $t$ sets of $2^t$ vectors $v_{ij}\in \Bbb C^t$ on the sphere where $i=1$ to $t$ and $j=1$ to $2^t$ on this with inner products satisfying $...
- 6,221
1
vote
1
answer
4k
views
how to create a schedule for 9 teams playing x number of games no team can play same team twice no team can play same game twice
I am setting up a minute to win it challenge for a party. I have 9 teams of 5 players each. Each round will be head to head challenge with one team idle per round. All games are played simultaneously. ...
- 21
0
votes
1
answer
141
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
0
votes
1
answer
80
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 ...
0
votes
1
answer
214
views
How can I arrange a group of people at tables and switch them around so that no two ever meet twice? [closed]
Say I have 5 tables of 4 people (i.e. 20 people in total) and a different game at every table. We play one round of games (so each table plays one unique game) and then switch tables. Is it possible ...
- 35
0
votes
1
answer
65
views
Minimum for combinatorial sortingproblem
I'm stuck with a combinatorial problem, maybe one of you can help me out, thanks in advance. So heres the problem:
Consider tuples $(i,j)\in \{1,...,N_1\}\times\{1,....,N_2\}=A$. Let $S_1,...,S_x$ be ...
- 320
0
votes
0
answers
239
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$ ...
- 67
0
votes
2
answers
207
views
Symmetrical combinatoral block design
Suppose that $(V,\mathcal{B}$) is a symmetric block design of type $2-(v,k,\lambda)$. Pick an arbitrary block $B \in \mathcal{B}$. Let $B_1,...,B_{v-1}$ be a list of the remaining blocks and let $n_1,....
- 3,408