15th Mexico 2001 Problem B3 A collector of rare coins has coins of denominations 1, 2, ... , n (several coins for each denomination). He wishes to put the coins into 5 boxes so that: (1) in each box there is at most one coin of each denomination; (2) each box has the same number of coins and the same denomination total; (3) any two boxes contain all the denominations; (4) no denomination is in all 5 boxes. For which n is this possible?
n = 10, 15, 20, 25, ... Solution Suppose box A has n-k coins. Then all the boxes must have n-k coins, by (2). The sum of the k denominations not in box A must be the same as the corresponding sum for any other box, so k > 1. By (3), the k denominations not in box A must be in every other box. Similarly for the other boxes. So each box contains the 4k denominations that are excluded from one of the other boxes. So the total number of coins must be 5k. So n must be a multiple of 5 and at least 10. Now for n = 10k, we can take the first 2k columns below to give the coins excluded from each box. A: 1, 10; 11, 20; 21, 30; 31, 40; ... B: 2, 9; 12, 19; 22, 29; 32, 39; ... C: 3, 8; 13, 18; 23, 28; 33, 38; ... D: 4, 7; 14, 17; 24, 27; 34, 37; ... E: 5, 6; 15, 16; 25, 26; 35, 36; ... Similarly, for n = 10k + 5, we can take the first 2k+1 columns below to give the coins excluded from each box. A: 1, 8, 15; 16, 25; 26, 35; ... B: 2, 9, 13; 17, 24; 27, 34; ... C: 3, 10, 11; 18, 23; 28, 33; ... D: 4, 6, 14; 19, 22; 29, 32; ... E: 5, 7, 12; 20, 21; 30, 31; ... For example, for n = 15, we take A = (2,3,4,5,6,7,9,10,11,12,13,14) B = (1,3,4,5,6,7,8,10,11,12,14,15) C = (1,2,4,5,6,7,8,9,12,13,14,15) D = (1,2,3,5,7,8,9,10,11,12,13,15) E = (1,2,3,4,6,8,9,10,11,13,14,15). 15th Mexican 2001 © John Scholes jscholes@kalva.demon.co.uk 9 March 2004 Last corrected/updated 9 Mar 04