15
\$\begingroup\$

A Steiner quadruple system \$SQS(n)\$ is a collection of subsets (blocks) of size 4 of a set \$S\$ of size \$n\$ such that every subset of \$S\$ of size 3 is in exactly one block. It is easy to show that the number of blocks is \$\frac14\binom n3\$ and that a necessary condition for an \$SQS(n)\$ to exist is \$n\equiv2,4\bmod6\$. It is much harder to show that that condition is also sufficient, which is what Haim Hanani did in 1960.

Hanani's proof is almost completely inductive: the only explicitly listed \$SQS(n)\$ is an \$SQS(14)\$ with 91 blocks. It can't be memorised, however, so I want a program to generate such a system for me.

Task

Output all blocks of some \$SQS(14)\$ – how it is constructed is irrelevant.

Output should consist of 91 blocks of four values each. You may use any 14 distinct values. Formatting is flexible, but there must be a clear separation between blocks, and it must be clear which four values are in each block.

This is ; fewest bytes wins. You must run your code to completion and include its output in your answer.

Example

I have found an \$SQS(14)\$ whose blocks arise from the orbits of the base blocks \$1235, 126C, 12AB, 12DE, 12FG\$ under the permutations \$(1234567)(ABCDEFG)\$ and \$(1A)(2F5G3D)(4B6E7C)\$. The following are two possible output formats for this system:

1235 2346 3457 4561 5672 6713 7124
AGFD GFEC FEDB EDCA DCBG CBAF BAGE
126C 237D 341E 452F 563G 674A 715B
AGC6 GFB5 FEA4 EDG3 DCF2 CBE1 BAD7
12AB 23BC 34CD 45DE 56EF 67FG 71GA
15AE 52EB 26BF 63FC 37CG 74GD 41DA
13AC 35CE 57EG 72GB 24BD 46DF 61FA
12DE 23EF 34FG 45GA 56AB 67BC 71CD
15FC 52CG 26GD 63DA 37AE 74EB 41BF
13GB 35BD 57DF 72FA 24AC 46CE 61EG
12FG 23GA 34AB 45BC 56CD 67DE 71EF
15GD 52DA 26AE 63EB 37BF 74FC 41CG
13DF 35FA 57AC 72CE 24EG 46GB 61BD
[[0, 1, 2, 4], [1, 2, 3, 5], [2, 3, 4, 6], [3, 4, 5, 0], [4, 5, 6, 1], [5, 6, 0, 2], [6, 0, 1, 3], [7, 13, 12, 10], [13, 12, 11, 9], [12, 11, 10, 8], [11, 10, 9, 7], [10, 9, 8, 13], [9, 8, 7, 12], [8, 7, 13, 11], [0, 1, 5, 9], [1, 2, 6, 10], [2, 3, 0, 11], [3, 4, 1, 12], [4, 5, 2, 13], [5, 6, 3, 7], [6, 0, 4, 8], [7, 13, 9, 5], [13, 12, 8, 4], [12, 11, 7, 3], [11, 10, 13, 2], [10, 9, 12, 1], [9, 8, 11, 0], [8, 7, 10, 6], [0, 1, 7, 8], [1, 2, 8, 9], [2, 3, 9, 10], [3, 4, 10, 11], [4, 5, 11, 12], [5, 6, 12, 13], [6, 0, 13, 7], [0, 4, 7, 11], [4, 1, 11, 8], [1, 5, 8, 12], [5, 2, 12, 9], [2, 6, 9, 13], [6, 3, 13, 10], [3, 0, 10, 7], [0, 2, 7, 9], [2, 4, 9, 11], [4, 6, 11, 13], [6, 1, 13, 8], [1, 3, 8, 10], [3, 5, 10, 12], [5, 0, 12, 7], [0, 1, 10, 11], [1, 2, 11, 12], [2, 3, 12, 13], [3, 4, 13, 7], [4, 5, 7, 8], [5, 6, 8, 9], [6, 0, 9, 10], [0, 4, 12, 9], [4, 1, 9, 13], [1, 5, 13, 10], [5, 2, 10, 7], [2, 6, 7, 11], [6, 3, 11, 8], [3, 0, 8, 12], [0, 2, 13, 8], [2, 4, 8, 10], [4, 6, 10, 12], [6, 1, 12, 7], [1, 3, 7, 9], [3, 5, 9, 11], [5, 0, 11, 13], [0, 1, 12, 13], [1, 2, 13, 7], [2, 3, 7, 8], [3, 4, 8, 9], [4, 5, 9, 10], [5, 6, 10, 11], [6, 0, 11, 12], [0, 4, 13, 10], [4, 1, 10, 7], [1, 5, 7, 11], [5, 2, 11, 8], [2, 6, 8, 12], [6, 3, 12, 9], [3, 0, 9, 13], [0, 2, 10, 12], [2, 4, 12, 7], [4, 6, 7, 9], [6, 1, 9, 11], [1, 3, 11, 13], [3, 5, 13, 8], [5, 0, 8, 10]]

If you have your system in list-of-lists format like the second example you may verify it is a Steiner quadruple system here.


Thanks to @DLosc for help with the phrasing.

\$\endgroup\$

4 Answers 4

14
\$\begingroup\$

Python, 85 bytes

print({(*sorted((i*3**j+j)%14for i in[1,5,j%5^22,9910>>j%5*4]),)for j in range(210)})

Try it online!

Outputs {(0, 1, 4, 5), (6, 8, 11, 12), (1, 7, 9, 11), (2, 3, 12, 13), (2, 4, 9, 11), (0, 6, 7, 13), (4, 5, 11, 12), (4, 8, 10, 12), (8, 9, 10, 11), (2, 6, 9, 13), (1, 2, 5, 7), (3, 5, 7, 11), (1, 3, 7, 13), (0, 1, 2, 3), (1, 4, 8, 11), (0, 2, 11, 13), (2, 7, 10, 13), (1, 6, 8, 13), (2, 7, 11, 12), (8, 9, 12, 13), (0, 1, 12, 13), (0, 2, 4, 10), (4, 6, 11, 13), (0, 4, 6, 8), (1, 4, 9, 12), (2, 4, 6, 12), (4, 5, 10, 13), (3, 4, 10, 11), (4, 7, 12, 13), (0, 8, 10, 13), (1, 2, 10, 12), (0, 1, 10, 11), (0, 2, 8, 12), (5, 7, 8, 10), (10, 11, 12, 13), (0, 4, 7, 11), (6, 7, 10, 11), (3, 4, 8, 13), (0, 1, 7, 8), (3, 9, 11, 13), (3, 7, 8, 12), (0, 3, 4, 12), (0, 2, 5, 6), (0, 4, 9, 13), (0, 1, 6, 9), (0, 3, 8, 9), (2, 4, 7, 8), (0, 5, 8, 11), (5, 6, 9, 11), (1, 3, 8, 10), (1, 5, 8, 12), (1, 3, 11, 12), (1, 3, 4, 6), (1, 2, 8, 9), (0, 3, 7, 10), (0, 3, 5, 13), (2, 5, 10, 11), (6, 7, 8, 9), (2, 3, 4, 5), (1, 9, 10, 13), (2, 3, 6, 7), (1, 5, 6, 10), (4, 6, 9, 10), (3, 5, 6, 8), (3, 6, 9, 12), (0, 5, 9, 10), (0, 6, 10, 12), (5, 7, 9, 13), (0, 5, 7, 12), (5, 6, 12, 13), (0, 9, 11, 12), (7, 9, 10, 12), (3, 6, 10, 13), (4, 5, 8, 9), (0, 3, 6, 11), (3, 4, 7, 9), (7, 8, 11, 13), (1, 4, 7, 10), (2, 3, 8, 11), (1, 6, 7, 12), (2, 3, 9, 10), (1, 5, 11, 13), (2, 5, 8, 13), (2, 5, 9, 12), (2, 6, 8, 10), (1, 2, 6, 11), (1, 3, 5, 9), (3, 5, 10, 12), (1, 2, 4, 13), (4, 5, 6, 7), (0, 2, 7, 9)}.

\$\endgroup\$
2
  • 8
    \$\begingroup\$ Just how did you find this? :O \$\endgroup\$ Feb 4 at 4:56
  • 1
    \$\begingroup\$ Please add an explanation of how this works and how you found it. \$\endgroup\$ Feb 6 at 16:16
3
\$\begingroup\$

Vyxal, 182 bytes

»∨vw\\ẇẆ|ετfẆτ›≥Πo∩Ṗ…›Ẏ⟑ȮĠḃ…°Ṗ5=₴ƛ¯⇩7¡∇∞}⁺εḭ>∑‛u²%¤ßǔ]‡∨ε⁼Ġ†ȧ£€Ż₁T±↑⁋N∵ɽE"@∩⁺ ≤Ǐ0¬ė⅛6⌈0ż⇧⌊≈ŀ¬∑ȮW√꘍↓ṗX→≥bOÞẇṀÞ≈¢e5Ṙẏð₀ꜝ→£∴∑↑›∇₇⋏o½↓t¼¨8¾‹O¾ṪO\ȧ₁↑żẆðŀErc⊍≤λ?↓ṙ…k;,ε÷5M<ṅǒR‡,∩ŻIλ»14τṘ4ẇ

Try it Online!

This just hardcodes the result.

»...»       # Base-255 compressed integer
     14τ    # Convert to base 14
        Ṙ   # Reverse (because leading zero)
         4ẇ # Chunks of length 4

Or, if we're allowed to take a few universe lifetimes:

Vyxal, 20 bytes

14ɾ364↔'4ẇ3vḋÞf:U⁼;h

Try it Online!

This is a horrendously inefficient bruteforcer. It computes all \$14^{364}\$* sets of 14 symbols of length 364, for each gets combinations of three elements and checks if they all appear once.

The last two bytes can be removed if we're allowed to output all such sets.

14ɾ                  # 1...14 
   364↔              # Combinations of length 364
       '          ;h # Find one such that...
        4ẇ           # When grouped into lengths of 4
          3vḋÞf      # And all subsets of length 3 within those lists
               :U⁼   # Does it include all subsets exactly once? 

* Roughly 10^400, so give it a few universe lifetimes

\$\endgroup\$
0
2
\$\begingroup\$

JavaScript (ES6), 229 bytes

Returns a rearranged version of the example \$SQS(14)\$ with symbols \$1\$ to \$9\$ and \$a\$ to \$e\$.

x=>`2zmGWS01bV02fOWIS3j01dGF4uHUF4yC01b4kQVbm1hk01dHA01b3b015F01b3jXFG5cFU4yFCj61hk01aV01b3bSCF5dFF5dFFpt1ikAV4gZCF5dFF6m27gVV4h01bFcw27gVV4z2l82sgU5r742en6m2sf`.match(/[A-Z]|[012]?../g).map(s=>(x=parseInt(s,36)-~x).toString(15))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 180 bytes

⪪”$↶⧴F»ZÀ{XBS↧⁺MDu➙{ν%↘D12W?xV_*o}ηφ|Xη&S↗[-W⦄[×±α_M«Sl5 rυ№|↷ηx?«Xü¡×=IvM±&3i◧5¿C№⟦sB⁴σχ?‽∨K↷¤⌊﹪➙νηT\⎚ι‴;Z8←$�✳L\`κⅈ5·⊖;,⊙ς7qo⊞▶ïsG⁻Yωr§ς1C-Cτ&≔⊞7AηγpβD9a›ω ≔1“Þω⬤m@‖PEI↙⊕≕¦·G*Fρ”⁴

Try it online! Link is to verbose version of code. Outputs values A-N. Explanation: Splits a compressed string into chunks of 4.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.