(85,21,5)-Blockplan

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der (85,21,5)-Blockplan ist ein spezieller Symmetrischer Blockplan. Um ihn konstruieren zu können, musste dieses kombinatorische Problem gelöst werden: eine leere 85 × 85 - Matrix wurde so mit Einsen gefüllt, dass jede Zeile der Matrix genau 21 Einsen enthält und je zwei beliebige Zeilen genau 5 Einsen in der gleichen Spalte besitzen (nicht mehr und nicht weniger). Das klingt relativ einfach, ist aber nicht trivial zu lösen. Es gibt nur gewisse Kombinationen von Parametern (wie hier v = 85, k = 21, λ = 5), für die eine solche Konstruktion überhaupt machbar ist. In dieser Übersicht sind die kleinsten solcher (v,k,λ) aufgeführt.

Dieser symmetrische Blockplan hat die Parameter v = 85, k = 21, λ = 5 und damit folgende Eigenschaften:

  • Er besteht aus 85 Blöcken und 85 Punkten.
  • Jeder Block enthält genau 21 Punkte.
  • Je 2 Blöcke schneiden sich in genau 5 Punkten.
  • Jeder Punkt liegt auf genau 21 Blöcken.
  • Je 2 Punkte sind durch genau 5 Blöcke verbunden.

Existenz und Charakterisierung

[Bearbeiten | Quelltext bearbeiten]

Es existieren mindestens 213964 nichtisomorphe 2-(85,21,5) - Blockpläne[1]. Zwei dieser Lösungen sind:

  • Lösung 1 mit der Signatur 85·84. Sie enthält 3570 Ovale der Ordnung 2.
  • Lösung 2 mit der Signatur 73·20, 6·21, 1·22, 5·84. Sie enthält 72 Ovale der Ordnung 4.

Liste der Blöcke

[Bearbeiten | Quelltext bearbeiten]

Hier sind alle Blöcke dieses Blockplans aufgelistet; zum Verständnis dieser Liste siehe diese Veranschaulichung

  • Lösung 1
  1   2   8  12  20  23  25  26  28  30  41  42  50  59  66  72  73  76  78  82  85
  1   2   3   9  13  21  24  26  27  29  31  42  43  51  60  67  73  74  77  79  83
  2   3   4  10  14  22  25  27  28  30  32  43  44  52  61  68  74  75  78  80  84
  3   4   5  11  15  23  26  28  29  31  33  44  45  53  62  69  75  76  79  81  85
  1   4   5   6  12  16  24  27  29  30  32  34  45  46  54  63  70  76  77  80  82
  2   5   6   7  13  17  25  28  30  31  33  35  46  47  55  64  71  77  78  81  83
  3   6   7   8  14  18  26  29  31  32  34  36  47  48  56  65  72  78  79  82  84
  4   7   8   9  15  19  27  30  32  33  35  37  48  49  57  66  73  79  80  83  85
  1   5   8   9  10  16  20  28  31  33  34  36  38  49  50  58  67  74  80  81  84
  2   6   9  10  11  17  21  29  32  34  35  37  39  50  51  59  68  75  81  82  85
  1   3   7  10  11  12  18  22  30  33  35  36  38  40  51  52  60  69  76  82  83
  2   4   8  11  12  13  19  23  31  34  36  37  39  41  52  53  61  70  77  83  84
  3   5   9  12  13  14  20  24  32  35  37  38  40  42  53  54  62  71  78  84  85
  1   4   6  10  13  14  15  21  25  33  36  38  39  41  43  54  55  63  72  79  85
  1   2   5   7  11  14  15  16  22  26  34  37  39  40  42  44  55  56  64  73  80
  2   3   6   8  12  15  16  17  23  27  35  38  40  41  43  45  56  57  65  74  81
  3   4   7   9  13  16  17  18  24  28  36  39  41  42  44  46  57  58  66  75  82
  4   5   8  10  14  17  18  19  25  29  37  40  42  43  45  47  58  59  67  76  83
  5   6   9  11  15  18  19  20  26  30  38  41  43  44  46  48  59  60  68  77  84
  6   7  10  12  16  19  20  21  27  31  39  42  44  45  47  49  60  61  69  78  85
  1   7   8  11  13  17  20  21  22  28  32  40  43  45  46  48  50  61  62  70  79
  2   8   9  12  14  18  21  22  23  29  33  41  44  46  47  49  51  62  63  71  80
  3   9  10  13  15  19  22  23  24  30  34  42  45  47  48  50  52  63  64  72  81
  4  10  11  14  16  20  23  24  25  31  35  43  46  48  49  51  53  64  65  73  82
  5  11  12  15  17  21  24  25  26  32  36  44  47  49  50  52  54  65  66  74  83
  6  12  13  16  18  22  25  26  27  33  37  45  48  50  51  53  55  66  67  75  84
  7  13  14  17  19  23  26  27  28  34  38  46  49  51  52  54  56  67  68  76  85
  1   8  14  15  18  20  24  27  28  29  35  39  47  50  52  53  55  57  68  69  77
  2   9  15  16  19  21  25  28  29  30  36  40  48  51  53  54  56  58  69  70  78
  3  10  16  17  20  22  26  29  30  31  37  41  49  52  54  55  57  59  70  71  79
  4  11  17  18  21  23  27  30  31  32  38  42  50  53  55  56  58  60  71  72  80
  5  12  18  19  22  24  28  31  32  33  39  43  51  54  56  57  59  61  72  73  81
  6  13  19  20  23  25  29  32  33  34  40  44  52  55  57  58  60  62  73  74  82
  7  14  20  21  24  26  30  33  34  35  41  45  53  56  58  59  61  63  74  75  83
  8  15  21  22  25  27  31  34  35  36  42  46  54  57  59  60  62  64  75  76  84
  9  16  22  23  26  28  32  35  36  37  43  47  55  58  60  61  63  65  76  77  85
  1  10  17  23  24  27  29  33  36  37  38  44  48  56  59  61  62  64  66  77  78
  2  11  18  24  25  28  30  34  37  38  39  45  49  57  60  62  63  65  67  78  79
  3  12  19  25  26  29  31  35  38  39  40  46  50  58  61  63  64  66  68  79  80
  4  13  20  26  27  30  32  36  39  40  41  47  51  59  62  64  65  67  69  80  81
  5  14  21  27  28  31  33  37  40  41  42  48  52  60  63  65  66  68  70  81  82
  6  15  22  28  29  32  34  38  41  42  43  49  53  61  64  66  67  69  71  82  83
  7  16  23  29  30  33  35  39  42  43  44  50  54  62  65  67  68  70  72  83  84
  8  17  24  30  31  34  36  40  43  44  45  51  55  63  66  68  69  71  73  84  85
  1   9  18  25  31  32  35  37  41  44  45  46  52  56  64  67  69  70  72  74  85
  1   2  10  19  26  32  33  36  38  42  45  46  47  53  57  65  68  70  71  73  75
  2   3  11  20  27  33  34  37  39  43  46  47  48  54  58  66  69  71  72  74  76
  3   4  12  21  28  34  35  38  40  44  47  48  49  55  59  67  70  72  73  75  77
  4   5  13  22  29  35  36  39  41  45  48  49  50  56  60  68  71  73  74  76  78
  5   6  14  23  30  36  37  40  42  46  49  50  51  57  61  69  72  74  75  77  79
  6   7  15  24  31  37  38  41  43  47  50  51  52  58  62  70  73  75  76  78  80
  7   8  16  25  32  38  39  42  44  48  51  52  53  59  63  71  74  76  77  79  81
  8   9  17  26  33  39  40  43  45  49  52  53  54  60  64  72  75  77  78  80  82
  9  10  18  27  34  40  41  44  46  50  53  54  55  61  65  73  76  78  79  81  83
 10  11  19  28  35  41  42  45  47  51  54  55  56  62  66  74  77  79  80  82  84
 11  12  20  29  36  42  43  46  48  52  55  56  57  63  67  75  78  80  81  83  85
  1  12  13  21  30  37  43  44  47  49  53  56  57  58  64  68  76  79  81  82  84
  2  13  14  22  31  38  44  45  48  50  54  57  58  59  65  69  77  80  82  83  85
  1   3  14  15  23  32  39  45  46  49  51  55  58  59  60  66  70  78  81  83  84
  2   4  15  16  24  33  40  46  47  50  52  56  59  60  61  67  71  79  82  84  85
  1   3   5  16  17  25  34  41  47  48  51  53  57  60  61  62  68  72  80  83  85
  1   2   4   6  17  18  26  35  42  48  49  52  54  58  61  62  63  69  73  81  84
  2   3   5   7  18  19  27  36  43  49  50  53  55  59  62  63  64  70  74  82  85
  1   3   4   6   8  19  20  28  37  44  50  51  54  56  60  63  64  65  71  75  83
  2   4   5   7   9  20  21  29  38  45  51  52  55  57  61  64  65  66  72  76  84
  3   5   6   8  10  21  22  30  39  46  52  53  56  58  62  65  66  67  73  77  85
  1   4   6   7   9  11  22  23  31  40  47  53  54  57  59  63  66  67  68  74  78
  2   5   7   8  10  12  23  24  32  41  48  54  55  58  60  64  67  68  69  75  79
  3   6   8   9  11  13  24  25  33  42  49  55  56  59  61  65  68  69  70  76  80
  4   7   9  10  12  14  25  26  34  43  50  56  57  60  62  66  69  70  71  77  81
  5   8  10  11  13  15  26  27  35  44  51  57  58  61  63  67  70  71  72  78  82
  6   9  11  12  14  16  27  28  36  45  52  58  59  62  64  68  71  72  73  79  83
  7  10  12  13  15  17  28  29  37  46  53  59  60  63  65  69  72  73  74  80  84
  8  11  13  14  16  18  29  30  38  47  54  60  61  64  66  70  73  74  75  81  85
  1   9  12  14  15  17  19  30  31  39  48  55  61  62  65  67  71  74  75  76  82
  2  10  13  15  16  18  20  31  32  40  49  56  62  63  66  68  72  75  76  77  83
  3  11  14  16  17  19  21  32  33  41  50  57  63  64  67  69  73  76  77  78  84
  4  12  15  17  18  20  22  33  34  42  51  58  64  65  68  70  74  77  78  79  85
  1   5  13  16  18  19  21  23  34  35  43  52  59  65  66  69  71  75  78  79  80
  2   6  14  17  19  20  22  24  35  36  44  53  60  66  67  70  72  76  79  80  81
  3   7  15  18  20  21  23  25  36  37  45  54  61  67  68  71  73  77  80  81  82
  4   8  16  19  21  22  24  26  37  38  46  55  62  68  69  72  74  78  81  82  83
  5   9  17  20  22  23  25  27  38  39  47  56  63  69  70  73  75  79  82  83  84
  6  10  18  21  23  24  26  28  39  40  48  57  64  70  71  74  76  80  83  84  85
  1   7  11  19  22  24  25  27  29  40  41  49  58  65  71  72  75  77  81  84  85
  • Lösung 2
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21
  1   2   3   4   5  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37
  1   2   3   4   5  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53
  1   2   3   4   5  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69
  1   2   3   4   5  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85
  1   6   7   8   9  22  23  24  25  38  39  40  41  54  55  56  57  70  71  72  73
  1   6   7   8   9  26  27  28  29  42  43  44  45  58  59  60  61  74  75  76  77
  1   6   7   8   9  30  31  32  33  46  47  48  49  62  63  64  65  78  79  80  81
  1   6   7   8   9  34  35  36  37  50  51  52  53  66  67  68  69  82  83  84  85
  1  10  11  12  13  22  23  24  25  42  43  44  45  62  63  64  65  82  83  84  85
  1  10  11  12  13  26  27  28  29  38  39  40  41  66  67  68  69  78  79  80  81
  1  10  11  12  13  30  31  32  33  50  51  52  53  54  55  56  57  74  75  76  77
  1  10  11  12  13  34  35  36  37  46  47  48  49  58  59  60  61  70  71  72  73
  1  14  15  16  17  22  23  24  25  50  51  52  53  58  59  60  61  78  79  80  81
  1  14  15  16  17  26  27  28  29  46  47  48  49  54  55  56  57  82  83  84  85
  1  14  15  16  17  30  31  32  33  42  43  44  45  66  67  68  69  70  71  72  73
  1  14  15  16  17  34  35  36  37  38  39  40  41  62  63  64  65  74  75  76  77
  1  18  19  20  21  22  23  24  25  46  47  48  49  66  67  68  69  74  75  76  77
  1  18  19  20  21  26  27  28  29  50  51  52  53  62  63  64  65  70  71  72  73
  1  18  19  20  21  30  31  32  33  38  39  40  41  58  59  60  61  82  83  84  85
  1  18  19  20  21  34  35  36  37  42  43  44  45  54  55  56  57  78  79  80  81
  2   6  10  14  18  22  26  30  34  38  42  46  50  54  58  62  66  70  74  78  82
  2   6  10  14  18  23  29  33  37  39  43  47  51  55  59  63  67  71  75  79  83
  2   6  10  14  18  24  28  32  36  40  44  48  52  56  60  64  68  72  76  80  84
  2   6  10  14  18  25  27  31  35  41  45  49  53  57  61  65  69  73  77  81  85
  2   7  11  15  19  22  26  30  34  39  43  47  51  56  60  64  68  73  77  81  85
  2   7  11  15  19  25  27  31  35  40  44  48  52  55  59  63  67  70  74  78  82
  2   7  11  15  19  24  28  32  36  41  45  49  53  54  58  62  66  71  75  79  83
  2   7  11  15  19  23  29  33  37  38  42  46  50  57  61  65  69  72  76  80  84
  2   8  12  16  20  22  26  30  34  40  44  48  52  57  61  65  69  71  75  79  83
  2   8  12  16  20  25  27  31  35  39  43  47  51  54  58  62  66  72  76  80  84
  2   8  12  16  20  24  28  32  36  38  42  46  50  55  59  63  67  73  77  81  85
  2   8  12  16  20  23  29  33  37  41  45  49  53  56  60  64  68  70  74  78  82
  2   9  13  17  21  22  26  30  34  41  45  49  53  55  59  63  67  72  76  80  84
  2   9  13  17  21  25  27  31  35  38  42  46  50  56  60  64  68  71  75  79  83
  2   9  13  17  21  24  28  32  36  39  43  47  51  57  61  65  69  70  74  78  82
  2   9  13  17  21  23  29  33  37  40  44  48  52  54  58  62  66  73  77  81  85
  3   6  11  17  20  22  27  32  37  40  43  46  53  56  59  62  69  72  75  78  85
  3   6  11  17  20  23  28  31  34  39  44  49  50  55  60  65  66  71  76  81  82
  3   6  11  17  20  24  29  30  35  38  45  48  51  54  61  64  67  70  77  80  83
  3   6  11  17  20  25  26  33  36  41  42  47  52  57  58  63  68  73  74  79  84
  3   7  10  16  21  22  27  32  37  39  44  49  50  54  61  64  67  73  74  79  84
  3   7  10  16  21  23  28  31  34  40  43  46  53  57  58  63  68  70  77  80  83
  3   7  10  16  21  24  29  30  35  41  42  47  52  56  59  62  69  71  76  81  82
  3   7  10  16  21  25  26  33  36  38  45  48  51  55  60  65  66  72  75  78  85
  3   8  13  15  18  22  27  32  37  38  45  48  51  57  58  63  68  71  76  81  82
  3   8  13  15  18  23  28  31  34  41  42  47  52  54  61  64  67  72  75  78  85
  3   8  13  15  18  24  29  30  35  40  43  46  53  55  60  65  66  73  74  79  84
  3   8  13  15  18  25  26  33  36  39  44  49  50  56  59  62  69  70  77  80  83
  3   9  12  14  19  22  27  32  37  41  42  47  52  55  60  65  66  70  77  80  83
  3   9  12  14  19  23  28  31  34  38  45  48  51  56  59  62  69  73  74  79  84
  3   9  12  14  19  24  29  30  35  39  44  49  50  57  58  63  68  72  75  78  85
  3   9  12  14  19  25  26  33  36  40  43  46  53  54  61  64  67  71  76  81  82
  4   6  12  15  21  22  28  33  35  40  42  49  51  57  59  64  66  71  74  80  85
  4   6  12  15  21  23  27  30  36  39  45  46  52  54  60  63  69  72  77  79  82
  4   6  12  15  21  24  26  31  37  38  44  47  53  55  61  62  68  73  76  78  83
  4   6  12  15  21  25  29  32  34  41  43  48  50  56  58  65  67  70  75  81  84
  4   7  13  14  20  22  28  33  35  39  45  46  52  55  61  62  68  70  75  81  84
  4   7  13  14  20  23  27  30  36  40  42  49  51  56  58  65  67  73  76  78  83
  4   7  13  14  20  24  26  31  37  41  43  48  50  57  59  64  66  72  77  79  82
  4   7  13  14  20  25  29  32  34  38  44  47  53  54  60  63  69  71  74  80  85
  4   8  10  17  19  22  28  33  35  38  44  47  53  56  58  65  67  72  77  79  82
  4   8  10  17  19  23  27  30  36  41  43  48  50  55  61  62  68  71  74  80  85
  4   8  10  17  19  24  26  31  37  40  42  49  51  54  60  63  69  70  75  81  84
  4   8  10  17  19  25  29  32  34  39  45  46  52  57  59  64  66  73  76  78  83
  4   9  11  16  18  22  28  33  35  41  43  48  50  54  60  63  69  73  76  78  83
  4   9  11  16  18  23  27  30  36  38  44  47  53  57  59  64  66  70  75  81  84
  4   9  11  16  18  24  26  31  37  39  45  46  52  56  58  65  67  71  74  80  85
  4   9  11  16  18  25  29  32  34  40  42  49  51  55  61  62  68  72  77  79  82
  5   6  13  16  19  22  29  31  36  40  45  47  50  55  58  64  69  72  74  81  83
  5   6  13  16  19  23  26  32  35  39  42  48  53  56  61  63  66  71  77  78  84
  5   6  13  16  19  24  27  33  34  38  43  49  52  57  60  62  67  70  76  79  85
  5   6  13  16  19  25  28  30  37  41  44  46  51  54  59  65  68  73  75  80  82
  5   7  12  17  18  22  29  31  36  39  42  48  53  54  59  65  68  70  76  79  85
  5   7  12  17  18  23  26  32  35  40  45  47  50  57  60  62  67  73  75  80  82
  5   7  12  17  18  24  27  33  34  41  44  46  51  56  61  63  66  72  74  81  83
  5   7  12  17  18  25  28  30  37  38  43  49  52  55  58  64  69  71  77  78  84
  5   8  11  14  21  22  29  31  36  38  43  49  52  56  61  63  66  73  75  80  82
  5   8  11  14  21  23  26  32  35  41  44  46  51  55  58  64  69  70  76  79  85
  5   8  11  14  21  24  27  33  34  40  45  47  50  54  59  65  68  71  77  78  84
  5   8  11  14  21  25  28  30  37  39  42  48  53  57  60  62  67  72  74  81  83
  5   9  10  15  20  22  29  31  36  41  44  46  51  57  60  62  67  71  77  78  84
  5   9  10  15  20  23  26  32  35  38  43  49  52  54  59  65  68  72  74  81  83
  5   9  10  15  20  24  27  33  34  39  42  48  53  55  58  64  69  73  75  80  82
  5   9  10  15  20  25  28  30  37  40  45  47  50  56  61  63  66  70  76  79  85

Zyklische Darstellung

[Bearbeiten | Quelltext bearbeiten]

Es existiert eine zyklische Darstellung (Singer-Zyklus) für Lösung 1 dieses Blockplans, sie ist isomorph zur obigen Liste der Blöcke. Ausgehend von dem dargestellten Block erhält man die restlichen Blöcke des Blockplans durch zyklische Permutation der in ihm enthaltenen Punkte.

  • Lösung 1
  1   2   8  12  20  23  25  26  28  30  41  42  50  59  66  72  73  76  78  82  85

Ein Oval des Blockplans ist eine Menge seiner Punkte, von welcher keine drei auf einem Block liegen. Hier ist ein Beispiel eines Ovals maximaler Ordnung für jede Lösung dieses Blockplans:

  • Lösung 1
  1   2
  • Lösung 2
  7  30  53  61

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Rudolf Mathon, Alexander Rosa: 2-(ν, κ, λ) Designs of Small Order. In: Charles J. Colbourn, Jeffrey H. Dinitz (Hrsg.): Handbook of Combinatorial Designs. 2nd Edition. Chapman & Hall/CRC, Boca Raton FL u. a. 2007, ISBN 978-1-4200-1054-1, S. 25–57.