1. Optimization of Grouping for Complete Element Pairing #

Conditions

• There are $v$ individuals.
• Every day, they are divided into $g$ groups of $k$ individuals each ($v=gk$ for specific values of $v,k,g$ that satisfy this equation).
• The goal is to ensure that every pair of individuals ends up in the same group at least once.
• Additionally, it’s desired to prevent any specific pair of individuals from always being in the same group.

Problem

• The objective is to find the minimal number of days and the corresponding combinations that satisfy the above conditions.

1.1. Specific Examples of Grouping #

What is presented here are the upper limits of solutions I calculated manually. Due to insufficient computational resources to test all combinations, I am showing some combinations that required the fewest days among the solutions found.

• Total number of individuals $v$
• Number of individuals per group $k$
• The number of days required to create all possible pairs $d$
• The maximum number of times the same two individuals end up in the same group $m$

If the number of individuals does not appear in the table below, consider using a larger number of individuals (5) and refer to the table, treating the missing number as a skipped entry.

This document presents cases up to $k=10$ individuals per group, but the link provided below includes cases up to $k=25$ individuals per group.

Optimization of Grouping for Complete Element Pairing -sikinote

2. Description of the Problem #

2.1. Origin of the Problem #

The problem originates from the Purikura Problem¹, with stricter conditions applied. To put it more formally,

This could be a suitable description. The differences from the Purikura Problem include:

• In the Purikura Problem, it is sufficient to randomly select individuals from the entire group, whereas in this grouping problem, the same individual cannot be placed in a group until everyone has been grouped, marking a significant distinction.

2.2. Specific Example of the Problem #

To make the problem more understandable, let’s consider a concrete example.

Imagine you are organizing a training session and are tasked with dividing the participants into groups.
Since many of the training participants are meeting each other for the first time, you want to ensure that, during the training, everyone ends up in the same group with all the other participants at least once.
To summarize, the situation is as follows:

• A total of $v=15$ people will participate in the training.
• The training will last for 7 days.
• The training will be conducted in a group work format, with $k=3$ people per group (a total of $g=5$ groups).
• The groups will be changed daily.

The question is, how should the groups be divided so that, during the training, everyone ends up in the same group with everyone else at least once? And, is it even possible to achieve this within the duration of the training? This is the problem at hand.

3. Details #

3.1. Classification of the Problem #

This problem belongs to the field of combinatorial mathematics, specifically to block designs and experimental design methods.

It relates to Covering Designs² and Steiner Systems³ within these areas.

3.1.1. Covering design #

A Covering Design is defined as²:

A covering design is a collection of k-element subsets, called blocks, of {1,2,…,v}, such that any t-element subset is contained in at least one block.

A covering design is characterized by the parameters $v$, $k$, and $t$, and the upper limit of its combinations is given by $C(v,k,t)$.

A specific problem of covering design with $t=2$ is¹:

• The Purikura Problem correspond to $C(v,k,v=2)$

A key distinction between a Covering Design and the problem discussed in this document is that there is no differentiation in dividing all individuals into groups without remainder every day. Consequently, the number of days derived from a covering design provides a lower bound for the number of days required to solve the problem.

3.1.2. Steiner System #

Similar to the covering design, the Steiner System³ is another related concept.
However, the Steiner System imposes a stricter condition than merely grouping individuals together at least once. In a Steiner System, each pair of elements appears together in exactly one group, making the conditions more stringent than those of the problem discussed in this document.

The exact solution to the problem presented here corresponds to a Steiner System with $t=2$. If a Steiner System can be found for any given $v, k$, it would represent an exact solution to the problem. However, it’s important to note that a Steiner System with $t=2$ does not exist for arbitrary values of $v,k$, so any solution would be conditional upon finding such a system.

Steiner Systems, even in their special cases, have been discussed as challenging problems, with specific instances being named and posed as problems. For example, the following two problems are well-known:

• Kirkman’s schoolgirl problem⁴ $S(t=2,k=3,v=15)$
• Social golfer problem⁵ $S(t=2,k=4,v=32)$

When $k=3$, this is specifically referred to as a Steiner triple system (STS), and Kirkman’s schoolgirl problem is denoted as $STS(15)$.

For more examples are shown in below page: Social Golfer Problem -Math Games

4. References #