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

- ID: `P2900`
- Reference: `frog-game-binary-tree-root`
- Page: https://theoremdb.org/statements/P2900
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Definitions

- **Definition.** Graph distance in a tree is the number of edges in the unique path between two vertices.
- **Definition.** An occupied vertex contains at least one frog; the destination must already be occupied immediately before the move.

### What 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.

## Status

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](#reference-1) [2](#reference-2) [3](#reference-3)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

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.

- 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.

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

### Open directions

- **Route 1** (reported): 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](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `frog-game-binary-tree-root`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>MathOverflow question 370694, “Gathering the frog game at the root of a full binary tree,” checked 2026-08-01. Question 370694 and all visible comments, checked through the Stack Exchange API on 2026-07-27. https://mathoverflow.net/questions/370694/is-the-frog-game-solvable-in-the-root-of-a-full-binary-tree
   - 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.
   - forum; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>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 defining the move rule and asking for root solvability at every full binary-tree height https://math.stackexchange.com/questions/3800570/is-the-frog-game-solvable-in-the-root-of-a-full-binary-tree
   - forum; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>Matej Veselovac, Frog Jumping Problem on Simple Graphs, final thesis, Department of Mathematics, J. J. Strossmayer University of Osijek, 2022. summary and binary-tree chapter conjecturing solvability for all vertices of sufficiently large complete binary trees https://www.mathos.unios.hr/~mdjumic/uploads/diplomski/VES12.pdf
   - website; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.