problems.txt

   1 11jun2003
   2
   3 1. There are N people standing in circle, where each has a hat white or black color.
   4 No one can see own hat, but see others hats. Every exact hour (like 12:00 or 2:00) each
   5 one who knows his hat color must raise a hand. Have to be at least 1 person for each
   6 hat's color. If those N people start to be in a circle
   7 from 12:01 and at 7:00 the M of them raise hands, so how many people were?
   8
   9 answer:
  10 If there is only 1 person w/ black hat (others w/ white), so he would see others and
  11 understand that no one has black, so because should be at least one, it is him that
  12 has black hat. At 1:00 he would raise his hand and afterwise others would see that
  13 and understand that he knows that he is only one w/ black hat, so they all will raise
  14 there hands at 2:00.
  15 Now, what if 2 people have black hats. So at 1:00 nobody will raise hands. Every person
  16 w/ black hat will see it and understand that there are 2 black hat owners, so first one
  17 they see and second is himself. So at 2:00 those 2 w/ black hat would raise hands. Now
  18 others will see it and raise hands at 3:00
  19 There is algorithm that describes that if we have 3 people w/ black hat so they will
  20 raise hands at 3:00 so others at 4:00.
  21 Now, in our example M people raise hands at 7:00, so there were 7 people w/ black hats.
  22 If there are 7 people w/ white hat, so they should raise hands also at 7:00 (by the
  23 same logic that others 7), but they don't, so there are 8 and more people w/
  24 white hat.
  25
  26 2. There are levels of groups where each node have only 3 sons. Each node have
  27 two sons of one type and one of other. Father node consider to be of type which are
  28 most of his sons (if father have 2 sons of x type, so he is of x type). It is creates
  29
  30 xxy      xxy      xyy   xxy      xxy      xyy   xxy      xyy      xyy
  31  |        |        |     |        |        |     |        |        |
  32   \       |       /       \       |       /       \       |       /
  33     ----- x -----           ----- x -----           ----- y -----
  34           |                       |                       |
  35            \                      |                      /
  36              -------------------  x  -------------------
  37 tree like at the above picture. What steps should be done in order to change type of the
  38 first (head) node.
  39
  40 answer: have to change type only for one y node to x node where there were 2 y nodes.