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

learn more… | top users | synonyms

1
vote
1answer
25 views

Minimum length $m$ of $n$ string with pairwise Hamming distance $m/2$

I want to construct $n$ binary strings, each of the same length $m$ (to be determined), such that each pair of string has Hamming distance exactly $m/2$ (i.e. the strings disagree on $m/2$ positions). ...
3
votes
2answers
139 views

How large can a set of pairwise disjoint 2-(7,3,1) designs (Fano planes) be?

As wikipedia defines well, the Fano plane is a small symmetric block design, specifically a 2-(7,3,1)-design. The points of the design are the points of the plane, and the blocks of the design are the ...
1
vote
2answers
82 views

Scheduling gym class

My cousin came to me with this problem yesterday: She has 8 students in her gym class. In tomorrows class she has planned 4 different activities to rotate them through, each of which requires ...
0
votes
1answer
26 views

Is there an estimate for how much k-element subsets are needed to have any t-element subset in at least one of them?

Let's call $S(t, k, n)$ a minimal number of $k$-element subsets (blocks) of an $n$-element set $S$ with the property that each $t$-element subset of $S$ is contained in at least one block. Are there ...
3
votes
1answer
54 views

Forming clubs with an odd number of members, with each pair of clubs having an even number of members in common

Suppose we have a town with $n$ residents who love forming groups. To limit the number of groups, the town head decided: 1) Every club must have an odd number of members, and 2) Any two clubs must ...
1
vote
0answers
44 views

Permutation of people and teams

Suppose 20 people attend an event where there is 4 different activities to do. Suppose we want to split the group in subgroups, each subgroup attending one session of an activity, then moving on the ...
0
votes
0answers
18 views

Constructing partial Steiner triple systems

Is there a general way to construct a partial Steiner triple system? There are algorithms to construct complete Steiner triple systems for $n \equiv 1, 3 \bmod 6$. From complete Steiner triple ...
4
votes
1answer
52 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 ...
2
votes
2answers
42 views

Known classes of Hadamard matrices

In the book Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices by Wallis et al., Appendix A of the chapter on Hadamard matrices gives a list of known classes of Hadamard matrices. However, ...
1
vote
1answer
46 views

Show that it is possible to guarantee a win by buying $14$ tickets.

You enter a lottery by picking a subset of three numbers from $\{1,2,3,4 \dots 14\}$ . You win a prize if you match at least two of the numbers on the winning ticket. Show that it is ...
2
votes
1answer
33 views

Balanced incomplete Block design for testing an experiment

I am reading something balanced incomplete block design from a book. I don't understand why is it easy to see that in this design Each vehicle is evaluated 8 times, each test driver evaluates 4 ...
2
votes
0answers
61 views

Is Einstein's riddle an example of a combinatorial design?

I have just learned a bit about combinatorial designs (BIBDs, constructing a ($b,v,r,k, \lambda$)-design, necessary conditions for a design, cyclic designs) and it reminded me a lot of Einstein's ...
1
vote
2answers
205 views

Grouping Problem

Suppose there are 9 strangers. We will assign them into 3 groups and each group has exactly 3 people. For each grouping, the strangers who were assigned into the same group will get to know each other ...
1
vote
1answer
29 views

a problem with tasters-combinatorial design theory

I have a collection of flavors being sampled in batches of $3$. I know that each pair of flavors occur together in exactly one batch. Also each flavor appears in the same number of batches. How can ...
1
vote
1answer
58 views

How to arrange tournament with 4 rounds for 100 players with each player playing game in group of 10?

I have tournament with 4 rounds and 100 players. Each round consists of 10 games (groups) with 10 players playing together a game (so every round is $10 \times 10$). Is it possible to schedule ...
3
votes
1answer
74 views

how to make a $3$-$(10,4,1)$ design using graphs

A $t$-$(v,k,\lambda)$ design is defined this way : We have a set with $v$ elements (called the points). We also have a collection of distinguished subsets each having $k$ elements, we call each of ...
2
votes
1answer
69 views

Special subspace in vector space over $\mathbb F_5$

Let $\mathbb F_5=\{0,1,2,3,4\}$ is finite field of size $5$. I am trying to find minimal $n$ so that vector space of dimension $n$ over $\mathbb F_5$ contains $2$ linearly independent vectors so that ...
1
vote
1answer
32 views

How can I create 14 unique team rosters from 24 students in groups of 2?

I have a class of 24 students, and they have 14 labs in which I have students partner up. I am trying to find a way to create a roster automatically such that none of my students has a repeat partner ...
3
votes
1answer
102 views

Finding symmetric commuting matrices $A,B,C,D \in M_n(1,-1)$ such that $ A^2+B^2+C^2+D^2=4nI_n $

I am trying to construct a Hadamard matrix of order 28 using Williamson's construction. But I am unable able to construct the necessary symmetric and commuting matrices. Definition: $H_n \in ...
0
votes
1answer
35 views

Existence of a (40,13,4)BIBD (Balanced Incomplete Block Design)

I have been asked to prove that there exists a (40,13,4)BIBD. I admittedly have no idea where to start with this. Checking some of the necessary conditions for BIBDs shows me that if such a BIBD ...
3
votes
3answers
57 views

Points necessary to intersect all lines in finite projective geometry

I'm reading about finite geometries, projective and affine. I wonder what the smallest set of points is, given a geometry $PG(d,q)$, that intersects all lines. (or hyperplanes.) For example in the ...
7
votes
1answer
232 views

What is the minimum number of guesses in order to guarantee to win the prize?

Your friend will pick a $4$-letter word and you will make guesses in order to find it. -A word can contain only the letters $A, B, C,\:\text {and} \:D$, and they can be used more than once. ...
7
votes
0answers
124 views

Minimal number of animals in a matching card game

I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The ...
0
votes
0answers
20 views

Hadamard matice decomposition to sparce matrices

$H_2=\begin{pmatrix} 1 & 1\\1 & -1 \end{pmatrix}$ and $H_{2n}=H_2\otimes H_n$. I am looking for decomposition of $H_n$ to sparce matrices and its proof. Is there any good source to suggest ? ...
0
votes
1answer
70 views

Visualising a 1-(50,15,15) design.

The problem I have is the visualisation of a 1-(50,15,15) design. That is a set of 50 points and 50 blocks (lines), so that each point is on 15 lines, and each line contains 15 points. My attempts ...
1
vote
1answer
49 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 ...
-5
votes
1answer
38 views

combinations of 5 groups question [duplicate]

I have $25$ people who will be split in to groups of $5$ people each day over $5$ days in $5$ different locations. Can I rotate them so they all meet each other only once and visit each location once ...
2
votes
1answer
88 views

How does the multiplicative group of a finite field, considered as a vector space, act on subspaces?

Given that a finite vector space $V = \operatorname{GF}(p)^n$ corresponds to the finite field $F = \operatorname{GF}(p^n)$, I'm wondering about how the multiplicative subgroup of $F$, $F^*$, acts on ...
2
votes
1answer
102 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 ...
1
vote
1answer
68 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
1
vote
0answers
54 views

Rotation of 15 people at five tables

I have five tables of four people each. At each table is a table leader who remains stationery. How do I rotate the 15 participants so that they get to meet new people each time they rotate?
0
votes
1answer
37 views

Integrality conditions and proof by double counting.

Theorem $\mathbf{3.4.}$ In a block design of type $2-(v,k,\lambda)$ every element lies in precisely $r$ blocks, where $$r(k-1)=\lambda(v-1)\textit{ and }bk=vr\;.$$ The letter $r$ stands for ...
0
votes
1answer
34 views

Constructing $\lambda$-difference sets. Please help.

Given a set say $A=${$0,1,4,16,r$} which is a subset of $\mathbb{Z}_{21}$. How do I find r, such that $A$ is a $\lambda$-difference set for some $\lambda$? Is there some methodical way to solve ...
0
votes
1answer
37 views

Question about symmetric block design and Hadamard matrix

I stock in middle of proving that if $A$ is matrix of symmetric block design and $B = 2A - J$ that $J$ is ones matrix then B is a Hadamard matrix if and only if $v = 4(k-\lambda)$. I need to prove ...
0
votes
1answer
26 views

Prove PB(8, {4,3}, 1) does not exist.

I was reading Wallis, Intro to Combinatorial Design. This is 2.1.3. I couldn't understand the way of counting. Hint says, let $f_4, f_3$ be the block counts of sizes 4,3 respectively, then, $6f_4 ...
2
votes
1answer
150 views

Determining the size of an automorphism group for a given design

I'm trying to wrap my head around the idea of automorphisms, and I'm having a lot of issues. One of the questions I've been given as an exercise is thus; Let $\mathbb{V} = \{1, 2, 3, 4, 5, 6\}$ ...
5
votes
2answers
862 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 ...
1
vote
1answer
75 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 ...
1
vote
0answers
66 views

Existence of Designs

I am familiar with Keevash's proof that provided divisibility conditions hold, $t-(n,k,\lambda)$ designs exist for all but finitely many $t,n,k,\lambda$. My question is, given some $n,t,k$ does ...
3
votes
1answer
38 views

Trying to find a combinatorial design which describes my problem

A group of 8 golfers would like to play in teams, split into two teams of 4, with a different arrangement of teams on each of 5 consecutive days; they would like each pair of players to be on the same ...
0
votes
2answers
105 views

Orthogonal arrays - relation to software testing, is that sample true?

When doing ortohognal arrays testing, the process is like this: Consider a function with 3 variables,each with 3 options. 3 pairs, each with 3*3 values = 27 parametric pairs. Each "function call" ...
1
vote
1answer
58 views

pairwise balanced design has block size related to the number of elements.

A pairwise balanced design is a set of elements $X$ and set of blocks $A$ such that each pair of elements of $X$ occurs in exactly $\lambda$ blocks. I am trying to solve the following problem: Given ...
0
votes
1answer
66 views

Proving Steiner triple system

Let $S$ be a set of size $v$ and let $T$ be a set of $3$-element subsets of $S$. Furthermore, suppose that (a) each pair of distinct elements of $S$ belongs to at least one triple in $T$, (b) $|T| ...
0
votes
0answers
21 views

Construction of a (3v-2,3,1)-BIBD

I want to construct a $(3v - 2,3,1)$-BIBD from a $(v,3,1)$-BIBD and a quasigroup of order $v-1$. Attempt: For new BIBD, firstly, I need $3v-2$ points. Let $A$ be a block in $(3v - 2,3,1)$-BIBD and ...
0
votes
0answers
39 views

Is there a formula to rotate users through 2 positions without repeating weeks, repeating positions, or being paired with the same user?

I need to rotate through users to do 2 jobs without doing the same job for consecutive times, without doing the same job twice in a row, and without being paired with the same person twice. Is there ...
1
vote
0answers
28 views

Combinatorial designs give triangulations of complete graphs

I recently attended a talk on combinatorial design theory. The speaker mentioned briefly that the Fano plane, and other designs give rise to triangulations of complete graphs (the Fano plane gives a ...
2
votes
1answer
46 views

Choosing a committee from two people who are not sitting beside each other.

Assume that $10$ people are sitting around a table. Determine the number of ways to choose a committee, where the committee is made up of two people who are NOT sitting next to each other. Take ...
0
votes
2answers
38 views

Number of blocks in this design $(V,\mathcal{B})$ $|V|=16$ and $\mathcal{B}$ has size $4$

Let $(V,\mathcal{B})$ be a design in which $|V|=16$, each block in $\mathcal{B}$ has size $4$, and each pair of points occurs in precisely one block. How many blocks are in this design? Try 1: ...
0
votes
1answer
22 views

Matrix array built from range?

I have the problem on a past exam: Let the array $L$ be defined by: $0\leq i, j \leq n-1$ $$L=[l_{i,j}] \text{where } l_{i.j} \equiv i+j \pmod n$$ Let $n=4$ and write down the array ...
0
votes
1answer
74 views

Prove Fisher's Inequality for a non-trivial 2 - (v, 4, λ) design

Fisher's Inequality states that if $v\ge k$, then $b\ge v$. In this case $k=4$. I am still pretty new to designs, and so don't understand things fully yet. There is a formula for $b$ as follows: $$b ...