Another Divisibility Puzzle (Posted on 2006-09-25)

	Submitted by K Sengupta
Rating: 4.0000 (1 votes)
Solution:	(Hide)
(108, 117, 135, 180) constitutes the solution for Part I. (1020, 1190, 1428, 1717, 1785) constitutes the solution for Part II. EXPLANATION: At the outset, for the sum to be divisible by M of the M+1 different numbers making up the sum, it must be a different multiple of each of these numbers. But the numbers have the same number of digits and start with the same digit, so the largest is less than twice the smallest. The sum is therefore less than 2M+1 times the smallest and larger than 1 + M/2 times the largest. But in practice, we cannot use a sum less than M times the largest, because there must be M different multiples within a range of less than a factor of 2. If M-1 is included, 2M-2 and larger multiples cannot be, and the number of different multiples M-1, M, ..., 2M-3 is only M-1 numbers. And likewise we cannot have both M and 2M in our set. So we have either M through 2M-1 or M+1 through 2M as our multiples. Part I: M =3 For M=3, we must have a sum multiples of either 3, 4, 5 or 4, 5, 6 of three of our numbers. Case A: The multiples are 3, 4, 5 For sum S, the numbers are S/3, S/4, S/5, and S-S/3-S/4-S/5 = 13S/60. Alternatively, we have 12k, 13k, 15k, and 20k with sum 60k. The smallest solution is from k=9: 108 + 117 + 135 + 180 = 540 Case B: The multiples are 4, 5, 6 The numbers are S/4, S/5, S/6, and S-S/4-S/5-S/6 = 23S/60. Since this last number is more than twice S/6, there is no solution in this category. Consequently, (108, 117, 135, 180) constitutes the solution for Part I. Part II : M =4 For M=4, the multiples are either 4, 5, 6, 7 or 5, 6, 7, 8. Case A: The multiples are ( 4, 5, 6, 7) The numbers are S/4, S/5, S/6, S/7 and S-S/4-S/5-S/6 - S/7 = 101S/420. The numbers are 60k, 70k, 84k, 101k, and 105k. The smallest solution is for k=17: 1020 + 1190 + 1428 + 1717 + 1785 = 7140. Case B : The multiples are (5, 6, 7, 8) The last number is 307 S / 840, which is larger than twice S/8, so there is no solution in this category. Consequently, (1020, 1190, 1428, 1717, 1785) constitutes the solution for Part II. Addendum: If we remove the "smallest" restriction, then substituting k = 18 and 19 in Part II (Case- A) we obtain two additional sets for Part II, which are: (1080, 1260, 1512, 1818, 1890) and (1140, 1330, 1596, 1919, 1995).

	Subject	Author	Date
	re: General Observation -- program bug	Charlie	2006-09-26 23:05:17
	General Observation	K Sengupta	2006-09-25 23:48:36
	re: part 2: the only one -- part 1 variant	Charlie	2006-09-25 14:51:40
	part 2: the only one	Charlie	2006-09-25 14:37:59
	solution (part 2)	Justin	2006-09-25 13:45:01
	solution (part I)	Justin	2006-09-25 12:01:13