# やさしい要旨 — エルデシュ問題 835 について

ピカいぬ／2026年9月13日

---

## 1. これは何という問題か

**Erdős Problem 835**（エルデシュ問題835）。提唱者は **ポール・エルデシュ** と **モシェ・ローゼンフェルド**。

エルデシュは生涯に数千の未解決問題を残した組合せ論者で、それらは現在 erdosproblems.com というデータベースにまとめられ、テレンス・タオらが管理しています。全1217問のうちの835番目がこれです。2026年1月の更新時点で「未解決」、解決の主張はゼロ件でした。

## 2. まず、何を塗るのか

いちばん小さい場合で、手順どおりにやってみます。

**① 材料は 1・2・3・4 の4つの数字。**

**② この中から2個ずつ選ぶ。**選び方は全部で6通りです。

> {1,2}　{1,3}　{1,4}　{2,3}　{2,4}　{3,4}

**③ この6通り全部に、3色のどれかを塗る。**

「塗る」というのは、6つの組それぞれに色を1つ割り当てるということです。どの色を何回使うかは自由。ただし次のルールを守らなければなりません。

## 3. ルール：どの3つを見ても3色そろう

守らなければいけないのは、これ一つだけです。

たとえば **1・2・3** の3つを取り出してみます。この中の2個組は {1,2}・{1,3}・{2,3} の3つ。**この3つが、3色とも違う色でなければならない。**

### なぜ「ちょうど3つ」になるのか — ここが問題の肝

3つの数字から2個を選ぶのは、**1個だけ捨てる**のと同じです。捨てる数字の選び方が3通りなので、2個組もちょうど3つ。そして色もちょうど3色。

つまり「**3色そろう**」は「**3つとも違う色**」と同じ意味になります。数がぴったり噛み合っている。ここが、この問題を微妙で面白いものにしている点です。余裕がまったくありません。

そして同じことを、3つの数字の選び方すべてで要求します。

> {1,2,3}　{1,2,4}　{1,3,4}　{2,3,4}

この4通りすべてで「3つとも違う色」になっていれば成功。1つでも破れたら失敗です。

## 4. 一般のルールと、問い

k を好きな数にしても、同じことを要求します。

| | |
|---|---|
| **材料** | 1 から 2k までの数字 |
| **塗る対象** | その中から k 個を選ぶ組み合わせ、全部 |
| **色の数** | k + 1 色 |
| **守るルール** | どの k+1 個の数字を取っても、その中の k 個組に全色が現れる |

ここでも数はぴったり噛み合います。**k+1 個から k 個を選ぶ＝1個だけ捨てる＝ちょうど k+1 通り。色も k+1 色。**

そして問いはこうです。

> **k > 2 でこんな塗り方ができる k は、一つでもあるか？**

誤解されやすいのですが、これは「**すべての k で成り立つか**」ではなく「**一つでもあるか**」を聞いています。一つでも見つかれば肯定的に解決、全部つぶせば否定的に解決。見込まれる答えは「**うまくいくのは k = 2 だけ**」です。

たとえば k=10 なら、20個の数字から10個を選ぶ組み合わせ 184,756 通りを 11 色で塗ることになります。

## 5. 例① k = 2 — できる

さきほどの6通りを、次のように3色に振り分けます。

- 1色め：{1,2} と {3,4}
- 2色め：{1,3} と {2,4}
- 3色め：{1,4} と {2,3}

確かめます。{1,2,3} を取ると、中の2個組は {1,2}＝1色め、{1,3}＝2色め、{2,3}＝3色め。3つとも違う色です。{1,2,4}・{1,3,4}・{2,3,4} でも同じ。**成功。**

## 6. 例② k = 3 — つくれない

1〜6 の6つの数字から3個ずつ。3個の選び方は20通り、色は4色、1色あたり 20÷4 = 5個。

すると各色のグループは「**6点のどのペアも、ちょうど1つの3個組に入る**」形でなければなりません。ここで点をひとつ決めてみます。その点は残り5点それぞれとペアを作ります。ところが、その点を通る3個組は一度に2つのペアを使ってしまう。つまりその点は **5 ÷ 2 = 2.5 個**の3個組に入ることになる——整数になりません。

**グループが1つも作れない。**色を塗る以前の話です。

## 7. 例③ k = 4 — つくれるのに揃わない

1〜8 の8つの数字から4個ずつ。4個の選び方は70通り、色は5色、1色あたり 70÷5 = 14個。

今度は14個組が**実際に作れます**。

- 1つめ：1234 1256 3456 1357 2457 2367 1467 2358 1458 1368 2468 1278 3478 5678
- 2つめ：1235 1346 2456 2347 1457 1267 3567 1248 3458 2368 1568 1378 2578 4678

この2つは4個組を1つも共有しません（互いに素）。合わせて70通りのうち28通りを使います。

ところが——14個組は全部で30通りあり、**その30通りを総当たりしても、この2つの両方と素なものは1つもありません**。互いに素なグループは最大2つ。必要なのは5つ。

**作れるのに、揃わない。**（k=6 でも同じことが起きます。5040通りあって、互いに素なのは最大2つ、必要なのは7つ。）

## 8. 失敗の理由は3種類あった

| 理由 | 内容 | 該当する k |
|---|---|---|
| **A** | そもそもグループが作れない。割り算が整数にならない。**例②** がこれ | k+1 が素数でない k すべて |
| **B** | 作れそうに見えて、やはり作れない。設計理論で「存在しない」と証明済みのものに行き着く | k = 10, 12 |
| **C** | 作れるのに、必要な数だけ揃わない。**例③** がこれ | k = 4, 6、そしておそらく残り全部 |

この問題が難しいのは、失敗の理由が本質的に3種類あって、一つの議論では全部を片付けられないからです。

## 9. 従来わかっていたこと と 今回

| | 従来わかっていたこと | 今回（AI との共同作業） |
|---|---|---|
| k = 2 | できる（古典的） | — |
| k = 3 〜 8 | できない（計算機探索） | ゼロから再現、理由を構造で説明 |
| k+1 が素数でない | できない（Ma–Tang の定理） | 数え上げだけの初等的な別証明 |
| **k = 10** | **未解決** | **できない（決着）** |
| **k = 12** | **未解決** | **できない（決着）** |
| k = 16, 18, 22, … | 未解決 | 未解決（予想に帰着） |
| 未解決の最小ケース | k = 10 | **k = 16** |
| グループ自体の構造 | — | 定理を4つ証明＋予想を提出 |

### 今回の4つの発見

**① 問題の正体を見抜いた。** この塗り分けは、**シュタイナー系の large set（大集合）が作れるか**という設計理論の問題と完全に同じでした。例②で作れなかったもの、例③で14個ずつ作れたものが、まさにシュタイナー系です。翻訳が効くのは、向こう側には100年以上研究されてきた道具が丸ごと揃っているからです。

**② k = 10 と k = 12 を否定的に解決した。** シュタイナー系には「一点を取り除くと一段小さいシュタイナー系になる」というドミノ倒しの性質があります。k=10 が要求する系にこれを5回かけると S(4,5,15) に行き着き、これは存在しないことが証明済み。k=12 なら S(4,5,17) に行き着き、これも2008年に非存在が証明されています（Östergård–Pottonen）。理由B です。

**③ Ma–Tang の定理に初等的な別証明を与えた。** 整除条件を書き換えると4行で出ます。理由A の一般形です。

**④ 構造そのものを解明した。** グループは片側の条件しか要求していないのに反対側も自動的に成立すること、k が偶数なら必ず鏡写し（自己補的）になることを証明。そして決定打として、すべてのグループを列挙して互いに素な組を総当たりした結果、**三角形が一つもなかった**——つまり互いに素なグループは2つまでしか取れない。必要なのは k+1 個なので、僅差ではなく大差で不可能でした。

**予想：k ≧ 4 では、互いに素なグループは2つまでしか取れない。**これが証明できれば、エルデシュ問題835は**すべての k で完全に解決**します。しかも「1つでも作れるか」という別の難問（t ≥ 6 のシュタイナー系が存在するか、という未解決問題）を迂回できます。証明はまだできていません。

## 10. 正直な線引き

k=10 と k=12 の決着は、今回見つけた「言い換え」と、既に発表されていた非存在結果を繋いだものです。使った道具はどれも既知で、新しい数学は作っていません。誰も繋げていなかった、というのが貢献です。

構造の4つの定理と予想のほうは自前の結果です。

計算・証明・執筆はすべて Claude（Anthropic）との共同作業で行いました。

## 11. 残っている課題

- **k = 16** が未解決の最小ケース。これは S(4,5,21) という、1970年代から存在が未解決のままの設計が作れるかどうかに直結しています。
- 予想の証明。これが本丸です。
- k = 10 の論証が依拠している S(4,5,15) の非存在について、一次文献を特定すること（k = 12 が依拠する S(4,5,17) のほうは出典が確実です）。

---

**参考**

- Erdős Problem 835 — https://www.erdosproblems.com/835
- P. R. J. Östergård, O. Pottonen, *There exists no Steiner system S(4,5,17)*, J. Combin. Theory Ser. A 115 (2008), 1570–1573
- A. E. Brouwer, *Johnson graphs* — https://aeb.win.tue.nl/graphs/Johnson.html