Numbers and boxes

Probability Level 4

The integers from 1 to 1000 (inclusive) are to be placed into boxes such that no box contains a number that is a multiple of another number in the same box.

What is the minimum number of boxes needed?

As an explicit example, the integers from 1 to 10 can be placed into 4 boxes while satisfying the condition:

Box 1 - $\{ 1 \}$
Box 2 - $\{ 2, 3, 5, 7 \}$
Box 3 - $\{ 4, 6, 9 , 10\}$
Box 4 - $\{ 8 \}$

The answer is 10.

5 solutions

H K
Mar 3, 2017

One can easily see that a solution with 10 boxes is possible with the following illustration:

Box 1:	1
Box 2:	2, 3
Box 3:	4, 5, 6, 7

...

Box 10:

512, ... , 1000

Likewise, it is not difficult to understand why 10 is the optimal number of boxes, for every power of 2 greater than 1 requires a new box as it is obviously a multiple of every smaller power of 2. Hence, 10 boxes are necessary because there are 10 different powers of 2 between 1 and 1000.

Moderator note:

As always, with finding a max/min, we need to 1) show that no higher/lower number works and 2) show that this number works.

This solution provides a clear explanation of why 1) we need at least 10 boxes, and 2) why 10 boxes is sufficient.

Nice question and solution. The way you have filled the boxes is the most elegant, but I solved it using a different arrangement. In box $n, 1 \le n \le 10$ , I placed all the positive integers $\le 1000$ which have $n - 1$ prime factors, (inclusive of multiplicity). So in box $1$ I placed $1$ alone, in box $2$ I placed all the primes, in box $3$ I placed $4, 6, 9, 10, 14, ....$ , in box $4$ I placed $8, 12, 18, 20, ...$ , and so on until in box $10$ I placed just $2^{9} = 512$ and $2^{8} \times 3 = 768$ .

Which makes me wonder: how many different ways can we arrange $1$ to $1000$ in $10$ boxes that satisfy the conditions of your question?

Brian Charlesworth - 4 years, 3 months ago

Thank you for the feedback. And I will certainly think about your new problem.

H K - 4 years, 3 months ago

I did it like that too. Felt more natural to me.

Peter van der Linden - 4 years, 3 months ago

I agree, Brian, I think you should post your comment as a solution because it's a very nice alternative interpretation!

(And please post that follow up problem as well)

Pi Han Goh - 4 years, 3 months ago

@Pi Han Goh – Looks like Jesse Nieminen has already posted that solution partition. As for the follow-up question, I first have to figure out what the answer is. If I can't, I'll post it as a discussion topic.

Brian Charlesworth - 4 years, 3 months ago

This is really a very elegant partition!

Agnishom Chattopadhyay - 4 years, 3 months ago

Jesse Nieminen
Mar 13, 2017

Clearly all of $2^0, 2^1, \ldots, 2^9$ need their own boxes and thus $10$ is the minimum.

However, by having all numbers with the same number of prime factors (not necessarily distinct) in the same box, we cannot have any of them dividing each other. We can achieve this using exactly $10$ boxes, since all numbers between $1$ and $1000$ can have at most $9$ prime factors.

Hence, the answer is $\boxed{10}$ .

There is no need to consider prime factors. For box number $n$ we simply pick all numbers $2^{n-1}, \dots, 2^n-1$ . Since $\frac{2^n-1}{2^{n-1}} < 2,$ we are sure that none of them are multiples of each other.

Arjen Vreugdenhil - 4 years, 2 months ago

You are right! This really is an elegant way to categorise all numbers.

Christopher Boo - 4 years, 2 months ago

This is the simplest and cleanest proof I have seen and with a direct method to compute the box number without factoriing. That beats the program code "solutions" for both being a proof and not a good guess, and efficiency of code that might be written. I did it the hard way with the prime multiples where each box holds all factorizations in range with the same number of factors. The number of boxes is the least n such that 2^n < N e.g. N = 1000 that can be calculated as CEILING(Log2(N)) + 1. Change the list to 2...N saves a whole box. As a math student (even with two math degrees I do not call myself a "mathematician", that honor I reserve for those who discover something new, and not just new to them) and experienced programmer I am a bit ashamed of not hitting the binary break out idea right off.

Robert DeLisle - 4 years, 2 months ago

Oh, that's a nice way to ensure that the non-divisibility condition is met.

Calvin Lin Staff - 4 years, 3 months ago

James Pigg
Mar 13, 2017

I solved this one by programming it. Here is the solution in Java.

http://tinyurl.com/PiggBoxes

I looked through the code. Correct me if I'm wrong, but what it seems to do is use the greedy algorithm approach of "check existing boxes. If none works, create a new box". This is how the explicit example of 10 was derived.

However, the greedy algorithm is only locally optimal (if we want to add 1 element to the existing boxes, then it will find the best way), but not necessarily globally optimal (maybe we want to create a new box for the element 3, even though we could place it along with 2, so that in a later stage we can place the element 9 in the box).

As such, we've found that 10 boxes would work, but do not yet know if it's the minimum . Using programming, how can we close this gap and show that no other smaller number of boxes would work?

Calvin Lin Staff - 4 years, 3 months ago

Your argument seems to be interesting about scope.

Can you please tell how to resolve it ? Thanks!

Harsh Shrivastava - 4 years, 2 months ago

What do you mean by "scope"?

Pi Han Goh - 4 years, 2 months ago

It is currently my belief that a pure coding approach cannot resolve the minimum issue, other than brute force checking. IE Show that for every arrangement of 1000 (or 512) numbers into 9 boxes, there are 2 that are a multiple of each other.

See my conversation with Greg in his solution.

Calvin Lin Staff - 4 years, 2 months ago

You did not solve it. Assuming the code is bug free, you discovered an upper bound, without any proof it is a minimum.

Robert DeLisle - 4 years, 2 months ago

Bhuvanesh Sridharan
Mar 16, 2017

The brute force method for this question is also very simple and fast. It is intuitively obvious that for the number of boxes to be minimum , it is more desirable to group largest possible numbers together as large numbers which are "close" are very less likely to be multiples of each other.

Hence we start of from 1000 and descend until we find a number where we disrupt the rule. Now for 1000 , we can group till 501. As 500x2 =1000. Similarly for 500 , we can go on till 251.

When n is even ---> we can group till n/2 +1

Where n is odd ---> we can group till (n+1)/2

Using this rule , we can easily count the groups within seconds :- (1)...1000-501
(2)...500-251
(3)...250-126 (4)...125-63 (5)...62-32 (6)...31-16 (7)...15-8 (8)...7-4 (9)...3,2 (10)...1

•There is no scope of movement of an element from a smaller set to a bigger set as it immediately violates the rule. • While moving a number from a bigger set to a smaller set does not change the number of sets (boxes) , thus serving no purpose whatsoever.

Therefore , the number of boxes in our arrangement is the least amount possible.

How do we know that this is really the minimum?

Agnishom Chattopadhyay - 4 years, 2 months ago

It's minimum considering the fact that we are grouping maximum possible elements in each set. It is important to note that we are not randomly grouping the elements but orderly descending from the highest number. Thus we are adding another box only when we strictly have to. There is no scope of movement of an element from a smaller set to a bigger set as it immediately violates the rule. While moving a number from a bigger set to a smaller set does not change the number of sets (boxes) , thus serving no purpose whatsoever. Therefore , the number of boxes in our arrangement is the least amount possible.

Bhuvanesh Sridharan - 4 years, 2 months ago

You are attempting to prove a greedy algorithm and the main idea is correct. Your reasoning could be made stronger if you justify that your solution is at least as good as the optimal solution, rather than because it couldn't be improved.

Another way to show that 10 is a minimum is to establish is: 1. Show that we must have at least 10 boxes. 2. A solution using 10 boxes is attainable.

Christopher Boo - 4 years, 2 months ago

@Christopher Boo – Thank you for replying to my solution.The proof using the powers of 2 has already been mentioned so I wanted to try something different. Isnt Justifying that the answer can't be improved further same as justifying that our answer is just as good as the optimal solution? I may be missing something here because I can't seem to find a way to add anything to my solution. Can you please help me out in refining the solution more? Thanks.

Bhuvanesh Sridharan - 4 years, 2 months ago

@Bhuvanesh Sridharan –

Isnt Justifying that the answer can't be improved further same as justifying that our answer is just as good as the optimal solution?

Unfortunately, no. You still need to justify why the solution that you have found is optimal. Without that, all your solution says is "I've found this method, but I don't know if there's a better method."

Pi Han Goh - 4 years, 2 months ago

@Bhuvanesh Sridharan – Your solution is to show that you utilise the first box, and then the second, third etc. How to be sure that maybe you can choose to not utilise the first box but you can perform better for the second or third?

Christopher Boo - 4 years, 2 months ago

Greg d'Entremont
Mar 15, 2017

Here is my Octave programming solution.

# Place each integer from 1 to 1000 into boxes containing integers that are not multiples of each other
clear;
n_start = 2;
n_end = 1000;
bin = [1];

for i=n_start:1:n_end;

   # start search at row 1
   r=1;
   i_is_not_assigned = 1;

   while( i_is_not_assigned )
      # Test to see if I've already searched all the rows
      # If I'm at the last row, add a next row,and assign i to the 1st element
      if(rows(bin)<r)                            # case of checking a row # that doesn't yet exist
         bin(r,1)=i;                             # Assign i to the first element of this newly created row
         i_is_not_assigned=0;                    # Set to false to break while loop

      # case of checking existing rows
      elseif(rows(bin)>=r)                       
         test_row = bin(r,:);                    # take one row
         test_row(test_row==0) = [];             # remove trailing zeros
         c_limit = columns(test_row);            # count elements
         mod_of_row = mod(i,[test_row]);         # take modula of each element
         has_no_multiple=not(any(mod_of_row==0));# test to see that no elements equal 0 (which implies it is a factor)

         # if no multiple, add element to end of row
         if ( has_no_multiple )
            bin(r,c_limit+1)=i;
            i_is_not_assigned = 0;
         endif
      endif

      # increment to next row if 'i' is not yet assigned to a bin
      if((i_is_not_assigned))
         r++;
      endif
   endwhile

endfor

rows(bin)
bin

You are using the greedy algorithm approach of "check existing boxes. If none works, create a new box". This is how the explicit example of 10 was derived.

As such, we've found that 10 boxes would work, but do not yet know if it's the minimum . Using programming, how can we close this gap and show that no other smaller number of boxes would work? It seems to me that the only way is to "Test all possible arrangement of up to 9 boxes and show that it doesn't work". Any other thoughts?

Calvin Lin Staff - 4 years, 2 months ago

Hi Calvin,
I see what you mean.

I can edit the code to attempt to place the next integer into a bin that has the least elements ... still it's not a full solution, but it may provide a new arrangement of those integers that satisfies the criteria.

As for a true minimization, I'll think some more. Greg

Greg d'Entremont - 4 years, 2 months ago

OK - I rewrote my script. Interestingly, I can pack all the integers from 1 to 1000 into 10 rows by 113 columns when I search for the least full row first. This is in contrast to the simple 'search from the top approach', which uses 10 rows by 299 columns.

As for the solution, as others have stated, since 2^n has at least one of the following (1,2,4,8,16,32, ..., 2^n-1) as a factor, each new 2^n will require a new box (or a new row in my program.)

As for testing the minimization, consider this: - the integers 512, 256, 128, 64, 32, 16, 8, 4, 2, and 1 already each exist in different boxes. - when 1024 is to be placed into a box, it is evenly divisible by each of the above integers, which are already in a box. - The result is that there exists no solution, other than to place 1024 into a new box.

Greg d'Entremont - 4 years, 2 months ago

As for testing the minimization, consider this: - the integers 512, 256, 128, 64, 32, 16, 8, 4, 2, and 1 already each exist in different boxes. - when 1024 is to be placed into a box, it is evenly divisible by each of the above integers, which are already in a box.

Yes, this indeed proves that we require at least 10 boxes.

However, without this reasoning, it is not clear why the code must create optimal partitioning for the integers. While we are filling in the box with the least number of partitions at every step, it is not necessary that this will give the optimal solution overall.

I don't know if you have actually updated your code in the solution. I ran this in octave and it still has 299 columns.

Agnishom Chattopadhyay - 4 years, 2 months ago

I didn't post the update, but what I did was that at line 42, I added a function to sort the matrix. I can post it if you want, but I don't want to enrage anyone. (See above). With the sorted matrix, it packs it into the 113 columns. It's not a solution, but I did enjoy writing the short program.

Greg d'Entremont - 4 years, 2 months ago

@Greg d'Entremont – I plan to post this as a new problem, although I am not sure of the answer.

Agnishom Chattopadhyay - 4 years, 2 months ago

Great! Thanks for analyzing the CS aspect of the problem :)

Calvin Lin Staff - 4 years, 2 months ago

I am appalled at the posting of computer programs as "solutions" to this problem without any supporting proof of the correctness of the code. Some are unclear about what constitutes proof in mathematics of which the computer science of algorithms is a subset. There are several good concise mathematical proofs posted that not only solve this puzzle for [1..1000] but solve it for [1..N] at no additional effort. Some also provide a simple explicit mapping of numbers to boxes that can be programmed much more efficiently than what the code "solutions" provide, and with the absolute assurance that the solution is correct.

Thinking comes before coding. Coding alone is not proof, it is computer assisted hand waving. A person armed with the insight shown by Vreugdenhil would not only have properly found the answer to the quiz, but found it on a basis good for any finite list of consecutive positive integers. If interested this person would also have coded and tested a box mapping program before a person writing the brute force box stuffing algorithm, that is not a proof, had managed a clean compile.

The general solution of the minimum question can be expressed as CEILING(log2(N)) + 1 based on the proofs given. In words, the minimum number of boxes is the least n such that N < 2^N. (the edge case is N = 2^m, when one more box is needed compared to 2^m - 1. This requires the strict inequality, and the "+1" on the expression above.)

The most simple and effective was given elsewhere on the thread by Arjen Vreugdenhil. He observed that no integers in the interval [2^(n-1), 2^n - 1] (n> 1) can divide each other, thus these intervals define a suitable box and its contents. The interval [1,1000] can be covered by 10 of these disjoint intervals with with n = 1..10 (with a few left over from 1001 to 1023). This puts every integer into one of 10 distinct boxes and establishes that none in a box is a multiple of another. That each of 10 powers of 2 starting with 1 = 2^0 to 512 = 2^9 must have a distinct box establishes that this 10 is also the minimum. Box number for each integer, x, is given directly by CEILING(log2(x)) + 1. So this one works well as a proof and is very constructive when the actual mapping can be computed trivially.

Before answering at the website I worked it the hard way with boxes defined as groups of integers having the same number of prime factors. It is more work as a proof, and much more work to code to compute the box numbers.

Robert DeLisle - 4 years, 2 months ago

# https://brilliant.org/weekly-problems/2017-03-13/intermediate/?problem=numbers-and-boxes
import sys
sys.setrecursionlimit(5000)   
def divisors(i, x, div_c):
    if i > 0:
        if i > 1:
            div =  [j for j in range(1,i+1) if i%j == 0]
        else:
            div =  [j for j in range(1,i+1) if i%j == 0]

        if max(div) in sorted(div_c)[::-1]:
            x = x+1
            globals()['Box%s' %x] = [i]
            if i > 2:
                div_c = []       
        else:
            globals()['Box%s' %x].append(i)

        if len(div) > 1 and div[-2] not in div_c :
            div_c.append(div[-2])
        if len(div) <= 1 and div[-1] not in div_c :
            div_c.append(div[-1])       
        divisors(i-1, x, div_c)
    else:
        for i in range(1,x+1):
           print 'Box%s:\t' %i, sorted(eval('Box%s' %i))
           print

max_int = 1000
Box = 1
Box1 = [max_int]
div_complete = []
div =  [j for j in range(1,max_int+1) if max_int%j == 0]
if len(div) > 1:
    div_complete.append(div[-2])
else:
    div_complete.append(div[-1])
divisors(max_int-1, Box, div_complete)

Box1:   [501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000]

Box2:   [251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500]

Box3:   [126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250]

Box4:   [63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125]

Box5:   [32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62]

Box6:   [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]

Box7:   [8, 9, 10, 11, 12, 13, 14, 15]

Box8:   [4, 5, 6, 7]

Box9:   [2, 3]

Box10:  [1]

Michael Fitzgerald - 3 years, 1 month ago

replace variable max_int (currently 1000) with another value within recursion limit to recalculate. Max value I could calculate on my machine = 3880

Michael Fitzgerald - 3 years, 1 month ago

Numbers and boxes

The answer is 10.

5 solutions

Moderator note:

0 pending reports