How many cuts are necessary to cut an n x n x n cube into 1 x 1 x 1 cubes? Existing cuboids may be stacked together for cutting. So one cut may go through multiple existing cuboids.

Source

Do not remember.

Solution

For the general a x b x c cuboid, we need f(a) + f(b) + f(c) cuts, where f(y) = ⌈ log y / log 2 ⌉. This can be proved by induction. Note that at any point, the "largest" cuboid requires the most steps; others can be sliced in parallel with this cuboid. When the "largest" cuboid has dimensions a x b x c, there are exactly 3 choices: to slice along one of the three sides. For a lying in the range (2^i, 2^(i+1)], any cut that results in the new "largest cuboid" being z x b x c, where z lies in the range (2^(i-1), 2^i], is optimal. This is because f(z) for all these z's is identical. For example, for 10 x 34 x 98 cuboid, any of the following could be the maximal cuboid for the remaining steps:

5 x 34 x 100
6 x 34 x 100
7 x 34 x 100
8 x 34 x 100
10 x 17 x 100
10 x 18 x 100
10 x 19 x 100
... and so on till
10 x 32 x 100
10 x 34 x 49
10 x 34 x 50
10 x 34 x 51
10 x 34 x 52
.. and so on till
10 x 34 x 64.

Shankar chooses a number uniformly at random between 1 and 1000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. If Geeta's guess is larger than the number, Shankar replaces the number with another number chosen uniformly at random [1, 1000]. What should Geeta's strategy be?

A goblin forewarns N gnomes as follows: "Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free." The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy?