Is it possible to place every one of the following numbers 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , … , 2 5 2 , 2 6 2 , 2 7 2 into either of the two regions A and B below such that the sums of the numbers in each region are equal?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
How did you construct this solution?
Log in to reply
I edited my solution to include a description of the algorithm I used.
I think it is little easy way to find A, B. By using " ( 4 k ) 2 − ( 4 k + 1 ) 2 − ( 4 k + 2 ) 2 + ( 4 k + 3 ) 2 = 4 "
By this way,
2 4 2 − 2 5 2 − 2 6 2 + 2 7 2
= 2 0 2 − 2 1 2 − 2 2 2 + 2 3 2
= 1 6 2 − 1 7 2 − 1 8 2 + 1 9 2
= 1 2 2 − 1 3 2 − 1 4 2 + 1 5 2
= 8 2 − 9 2 − 1 0 2 + 1 1 2
= 4
And, considering about " ( o d d ) 2 ≡ 1 ( m o d 8 ) "
1 , 4 , 9 , 1 6 , 2 5 , 3 6 , 4 9 : 1 , 4 , 1 , 0 , 1 , 4 , 1 ( m o d 8 ) ⇒ 1 + 9 + 2 5 + 4 9 − 4 − 1 6 − 3 6 > 2 0 so unable
1 4 9 1 6 2 5 3 6 4 9 6 4 8 1 1 0 0 1 2 1 : 1 4 1 0 1 4 1 0 1 4 1 ( m o d 8 ) => 1 2 1 − 8 1 − 4 9 − 2 5 − 9 − 1 = − 4 4 ( i d e a : 1 − 1 − 1 − 1 − 1 ≡ 4 ( m o d 8 ) )
so − 4 4 + 1 0 0 − 6 4 + 3 6 − 4 − 1 6 = 8 and
2 4 2 − 2 5 2 − 2 6 2 + 2 7 2 - 2 0 2 − 2 1 2 − 2 2 2 + 2 3 2 - 1 6 2 − 1 7 2 − 1 8 2 + 1 9 2 - 1 2 2 − 1 3 2 − 1 4 2 + 1 5 2 = − 8
so we can find!!
1 1 2 − 9 2 − 7 2 − 5 2 − 3 2 − 1 2 + 1 0 2 − 8 2 + 6 2 − 4 2 − 2 2 + 2 4 2 − 2 5 2 − 2 6 2 + 2 7 2
− ( 2 0 2 − 2 1 2 − 2 2 2 + 2 3 2 ) − ( 1 6 2 − 1 7 2 − 1 8 2 + 1 9 2 ) − ( 1 2 2 − 1 3 2 − 1 4 2 + 1 5 2 ) = 0
Two more solutions:
First one is put 15 and all even numbers other than 6 into A, and 6 with all odd numbers other than 15 into B. That is:
15^2 + 2^2 + 4^2 + 8^2 + 10^2 + ... + 26^2 = 6^2 + 1^2 +3^2 + 5^2 + 7^2 + 9^2 + 11^2 + 13 ^2 + 17^2 + ... + 27^2
Second one is put 17 and all even numbers other than 10 into A, and 10 with all odd numbers other than 17 into B. That is:
17^2 + 2^2 + 4^2 + 6^2 + 8^2 + 12^2 + ... + 26^2 = 10^2 + 1^2 +3^2 + 5^2 + 7^2 + 9^2 + 11^2 + 13 ^2 + 15^2 + 19^2 + ... + 27^2
Nice! How did you construct these, Wei?
Log in to reply
I used modular 4 math. Since the sum of 1^2 to 27^2 is 6930, half of it is 3465, which is 1(mod 4). We know odd number squared is 1(mod4), and even number squared is 0(mod4). Suppose A region is the one with less odd numbers in it, then the number of odd numbers there has to be either 1 or 5.
For the case of one odd numbers in A, I just need to check 14 cases, from 1,3,... to 27. Since Sum of all even squared is 3276, to get to the desired sum of 3465, we have to start at 15, as 13^2<(3465-3279). Then it's easy to see that 15 and 17 works. Actually, we can generate a third solution from the second solution, by swapping 6,8 in A with 10 in B, as 6^2 + 8^2 =10^2.
For the case of 5 odd numbers in A, Jesse's solution is one of them. I don't know if there are other ones, or an easy way to check, there are a lot of combinations, selecting 5 out of 14.
Log in to reply
Couldn't half of 2(mod4) be 3(mod4) as well? 6 is 2(mod4) but half 6 is 3, or 3(mod4)?
I'm really asking a question, not challenging your solution. I'm not very familiar with modular arithmetic.
Log in to reply
@Dylan Torrance – Yeah, you're right. So I can not use that argument to show the sum of A has to be 1(mod4). Instead, we can compute the sum of A to be 3465, and it is indeed 1(mod4). So the end result still stands, namely: "Suppose A region is the one with less odd numbers in it, then the number of odd numbers there has to be either 1 or 5."
I've edited my comment to reflect the change.
Log in to reply
@Wei Chen – Ok, I knew 3465 was 1(mod4), I just wasn't sure if there was some kind of rule in modular arithmetic that I wasn't familiar with. The solution looks good! Having just 14 possible solutions to check leaves much less to the luck of brute force than Jesse's. :)
But how do u know which one to put in what?
Log in to reply
Good question Swapan Das. Here's what I would do: first decide that if 2n goes in A, then 2n+1 goes in B, and vice versa. Then it turns into the question of making
± 1 ± 5 ± 9 . . . ± 5 3
equal to zero by appropriate choices of pluses and minuses, etc.
I realized that in order for A=B, both A and B need to be half of the sum of all numbers. I calculated (using an excel spreadsheet) that the sum is 6930 => A=B=6930/2=3465.
I then used the largest numbers , their sum not exceeding 3465, to find 27^2 + 26^2 + 25^2 + 24^2 + 23^2 = 529 + 576 + 625 + 676 + 729 = 3135 Then using the smaller numbers, I was able to find the missing 330; 2^2 + 6^2 + 11^2 + 13^2 = 4 + 36 + 121 + 169 = 330
From here it follows that the remaining numbers will also add up to 3465. Hence the answer is "Yes, it is possible".
I'd like to note that I was just quickly trying to see if it was possible to get a quick answer this way, which turned out to be possible, but I wouldn't know where to start a proof if it hadn't been possible, and would be curious to know if there is a more elegant solution. As well as that I'm curious to know how many possibilities there are!
A) 9 + 16 + 25 + 49 + 64 + 81 + 100 + 121 + 144 + 169 + 196 + 225 + 256 + 324 + 361 + 400 + 441 + 484
B) 1 + 4 + 36 + 289 + 529 + 576 + 625 + 676 + 729
How did you get this partition?
4^2 + 8 2 + 16^2 + 23^2 + 24^2 + 25^2 + 26^2 + 27^2 = 3465 = (1/2) (6930) = sum from k = 1 to k = 27 of k^2. Ed Gray
Pardon my typo, 82 should be 8^2. Ed Gray
Actually, the sum is 3471, not 3465. The number of odds has to be 1 or 5, not 3 as in your set. See my comment above.
Could you explain how you got this set?
dynamic programming for the win
True. Wanna share your code? :)
I got it as squares of numbers from 5 to 20 and 25 add to 3465.
Omg..so many solutions exist...how many?
Total instances 55626
runfile('C:/Users/Fitzgeralds/mystuff/combinations totalling X.py', wdir='C:/Users/Fitzgeralds/mystuff')
What is the low end of the integer range? : 1 What is the high end of the integer range? : 27
Target value for sum of squares split between Region A and Region B: 3465.00
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 20 21 22 24 Region B: 16 17 19 23 25 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 18 19 20 22 25 Region B: 15 17 21 23 24 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 18 21 22 24 25 Region B: 15 16 17 19 20 23 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 20 22 23 26 Region B: 15 16 17 18 21 24 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 18 19 22 24 26 Region B: 14 16 17 20 21 23 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 19 20 24 27 Region B: 14 15 17 21 22 23 25 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 17 18 23 24 26 Region B: 13 16 19 20 21 22 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 14 17 20 24 25 27 Region B: 13 15 16 18 19 21 22 23 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 14 17 21 22 26 27 Region B: 13 15 16 18 19 20 23 24 25
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 14 18 19 23 26 27 Region B: 13 15 16 17 20 21 22 24 25
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 15 16 20 23 26 27 Region B: 13 14 17 18 19 21 22 24 25
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 16 17 18 20 21 23 24 Region B: 13 14 15 19 22 25 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 16 23 25 26 27 Region B: 13 14 15 17 18 19 20 21 22 24
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 17 20 21 22 24 25 Region B: 13 14 15 16 18 19 23 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 18 19 20 23 24 25 Region B: 13 14 15 16 17 21 22 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 12 18 19 21 22 23 26 Region B: 13 14 15 16 17 20 24 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 18 22 24 27 Region B: 12 17 19 20 21 23 25 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 13 14 17 18 24 26 27 Region B: 12 15 16 19 20 21 22 23 25
Region A: 1 2 3 4 5 6 7 8 9 10 11 13 16 17 18 19 20 22 26 Region B: 12 14 15 21 23 24 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 13 17 18 21 22 24 26 Region B: 12 14 15 16 19 20 23 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 14 15 18 22 23 24 25 Region B: 12 13 16 17 19 20 21 26 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 14 15 19 21 22 24 26 Region B: 12 13 16 17 18 20 23 25 27
Region A: 1 2 3 4 5 6 7 8 9 10 11 14 16 18 21 22 23 27 Region B: 12 13 15 17 19 20 24 25 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 14 16 19 20 21 24 27 Region B: 12 13 15 17 18 22 23 25 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 14 17 18 19 22 24 27 Region B: 12 13 15 16 20 21 23 25 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 15 16 17 20 22 24 27 Region B: 12 13 14 18 19 21 23 25 26
Region A: 1 2 3 4 5 6 7 8 9 10 11 16 17 22 24 25 27 Region B: 12 13 14 15 18 19 20 21 23 26
…………………………………………
…………………………………………
…………………………………………
Region A: 11 12 15 16 17 20 21 22 23 24 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 18 19 25 26 27
Region A: 11 12 15 16 17 20 25 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 18 19 21 22 23 24
Region A: 11 12 15 17 18 19 20 21 22 26 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 16 23 24 25 27
Region A: 11 12 15 19 20 22 23 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 16 17 18 21 26 27
Region A: 11 12 16 17 21 22 23 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 15 18 19 20 26 27
Region A: 11 12 16 19 20 21 22 23 27 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 15 17 18 24 25 26
Region A: 11 12 17 18 19 21 22 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 13 14 15 16 20 23 24 27
Region A: 11 13 14 15 17 22 24 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 16 18 19 20 21 23 25
Region A: 11 13 14 15 18 20 21 22 23 24 Region B: 1 2 3 4 5 6 7 8 9 10 12 16 17 19 25 26 27
Region A: 11 13 14 15 18 20 25 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 16 17 19 21 22 23 24
Region A: 11 13 14 16 18 19 20 22 23 25 Region B: 1 2 3 4 5 6 7 8 9 10 12 15 17 21 24 26 27
Region A: 11 13 14 18 21 22 23 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 12 15 16 17 19 20 26 27
Region A: 11 13 15 18 19 22 23 24 26 Region B: 1 2 3 4 5 6 7 8 9 10 12 14 16 17 20 21 25 27
Region A: 11 13 15 18 20 21 22 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 12 14 16 17 19 23 24 27
Region A: 11 13 16 17 20 21 22 24 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 14 15 18 19 23 25 26
Region A: 11 13 16 18 19 20 23 24 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 14 15 17 21 22 25 26
Region A: 11 13 19 20 22 24 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 17 18 21 23 26
Region A: 11 14 15 16 17 18 19 21 24 26 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 20 22 23 25 27
Region A: 11 14 15 16 17 18 20 21 22 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 19 23 24 25 26
Region A: 11 14 15 18 19 20 22 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 16 17 21 23 24 26
Region A: 11 14 16 17 18 21 22 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 15 19 20 23 24 26
Region A: 11 14 17 20 23 24 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 15 16 18 19 21 22 26
Region A: 11 14 17 21 22 23 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 15 16 18 19 20 24 25
Region A: 11 15 16 17 18 19 22 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 14 20 21 23 24 25
Region A: 11 17 20 21 22 23 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 18 19 26 27
Region A: 12 13 14 15 16 17 18 19 21 22 24 Region B: 1 2 3 4 5 6 7 8 9 10 11 20 23 25 26 27
Region A: 12 13 14 15 18 19 20 21 23 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 16 17 22 24 25 27
Region A: 12 13 14 18 19 21 23 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 15 16 17 20 22 24 27
Region A: 12 13 15 16 20 21 23 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 14 17 18 19 22 24 27
Region A: 12 13 15 17 18 22 23 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 14 16 19 20 21 24 27
Region A: 12 13 15 17 19 20 24 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 14 16 18 21 22 23 27
Region A: 12 13 16 17 18 20 23 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 14 15 19 21 22 24 26
Region A: 12 13 16 17 19 20 21 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 14 15 18 22 23 24 25
Region A: 12 14 15 16 19 20 23 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 13 17 18 21 22 24 26
Region A: 12 14 15 21 23 24 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 13 16 17 18 19 20 22 26
Region A: 12 15 16 19 20 21 22 23 25 Region B: 1 2 3 4 5 6 7 8 9 10 11 13 14 17 18 24 26 27
Region A: 12 17 19 20 21 23 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 18 22 24 27
Region A: 13 14 15 16 17 20 24 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 18 19 21 22 23 26
Region A: 13 14 15 16 17 21 22 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 18 19 20 23 24 25
Region A: 13 14 15 16 18 19 23 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 17 20 21 22 24 25
Region A: 13 14 15 17 18 19 20 21 22 24 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 16 23 25 26 27
Region A: 13 14 15 19 22 25 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 16 17 18 20 21 23 24
Region A: 13 14 17 18 19 21 22 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 15 16 20 23 26 27
Region A: 13 15 16 17 20 21 22 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 14 18 19 23 26 27
Region A: 13 15 16 18 19 20 23 24 25 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 14 17 21 22 26 27
Region A: 13 15 16 18 19 21 22 23 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 14 17 20 24 25 27
Region A: 13 16 19 20 21 22 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 17 18 23 24 26
Region A: 14 15 17 21 22 23 25 26 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 19 20 24 27
Region A: 14 16 17 20 21 23 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 18 19 22 24 26
Region A: 15 16 17 18 21 24 25 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 20 22 23 26
Region A: 15 16 17 19 20 23 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 18 21 22 24 25
Region A: 15 17 21 23 24 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 18 19 20 22 25
Region A: 16 17 19 23 25 26 27 Region B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 20 21 22 24
Total instances 55626
Less than half of 1% of all possible combinations 55,626, 134,217,727, 0.04144%
Number of Comb
1 27
2 351
3 2,925
4 17,550
5 80,730
6 296,010
7 888,030
8 2,220,075
9 4,686,825
10 8,436,285
11 13,037,895
12 17,383,860
13 20,058,300
14 20,058,300
15 17,383,860
16 13,037,895
17 8,436,285
18 4,686,825
19 2,220,075
20 888,030
21 296,010
22 80,730
23 17,550
24 2,925
25 351
26 27
27 1
55,626 134,217,727
0.04144%
Log in to reply
55626 instances? If we consider only the groups and not the order of the numbers there are only 3280 posible answers. How many of this posible answers are correct answers?
Denote A(n)=n (n+1) (2n+1)/6. Then A(22)-A(10)+A(5)=3465. But A(22)-A(10)+A(5)=1^2+...+5^2+11^2+...+22^2 and thus $$1^2+...+5^2+11^2+...+22^2=6^2+...+10^2+23^2+...+27^2$$.
Problem Loading...
Note Loading...
Set Loading...
This is not a number theoric solution!
Author of this problem should post a number theoric solution since this is categorized as number theory.
We can find all solutions using the following algorithm:
Note that 3 4 6 5 is half of the sum of all of the squares given by 6 2 7 ⋅ 2 8 ⋅ 5 5 = 6 9 3 0 and hence sum of both A and B must be 3 4 6 5 .
The algorithm works because it starts with 2 7 2 in A and in each cycle it checks if the sum of the elements of A is half of the sum of all of the squares and if it is we have a solution.
Then we continue to find the other solutions.
If we have 1 2 in A we cannot continue with it there so we remove it, end the algorithm if A is empty and otherwise make the smallest square in A smaller and go back to check if we have a solution.
Now if the sum is too large, since we know that we don't have 1 2 in A , we can just make the smallest square in A smaller and go back to check if we have a solution.
Now we know that the sum is either less than or equal to the half of the sum of the squares, and since we know that we don't have 1 2 in A , we just add the largest square smaller than the smallest square in A to A and go check if we have a solution.
After only few cycles of this algorithm we find that,
2 7 2 + … + 2 3 2 + 1 7 2 + 5 2 + 4 2 = 2 2 2 + … + 1 8 2 + 1 6 2 + … 6 2 + 3 2 + 2 2 + 1 2 .
Hence the answer is Yes, it is possible .