A cyclic construction of triples in which every pair appears once

MOONL1T·Jul 24, 2025

Counting suggests a Steiner triple system, but quoting an existence theorem feels much stronger than necessary. Can we explicitly construct the triples for 3n children when n is odd? Problem: In a school class with

3n

children, any two children make a common present to exactly one other child. Prove that for all odd

n

it is possible that the following holds: For any three children

A

B

and

C

in the class, if

A

and

B

make a present to

C

then

A

and

C

make a present to

B

. Source: Baltic Way 2008 · MNET-014V

Open MNET-014V in the question bank →

4 replies

MissingNo404·Jul 26, 2025

Label the children

(i,r)

with i modulo n and r modulo 3. Include the vertical triples

\{(i,0),(i,1),(i,2)\}

. For each unordered distinct pair i,j and each r, also include

\{(i,r),(j,r),((i+j)/2,r+1)\}

, where division by 2 is modulo n.

MOONL1T·Jul 26, 2025

Odd n is exactly what makes that midpoint unique. Same-layer pairs are covered once, and pairs with equal first coordinate are covered by the vertical triples.

MissingNo404·Jul 26, 2025

For a mixed-layer pair

(i,r),(k,r+1)

with i≠k, the remaining vertex must be

(2k-i,r)

. It is different from i because 2 is invertible, and it is uniquely determined. Every unordered pair of distinct layers has exactly one orientation r→r+1 modulo 3, so this covers the remaining pairs once.

threeheartsleft·Jul 26, 2025

Now define the recipient of a pair to be the third child of its unique triple. Symmetry inside each triple gives the requested implication immediately.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

A cyclic construction of triples in which every pair appears once

MOONL1T·Jul 24, 2025

3n

children, any two children make a common present to exactly one other child. Prove that for all odd

n

it is possible that the following holds: For any three children

A

B

and

C

in the class, if

A

and

B

make a present to

C

then

A

and

C

make a present to

B

. Source: Baltic Way 2008 · MNET-014V

Open MNET-014V in the question bank →

4 replies

MissingNo404·Jul 26, 2025

Label the children

(i,r)

with i modulo n and r modulo 3. Include the vertical triples

\{(i,0),(i,1),(i,2)\}

. For each unordered distinct pair i,j and each r, also include

\{(i,r),(j,r),((i+j)/2,r+1)\}

, where division by 2 is modulo n.

MOONL1T·Jul 26, 2025

Odd n is exactly what makes that midpoint unique. Same-layer pairs are covered once, and pairs with equal first coordinate are covered by the vertical triples.

MissingNo404·Jul 26, 2025

For a mixed-layer pair

(i,r),(k,r+1)

with i≠k, the remaining vertex must be

(2k-i,r)

threeheartsleft·Jul 26, 2025

Now define the recipient of a pair to be the third child of its unique triple. Symmetry inside each triple gives the requested implication immediately.