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

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


here is the problem :

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

editorial :

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!

Tags coci, help, proof


  Rev. Lang. By When Δ Comment
en3 English debugging_since_epoch 2023-09-27 19:19:25 0 (published)
en2 English 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 English debugging_since_epoch 2023-09-22 13:48:41 1136 Initial revision (published)