benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / A ten-level 2-tree is drawn in the plane: a vertex A₁ is marked, it is connected by segments with two vertices B₁ and B₂, each of B₁ and B₂ is connected by segments with two of the…

Problem

Answer published by the source. Consult the official source to check your work against its answer.

problem

A ten-level 2-tree is drawn in the plane: a vertex A1A_{1} is marked, it is connected by segments with two vertices B1B_{1} and B2B_{2}, each of B1B_{1} and B2B_{2} is connected by segments with two of the four vertices C1,C2,C3,C4C_{1}, C_{2}, C_{3}, C_{4} (each CiC_{i} is connected with one BjB_{j} exactly); and so on, up to 512 vertices J1,…,J512J_{1}, \ldots, J_{512}. Each of the vertices J1,…,J512J_{1}, \ldots, J_{512} is coloured blue or golden. Consider all permutations ff of the vertices of this tree, such that (i) if XX and YY are connected with a segment, then so are f(X)f(X) and f(Y)f(Y), and (ii) if XX is coloured, then f(X)f(X) has the same colour. Find the maximum MM such that there are at least MM permutations with these properties, regardless of the colouring.
Plain-text mathematical notation (without MathML)
A ten-level 2-tree is drawn in the plane: a vertex A₁ is marked, it is connected by segments with two vertices B₁ and B₂, each of B₁ and B₂ is connected by segments with two of the four vertices C₁,C₂,C₃,C₄ (each C_(i) is connected with one B_(j) exactly); and so on, up to 512 vertices J₁,…,J₅₁₂. Each of the vertices J₁,…,J₅₁₂ is coloured blue or golden. Consider all permutations f of the vertices of this tree, such that (i) if X and Y are connected with a segment, then so are f(X) and f(Y), and (ii) if X is coloured, then f(X) has the same colour. Find the maximum M such that there are at least M permutations with these properties, regardless of the colouring.
Original LaTeX notation
A ten-level 2-tree is drawn in the plane: a vertex $A_{1}$ is marked, it is connected by segments with two vertices $B_{1}$ and $B_{2}$, each of $B_{1}$ and $B_{2}$ is connected by segments with two of the four vertices $C_{1}, C_{2}, C_{3}, C_{4}$ (each $C_{i}$ is connected with one $B_{j}$ exactly); and so on, up to 512 vertices $J_{1}, \ldots, J_{512}$. Each of the vertices $J_{1}, \ldots, J_{512}$ is coloured blue or golden. Consider all permutations $f$ of the vertices of this tree, such that (i) if $X$ and $Y$ are connected with a segment, then so are $f(X)$ and $f(Y)$, and (ii) if $X$ is coloured, then $f(X)$ has the same colour. Find the maximum $M$ such that there are at least $M$ permutations with these properties, regardless of the colouring.

Discussion

Discussion

No discussion posts on this page yet. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

See answer Answer published by the source

Artifacts

Code, notes and reproducible work shared by participants. Files are served from a separate origin.

No artifacts on this page yet. Share reproducible code or notes in a contribution. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

Source and history

task_id
26f8d592-5838-569c-9184-826f4748f206
task_key
test--26f8d592-5838-569c-9184-826f4748f206
task_revision_id
1
config / split
/ test

Official source

initial import