[#P2900] Gathering the frog game at the root of a full binary tree

A mathematical schematic of Gathering the frog game at the root of a full binary tree. — A statement-only illustration of the mathematical objects and operations in this problem.

Problem. For an integer \(h\ge3\), let \(T_h\) be the rooted full binary tree with levels \(0,1,\ldots,h\), so every vertex below level \(h\) has two children. Initially place one frog at every vertex. A legal move chooses occupied vertices \(u\ne v\), lets \(f\) be the number of frogs at \(u\), requires the graph distance \(d(u,v)=f\), and moves all \(f\) frogs from \(u\) to \(v\). Can a finite sequence of legal moves gather all \(2^{h+1}-1\) frogs at the root for every \(h\ge3\)?

1Context

Successful reductions seem to reuse small local move patterns. A library indexed by subtree height, boundary frog counts, and resulting root loads could turn isolated searches into an inductive proof.

2Definitions

Definition 1. Graph distance in a tree is the number of edges in the unique path between two vertices.

Definition 2. An occupied vertex contains at least one frog; the destination must already be occupied immediately before the move.

3What counts as a solution

Give a construction of a legal move sequence for every h>=3, with a proof that the recursive construction terminates at the root, or exhibit a height h and an invariant proving that no root-gathering sequence exists.
For any individual-height computation, provide the complete move list and replay it with exact frog counts and graph distances; finite height checks alone do not settle the universal target.

1Status

Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: The MathOverflow and Mathematics Stack Exchange versions have no answers. The source reports explicit reductions for heights 3 through 19 but no uniform construction, and the later exact-title search found no resolution. Exact unresolved remainder: Give a construction of a legal move sequence for every h>=3, with a proof that the recursive construction terminates at the root, or exhibit a height h and an invariant proving that no root-gathering sequence exists. For any individual-height computation, provide the complete move list and replay it with exact frog counts and graph distances; finite height checks alone do not settle the universal target.^[1][2][3]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 Unresolved in this packet after the dated source check. Strongest checked result: The MathOverflow and Mathematics Stack Exchange versions have no answers. The source reports explicit reductions for heights 3 through 19 but no uniform construction, and the later exact-title search found no resolution. Exact unresolved remainder: Give a construction of a legal move sequence for every h>=3, with a proof that the recursive construction terminates at the root, or exhibit a height h and an invariant proving that no root-gathering sequence exists. For any individual-height computation, provide the complete move list and replay it with exact frog counts and graph distances; finite height checks alone do not settle the universal target.^[1][2][3] Relevance to this problem For Gathering the frog game at the root of a full binary tree, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3 Details The packet's cited sources and equivalent formulations were checked in the dated review recorded below. Strongest checked result: The MathOverflow and Mathematics Stack Exchange versions have no answers. The source reports explicit reductions for heights 3 through 19 but no uniform construction, and the later exact-title search found no resolution. Exact unresolved remainder: Give a construction of a legal move sequence for every h>=3, with a proof that the recursive construction terminates at the root, or exhibit a height h and an invariant proving that no root-gathering sequence exists. For any individual-height computation, provide the complete move list and replay it with exact frog counts and graph distances; finite height checks alone do not settle the universal target. Open full record →
	Trace	Reported
attempt · Route 1 Give a construction of a legal move sequence for every h>=3, with a proof that the recursive construction terminates at the root, or exhibit a height h and an invariant proving that no root-gathering sequence exists. For any individual-height computation, provide the complete move list and replay it with exact frog counts and graph distances; finite height checks alone do not settle the universal target.^[1] Relevance to this problem Gives the next worker a direct completion target while separating partial progress from a full answer. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Work against the displayed statement and preserve every hypothesis and quantifier. Give a construction of a legal move sequence for every h>=3, with a proof that the recursive construction terminates at the root, or exhibit a height h and an invariant proving that no root-gathering sequence exists. For any individual-height computation, provide the complete move list and replay it with exact frog counts and graph distances; finite height checks alone do not settle the universal target. Any computation must retain a replayable witness and a matching exclusion or completeness certificate. Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-27. The MathOverflow and Mathematics Stack Exchange versions have no answers. The source reports explicit reductions for heights 3 through 19 but no uniform construction, and the later exact-title search found no resolution.

On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for MathOverflow question 370694; the page has no comments containing a hidden solution.
The Mathematics Stack Exchange precursor gives the same formal move rules and remains unanswered in the checked snapshot.
A 2022 thesis cites both question pages and discusses the game, but the available search extract did not claim a proof for every binary-tree height.
A TheoremDB search for lazy toad, frog game, full binary tree, and root-solvable move sequences found no duplicate.
Independent source, duplicate, exact-title, and equivalent-formulation review completed on 2026-08-01.

Recorded example 1. The source reports hand-checked root solutions for every height from 3 through 19; height 2 is excluded from the conjectured family.

Computational notes

At height 19 the tree has 2^20-1 vertices, yet the reported reductions use local patterns involving at most 31 vertices. Height 20 was the first case requiring a larger pattern in that exploration.

2See also

Winner complexity of Node Kayles on subcubic treescombinatorial games
Planar drums whose spectra differ only finitelymathoverflow source
Computability of the area of the Mandelbrot setmathoverflow source

How to cite

TheoremDB contributors, “Gathering the frog game at the root of a full binary tree,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/frog-game-binary-tree-root

This page as plain text: frog-game-binary-tree-root.md

This problem includes 2 records joined by 2 typed links, sourced from mathoverflow.net^[1], current as of August 1, 2026.

1References

Packet source. MathOverflow question 370694, “Gathering the frog game at the root of a full binary tree,” checked 2026-08-01. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗forum · reference source · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at Question 370694 and all visible comments, checked through the Stack Exchange API on 2026-07-27.Also cited at Full question, answers, and visible comments concerning Gathering the frog game at the root of a full binary tree; checked 2026-08-01.Also cited at Editorial research route recorded 2026-08-01.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Gathering the frog game at the root of a full binary tree: This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.Source named by the research packet.
Mathematics Stack Exchange question 3800570, related discussion for “Gathering the frog game at the root of a full binary tree,” checked 2026-08-01. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗forum · reference source · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at question statement defining the move rule and asking for root solvability at every full binary-tree height.Source used to assess the problem's recorded status.For Gathering the frog game at the root of a full binary tree, this source is an exact duplicate and discovery source whose finite experiments do not settle the universal target.
Matej Veselovac, Frog Jumping Problem on Simple Graphs, final thesis, Department of Mathematics, J. J. Strossmayer University of Osijek, 2022. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at summary and binary-tree chapter conjecturing solvability for all vertices of sufficiently large complete binary trees.Source used to assess the problem's recorded status.For Gathering the frog game at the root of a full binary tree, this source directly treats the frog game and records a conjecture rather than a proof of root solvability for every h >= 3.

This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.

[#P2900] Gathering the frog game at the root of a full binary tree

1Context

2Definitions

3What counts as a solution

1Status

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance