Number and Counting

Question

Q . Suppose that we state that a positive integer number ???? is called “special” if the set {1,2,3, . . . ,2016} can be split into ???? subsets, all of them with the same number of elements and the same sum of elements.

a) What are the smallest ???? > 1 and the largest ???? < 2016 “special” numbers? Why?

b) Which of the two numbers 336 and 672, if any, is a “special” number? Why?

Answer 1

Abhinav,

 

To answer a) you will need to know the integer divisors of 2016 to get started. Here's the easy part:

 

2016 = 2⁵ 3² 7 is the prime factorization of the number.

 

Now you can try experimenting with factors of 2016 and think about what can happen.

 

As for b), notice that 2016 = 336 × 6 and 2016 = 672 × 3. To see if either of these is special, you might want to look at the remainders when dividing by 6 and 3, respectively. I cannot guarantee that this will be part of the solution, but this problem looks like it is heavily involved with modular arithmetic.

 

I prefer not to show you how to solve this, because that is most of the effort in learning how to solve problems. You just have to try struggling with it for a while.

 

Good luck!

Answer 2

NEEDED INFORMATION:

First, note that there are 2016 elements in the set {1,2,3,…,2016}.

 

Second, note that:

 The prime factors of 2016 are:   2*2*2*2*2*3*3*7

 The prime factors of 336 are:     2*2*2*2*3*7

 The prime factors of 672 are:     2*2*2*2*2*3*7

 

Also, a very important formula is needed here—

    Gauss’ Formula for the sum of the numbers from 1 to N is:

                 Sum = N(N+1)/2

    This formula can be found by calculating twice the sum as:

       ( (1+2016)+(2+2015)+(3+2014)+…+(2016+1) )/2

        where there are 2016 sums of 2017.

        Later, we will need X sums of Y to verify that a X is “special.”

 

ANALYSIS:

 

Now, determine the characteristics of a “special” number in terms of the preceding information:

 

  -  To split 2016 elements evenly (that is, subsets with “the same number of elements”), the “special” number must have prime factors that are a subset of those of 2016.  For example, there possibly could be 2*3*7=42 subsets or 2*2*2*3=24 subsets (note: that’s only part of the definition of “special”).  There could NOTbe 3*3*3=27 subsets made from 2016 elements such that the subsets contained the same number of elements.  This establishes the first criteria and both 336 and 672 pass it – but there’s another criteria.

 

  -  Once the number of subsets has been determined, the elements (the digits from 1 to 2016) must be placed into the subsets such that the sum of their elements is the same.  This means that the sum of the elements in the set {1,2,3,…,2016} can likewise be split into the same number of subsets (working out the sums later).  The sum of the elements in the set {1,2,3…,2016} is 2016*2017/2 = 2033136 which has prime factors of 2*2*2*2*3*3*7*2017.  So, the sums of the elements in the subsets must have prime factors that are subsets of these factors.  That’s the second criteria.

 

Could the original set be “split” into 336 subsets whose sums are the same?  Each subset must contain 2016/336 = 6 elements and each sum must be 2033136/336 = 6051.  The subsets are:

    {        1,  2016,      2,  2015,       3,  2014}                [sum=6051]

    {        4,  2013,      5,  2012,       6,  2011}                [sum=6051]

       . . .

    { 1006, 1011,   1007, 1010,   1008, 1009}                [sum=6051]

        There are 336 subsets, each with a sum of 6051, so 336 is “special.”

 

Could there be 672 subsets whose sums are the same?  Each subset must contain 2016/672 = 3 elements and each sum must be 2033136/672 = 3025.5.  Sorry, we cannot “split” the original set into subsets whose sum of their elements is 3025.5, so 672 is not “special.”

 

Now, what’s the fewest number of subsets (the lowest “special” number >1)?  The choices are 2, 3, 4, 6, 7, 8, 9, …    [note: products of multiplying 2, 2, 2, 2, 2, 3, 3, 7]

 

Could there be 2 subsets whose sums are the same?  Each subset must contain 2016/2 = 1008 elements and each sum must be 2033136/2 = 1016568.  Consider thes subsets:

   {    1, 2016,      2, 2015,       3, 2014,  …   ,    502, 1515,    503, 1514,     504, 1514}

   {505, 1513,   506, 1512,    507, 1511,  …   ,  1006,1101,   1007, 1010,   1008, 1009}

     Each subset has 1008 elements whose sum is 1016568, so 2 is a “special” number.

 

Now, the largest number of subsets must have at least two elements if the sum of the elements is to be equal for each of the subsets.  So, could there be 1008 subsets whose sums are the same?  Each subset must contain 2016/1008 = 2 elements and the sum of the elements in each subset must be 2033136/1008 = 2017.  Well that’s easy if you’ve understood the answer so far.