COCI 2021/2022 Contest 2 Problem Hiperkocka — No Proof in the editorial

Revision en3, by debugging_since_epoch, 2023-09-27 19:19:25

Statement

here is the problem : https://oj.uz/problem/view/COCI21_hiperkocka

Abridged Statement : you are given a tree T with n edges , you want to find a tiling using T on the hipercube Q_n.A hipercube with Q_i is defined as a tree such that node x and node y have an edge if and only if bitwise xor of them is a power of 2.

(please see the problem if you couldnt understood the abridged statement)

Editorial & Issue

As you can see in the editorial , it gives a construction which appearantly works but it doesnt provide a proof :/ I couldnt make sense on spesifically this paragraph :

"The rest of the trees can be placed as follows: for each x ∈ {0, . . . , 2n − 1} that has an even number of ones in binary, we take the hipercube nodes on which the first tree was placed and xor their labels with x. Notice that in such a way we obtain 2n−1 trees."

Any help and insight provided for the problem is welcomed!

History

Revisions

Rev. Lang. By When Δ Comment
en3 debugging_since_epoch 2023-09-27 19:19:25 0 (published)
en2 debugging_since_epoch 2023-09-22 13:50:22 6 Tiny change: 'T on the hypercube Q_n.A hypercube wi' -> 'T on the hipercube Q_n.A hipercube wi' (saved to drafts)
en1 debugging_since_epoch 2023-09-22 13:48:41 1136 Initial revision (published)