Too Many Variables!

Probability Level 5

Let A , B A, B be sets of non-negative integers, each containing exactly 10 elements, satisfying the property that any integer between 1 and 100 inclusive can be expressed as the sum of an element in A A and an element in B B ; that is, for each n ∈ { 1 , 2 , … , 100 } n \in \{1, 2, \ldots, 100\} , there exists a ∈ A a \in A and b ∈ B b \in B such that n = a + b n = a+b . How many unordered pairs of such { A , B } \{A, B\} are there?

As an explicit example, this is one solution of the possible sets: A = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } B = { 1 , 11 , 21 , 31 , 41 , 51 , 61 , 71 , 81 , 91 } . \begin{aligned} A&=& \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \\ B&=&\{1, 11, 21, 31, 41, 51, 61, 71, 81, 91\} . \end{aligned} Also, note that A = { 1 , 11 , 21 , 31 , 41 , 51 , 61 , 71 , 81 , 91 } B = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } . \begin{aligned} A&=&\{1, 11, 21, 31, 41, 51, 61, 71, 81, 91\} \\ B&=&\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}. \end{aligned} counts as the same solution as above.

Clue: Cyclotomic polynomials .


The answer is 14.

View wiki
Julian Poon by Julian Poon , 20, Singapore

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.

1 solution

Julian Poon
Nov 1, 2016

Let the numbers in Set A be a 1 , a 2 , a 3 . . . , a 10 a_1, a_2, a_3..., a_{10} and the numbers in Set B be b 1 , b 2 , b 3 . . . , b 10 b_1, b_2, b_3..., b_{10} .

Then

( ∑ n = 1 10 x a n ) ( ∑ n = 1 10 x b n ) = A ( x ) B ( x ) = ∑ n = 1 100 x n = x ⋅ x 100 − 1 x − 1 \left(\sum _{n=1}^{10}x^{a_n}\right)\left(\sum _{n=1}^{10}x^{b_n}\right)=A(x)B(x)=\sum _{n=1}^{100}x^n=x\cdot \frac{x^{100}-1}{x-1}

(Left as exercise for the reader)

So now the problem changes to how many ways are there to factor x ⋅ x 100 − 1 x − 1 x\cdot \frac{x^{100}-1}{x-1} such that A ( x ) A(x) and B ( x ) B(x) both have positive coefficients and the sum of their coefficients must equate to 10 10 .

Fully factorising x ⋅ x 100 − 1 x − 1 x\cdot \frac{x^{100}-1}{x-1} through cyclotomic polynomials gives:

x ⋅ x 100 − 1 x − 1 = x ⋅ ∏ d ∣ n , d > 1 Φ d ( x ) x\cdot \frac{x^{100}-1}{x-1}=x \cdot \prod_{d|n, d>1}\Phi_d(x) = x ( x + 1 ) ( x 2 + 1 ) ( x 4 − x 3 + x 2 − x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) ( x 8 − x 6 + x 4 − x 2 + 1 ) ( x 20 − x 15 + x 10 − x 5 + 1 ) ( x 20 + x 15 + x 10 + x 5 + 1 ) ( x 40 − x 30 + x 20 − x 10 + 1 ) =x\left(x+1\right)\left(x^2+1\right)\left(x^4-x^3+x^2-x+1\right)\left(x^4+x^3+x^2+x+1\right)\left(x^8-x^6+x^4-x^2+1\right)\left(x^{20}-x^{15}+x^{10}-x^5+1\right)\left(x^{20}+x^{15}+x^{10}+x^5+1\right)\left(x^{40}-x^{30}+x^{20}-x^{10}+1\right)

Through a systematic search, it can be found that there are 14 solutions:

  1. A = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } , B = { 1 , 11 , 21 , 31 , 41 , 51 , 61 , 71 , 81 , 91 } A=\left\{0,1,2,3,4,5,6,7,8,9\right\}, B=\left\{1,11,21,31,41,51,61,71,81,91\right\}
  2. A = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } , B = { 0 , 10 , 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 } A=\left\{1,2,3,4,5,6,7,8,9,10\right\}, B=\left\{0, 10, 20, 30, 40, 50, 60, 70, 80, 90\right\}
  3. A = { 0 , 1 , 4 , 5 , 8 , 9 , 12 , 13 , 16 , 17 } , B = { 1 , 3 , 21 , 23 , 41 , 43 , 61 , 63 , 81 , 83 } A=\left\{0,1,4,5,8,9,12,13,16,17\right\}, B=\left\{1,3,21,23,41,43,61,63,81,83\right\}
  4. A = { 1 , 2 , 5 , 6 , 9 , 10 , 13 , 14 , 17 , 18 } , B = { 0 , 2 , 20 , 22 , 40 , 42 , 60 , 62 , 80 , 82 } A=\left\{1,2,5,6,9,10,13,14,17,18\right\}, B=\left\{0,2,20,22,40,42,60,62,80,82\right\}
  5. A = { 0 , 1 , 2 , 3 , 4 , 25 , 26 , 27 , 28 , 29 } , B = { 1 , 6 , 11 , 16 , 21 , 51 , 56 , 61 , 66 , 71 } A=\left\{0,1,2,3,4,25,26,27,28,29\right\}, B=\left\{1,6,11,16,21,51,56,61,66,71\right\}
  6. A = { 1 , 2 , 3 , 4 , 5 , 26 , 27 , 28 , 29 , 30 } , B = { 0 , 5 , 10 , 15 , 20 , 50 , 55 , 60 , 65 , 70 } A=\left\{1,2,3,4,5,26,27,28,29,30\right\}, B=\left\{0,5,10,15,20,50,55,60,65,70\right\}
  7. A = { 0 , 1 , 10 , 11 , 20 , 21 , 30 , 31 , 40 , 41 } , B = { 1 , 3 , 5 , 7 , 9 , 51 , 53 , 55 , 57 , 59 } A=\left\{0,1,10,11,20,21,30,31,40,41\right\}, B=\left\{1,3,5,7,9,51,53,55,57,59\right\}
  8. A = { 1 , 2 , 11 , 12 , 21 , 22 , 31 , 32 , 41 , 42 } , B = { 0 , 2 , 4 , 6 , 8 , 50 , 52 , 54 , 56 , 58 } A=\left\{1,2,11,12,21,22,31,32,41,42\right\}, B=\left\{0,2,4,6,8,50,52,54,56,58\right\}
  9. A = { 0 , 5 , 10 , 15 , 20 , 25 , 30 , 35 , 40 , 45 } , B = { 1 , 2 , 3 , 4 , 5 , 51 , 52 , 53 , 54 , 55 } A=\left\{0,5,10,15,20,25,30,35,40,45\right\}, B=\left\{1,2,3,4,5,51,52,53,54,55\right\}
  10. A = { 1 , 6 , 11 , 16 , 21 , 26 , 31 , 36 , 41 , 46 } , B = { 0 , 1 , 2 , 3 , 4 , 50 , 51 , 52 , 53 , 54 } A=\left\{1,6,11,16,21,26,31,36,41,46\right\}, B=\left\{0,1,2,3,4,50,51,52,53,54\right\}
  11. A = { 0 , 1 , 20 , 21 , 40 , 41 , 60 , 61 , 80 , 81 } , B = { 1 , 3 , 5 , 7 , 9 , 11 , 13 , 15 , 17 , 19 } A=\left\{0,1,20,21,40,41,60,61,80,81\right\}, B=\left\{1,3,5,7,9,11,13,15,17,19\right\}
  12. A = { 1 , 2 , 21 , 22 , 41 , 42 , 61 , 62 , 81 , 82 } , B = { 0 , 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 } A=\left\{1,2,21,22,41,42,61,62,81,82\right\}, B=\left\{0,2,4,6,8,10,12,14,16,18\right\}
  13. A = { 0 , 5 , 20 , 25 , 40 , 45 , 60 , 65 , 80 , 85 } , B = { 1 , 2 , 3 , 4 , 5 , 11 , 12 , 13 , 14 , 15 } A=\left\{0,5,20,25,40,45,60,65,80,85\right\}, B=\left\{1,2,3,4,5,11,12,13,14,15\right\}
  14. A = { 1 , 6 , 21 , 26 , 41 , 46 , 61 , 66 , 81 , 86 } , B = { 0 , 1 , 2 , 3 , 4 , 10 , 11 , 12 , 13 , 14 } A=\left\{1,6,21,26,41,46,61,66,81,86\right\}, B=\left\{0,1,2,3,4,10,11,12,13,14\right\}

You can greatly reduce the workings needed for the systematic search by noting that A ( 1 ) = B ( 1 ) = 10 A(1)=B(1)=10 .

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Very nice solution! Great way to use the generating functions to express the calculations.

Using the fact that A ( 1 ) = B ( 1 ) = 10 A(1) = B(1) = 10 , we know that the terms x + 1 , x 2 + 1 x+1, x^2+1 must be in different factors. Similarly for x 4 + x 3 + x 2 + x + 1 , x 20 + x 15 + x 10 + x 5 + 1 x^4+x^3+x^2+x+1, x^{20}+x^{15}+x^{10} + x^5 + 1 . So there are 2 possible pairings of these 4 terms

Then, for the other 5 terms, they can be thrown into either pairinf, hence we have 2 5 × 2 = 64 2^5 \times 2 = 64 cases to check.

Calvin Lin Staff - 4 years, 7 months ago

Log in to reply

You can still reduce the number of cases to 32 by disregarding the x x factor when checking. This is still really tedious though. I was hoping that through posting the problem somebody could come up with an easier way.

Julian Poon - 4 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...