Ponder This Challenge - February 2001 - Kubricia's 2001 money boxes

Ponder This Challenge:

Suggested by Dieter Verhofstadt

Kubricia is a country with 2001 citizens. Each carries a different national security number from 1 to 2001. In addition, there is the King of Kubricia, Stanley the First, who has been assigned the number 0, silent witness of his modest nature.

The king has 2001 boxes stuffed with money to celebrate the year 2001. The boxes are numbered from 1 to 2001. Box number n contains (inexhaustibly many) envelopes of n Kubrician dollars each.

The King, who does not dislike a bit of math, has also divided his citizens, including himself, into two groups.

The first group passes a box. If two people in the group have national security numbers whose sum equals the number of the box, they jointly take an envelope out of the box, and each takes an amount of Kubrician dollars out of the envelope, equal to their national security number. If one citizen has a number which is half the number of the box, one can take an envelope with all n dollars for oneself. The group goes on to the next box and does accordingly. The second group does likewise.

For instance, if Mr. 1200 and Mrs. 300 are in the same group, they step forward the moment their group reaches box 1500, and take an envelope of 1500 dollars. Mr. 1200 takes 1200 dollars and Mrs 300 takes 300 dollars. Mrs. 750 passes box 1500, and takes the envelope with all 1500 dollars.

The groups are conceived so that at each box, both groups will have taken the same number of envelopes out of the box.

Question 1:

Does citizen number 2001 belong to the King's group?

Question 2:

Which citizen(s) will have received the highest amount of Kubrician dollars, once both groups have passed all boxes?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Question 1:

  Does citizen number 2001 belong to the King's group?

  Answer: No

  Group 1 = 0,2,5,6,8,11,13,14,17,18,20, ...
  Group 2 = 1,3,4,7,9,10,12,15,16,19,21, ...

  Procedure:

  Write the number in binary.
  Odd number of zero's in binary expansion: with the King.
  Even number of zero's in binary expansion: not with the King.

  2001 = 11111010001 even number of zero's.

  Lemma:

  Let n be a nonzero number and B one of the two groups.

  n is element of B (if and only if) 2n is not an element of B (if and only if) 2n+1 is an element of B.

  Proof of Lemma:

  Assign people to groups inductively, starting with 0 (automatically in Group 1) and working up. When assigning Person n, we consider the fate of envelopes in Box n. The group chosen for Person n will forced (if indeed it is possible); that is, it cannot be the case that, given the assignments so far of people 0,1,...,n-1, that Person n could either be in Group 1 or Group 2 and that either way the condition at Box n would be satisfied, since assignment to Group 1 gives one more envelope to Group 1 (0+n=n) and no change to Group 2. So we only have show that the proposed global assignment is consistent.

  Consider odd n=2k+1.
  Since (2j in group 1) iff (2j+1 in group 2), we know size(group 1 intersect {0,1,...,2k+1}) = size(group 2 intersect {0,1,...,2k+1}) = k+1. Now of the k+1 pairs of people, each of which could collect an envelope, say that B are entirely in group 1, C are entirely in group 2, and D pairs are split between the two groups. Then k+1=2B+D=2C+D, so that B=C, and the condition is satisfied at n.

  Now consider even n=2k.
  Let Person k temporarily clone himself into k' and k", and think of (k',k") as being one of the pairs of people who collects an envelope. Now there are k+1 pairs of people with numbers adding to n=2k, namely (0,2k), (1,2k-1), ..., (k-1,k+1) and (k',k"). Again the two groups are equally sized: the people in {0,1,...,2k-1} are split evenly between the two groups; there is an extra person represented by k" in one group; and the unmatched person at n=2k is in the opposite group. So each group has an intersection of size k+1 with the set {0,1,...,k-1,k',k",k+1,...,2k}.
  As before k+1=2B+D=2C+D so that B=C, and the condition is again satisfied.

  Question 2:

  Which citizen(s) will have received the highest amount of Kubrician dollars, once both groups have passed all boxes?

  Answer:

  Citizen number 997.

  Let F(n) be the amount that citizen n receives.

  If n is even, then exactly half the citizens with numbers between 0 and 2001-n are in the same group with citizen n, so that citizen n shares in (2002-n)/2 envelopes. Each such envelope gives him n dollars, except that if 2n<2001, then envelope 2n gives him an extra n dollars.
  So:
  F(n) = n*(2002-n)/2 if n is even and 2n>2001;
  F(n) = n*(2002-n)/2+n if n is even and 2n<2001.

  If n is odd, then exactly half the citizens with numbers between 0 and 2000-n are in the sane group with citizen n, so that citizen n shares in (2001-n)/2 envelopes, each giving him n dollars. As before, box 2n will give him an extra n dollars if 2n<2001. Also, box 2001 will give him an extra n dollars if citizen 2001-n is in the same group with n. Therefore:

  F(n) = n*(2001-n)/2		if n is odd, 2n>2001, and 2001-n is in the opposite group;
  F(n) = n*(2001-n)/2+n		if n is odd, 2n>2001, and 2001-n is in the same group;
  F(n) = n*(2001-n)/2+n		if n is odd, 2n<2001, and 2001-n is in the opposite group;
  F(n) = n*(2001-n)/2+2n		if n is odd, 2n<2001, and 2001-n is in the same group.

  We find that 997 is the largest odd number n in this latter group, namely 2n<2001 and (997,1004) are in the same group.
  F(997)=502488.
  Numbers n in the other groups give smaller values of F(n).

  Rocke Verser points out the following facts:

  • The King's celebration will cost his treasury a paltry KU$669132464.
    • Box #1999 will have yielded more money to the citizens than any other box. (KU$1155422)

      • Box #1919 will have yielded more envelopes to the citizens than any other box. (598)

        Colin Bown and Stephane Higueret point out that person 2001 will go broke.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Niklas Een (02.01.2001 @ 12:39 PM EDT)
• Koen Claessen (02.01.2001 @ 12:39 PM EDT)
• Aron Fay (02.01.2001 @ 1:13 PM EDT)
• Colin Bown (02.01.2001 @ 1:46 PM EDT)
• Vladamir Sedach (02.01.2001 @ 2:35 PM EDT)
• Henry Bottomley (02.01.2001 @ 3:51 PM EDT)
• Samantha Levin (02.01.2001 @ 4:55 PM EDT)
• Jonathan Wildstrom (02.01.2001 @ 5:53 PM EDT)
• Vince Lynch (02.01.2001 @ 6:03 PM EDT)
• Joseph DeVincentis (02.01.2001 @ 10:02 PM EDT)
• Yuriy Groysman (02.02.2001 @ 12:49 AM EDT)
• Keith Peters (02.02.2001 @ 2:31 AM EDT)
• Todd Pocklington (02.02.2001 @ 1:12 PM EDT)
• Ionel Santa (02.02.2001 @ 2:54 PM EDT)
• John Hamilton (02.02.2001 @ 3:58 PM EDT)
• Jack Kennedy (02.02.2001 @ 5:03 PM EDT)
• Francis Golding (02.03.2001 @ 6:38 AM EDT)
• Dan Peleg (02.03.2001 @ 9:27 AM EDT)
• Marian Olteanu (02.03.2001 @ 11:18 AM EDT)
• Dave Biggar (02.03.2001 @ 4:03 PM EDT)
• Gopika Goswami (02.03.2001 @ 5:34 PM EDT)
• David McKee (02.03.2001 @ 10:10 PM EDT)
• Rocke Verser (02.04.2001 @ 7:11 AM EDT)
• Ming Song (02.05.2001 @ 5:46 PM EDT)
• C A Subramanian (02.06.2001 @ 3:36 AM EDT)
• Stephane Higueret (02.06.2001 @ 4:38 AM EDT)
• Prithu Bharati (02.06.2001 @ 11:49 PM EDT)
• Daniel Bitin (02.07.2001 @ 8:00 AM EDT)
• Bill Daly (02.07.2001 @ 3:09 PM EDT)
• Kevin Pulo (02.07.2001 @ 5:50 PM EDT)
• Latha Boopathy (02.07.2001 @ 11:19 PM EDT)
• Breaz Ionut Marius (02.09.2001 @ 9:10 AM EDT)
• Shmuel Spiegel (02.11.2001 @ 12:04 PM EDT)
• Mohit Sauhta (02.10.2001 @ 1:52 AM EDT)
• Octavian Marasescu (02.12.2001 @ 6:55 AM EDT)
• Dharmashankar Subramanian (02.12.2001 @ 6:49 PM EDT)
• Preeti Kelkar (02.12.2001 @ 8:06 PM EDT)
• Christie Bolton (02.13.2001 @ 11:52 PM EDT)
• Shahrad Sassouni (02.14.2001 @ 1:15 PM EDT)
• Xuan Baldauf (02.15.2001 @ 2:14 AM EDT)
• Tim Edmonds (02.15.2001 @ 5:38 PM EDT)
• Ritesh Ramanand Rao Turlapaty (02.17.2001 @ 12:08 PM EDT)
• Jesus Sanz (02.20.2001 @ 5:36 AM EDT)
• Nagendra (02.20.2001 @ 9:40 AM EDT)
• Nicolas Maskens (02.20.2001 @ 10:47 AM EDT)
• Mihai Cioc (02.22.2001 @ 12:49 AM EDT)
• Frans A Buijsen (02.23.2001 @ 9:38 AM EDT)
• Nicusor Timneanu (02.23.2001 @ 10:29 AM EDT)
• Howard Kaye (02.23.2001 @ 1:50 PM EDT)
• Eden Chlamtac (02.25.2001 @ 5:19 PM EDT)
• Krishna Kumar (02.26.2001 @ 11:50 AM EDT)
• Eddie Mansu (02.26.2001 @ 12:11 PM EDT)
• Alexey Vorobyov (02.28.2001 @ 7:16 PM EDT)
• Just part A: (None)
• Stephen Merriman (02.01.2001 @ 6:17 PM EDT)
• Tao Lin (02.02.2001 @ 2:58 PM EDT)
• Anand Subramaniam (02.02.2001 @ 3:19 PM EDT)
• Larissa Netchiporouk (02.03.2001 @ 4:21 PM EDT)
• Latha B (02.04.2001 @ 11:21 AM EDT)
• Richard Doane (02.05.2001 @ 12:36 PM EDT)
• Derek Kisman (02.05.2001 @ 11:44 PM EDT)
• Bill Schwennicke (02.06.2001 @ 3:47 PM EDT)
• George Tolley (02.07.2001 @ 5:52 PM EDT)
• Johannes Schindelin (02.09.2001 @ 10:45 AM EDT)
• Marcel Isaila (02.15.2001 @ 11:37 AM EDT)