Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

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

Revision en1, by debugging_since_epoch, 2023-09-22 13:48:41

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 hypercube Q_n.A hypercube 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 : https://hsin.hr/coci/archive/2021_2022/contest2_solutions.zip

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

History

 
 
 
 
Revisions
 
 
  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)