Barbeau's Polynomials, Exploration 2

Question

I'm reading Barbeau's Polynomials.

Let $m$ be a positive integer. It is a remarkable fact that the numbers from $1$ to $2^{m+1}$ inclusive can be subdivided into two subsets $A$ and $B$ such that, for any polynomial $p(t)$ of degree not exceeding $m$, the sum of the values of the values of the polynomials over the numbers in $A$ is equal to the sum of the values over the numbers in $B$. Show that we can reduce the problem to finding sets $A$ and $B$ for which the sum of the $k$th powers of the numbers in one set is equal to the sum of the $k$th powers for the other, for $k=0,1,2,...,m$.

I'm trying to check the information given in the exercise empiricaly on Mathematica, I've created a polynomial function $f(x)=gx^2+bx+c$ and I've partitioned the set of numbers from $1$ to $2^{3+1}$ this way:

$\{2, 3, 8, 9, 10, 11, 12, 13\}$

$\{14, 6, 16, 4, 15, 5, 7, 1\}$

Now I'm trying to sum the values of the polynomial over the values on $A$ and $B$ and I'm obtaining:

$68 b + 8 c + 692 g$

$68 b + 8 c + 804 g$

I've used a polynomial of degree $>3$ and I'm not obtaining the desired result. What am I doing wrong?

You would need a partition where the squares add to the same number — tfw cant into math, Oct 28 '13 at 02:25
It's weird. He writes first that polynomials over the values of the sets $A$ and $B$ are going to yield the desired result. — Red Banana, Oct 28 '13 at 03:18
Does he actually mention that partition? Otherwise I don't understand the problem — tfw cant into math, Oct 28 '13 at 03:59

score 2 · Accepted Answer · answered Oct 28 '13 at 19:09

2

He says it is possible for you to arrange the numbers from $1$ to $16$ into sets $A$ and $B$ where any cubic polynomial's values on one sums to the sum of its values on the other. He does not say that you can use any partition. That's patently false.

On the other hand, if you look at the split

$\{1, 4, 6, 7, 10, 11, 13, 16\}, \qquad \{2, 3, 5, 8, 9, 12, 14, 15\},$

then you'll see that the sum of the $0$th powers on both sides is $8$, the first powers is $68$, the second powers is $748$, and the third powers is $9248$. Since they agree on kth powers, and polynomials are sums of kth powers, any cubic polynomial will have the desired property, i.e. the sum of its values on the first list will equal the sum of its values on the second list.

Further, you can show that this is the only way of splitting the numbers up to $16$ to have the desired property.

So to concretely answer your question: your partition would not work. Not every partition works - some very special partitions work.

answered Oct 28 '13 at 19:09

davidlowryduda

91,687

Hey! Thanks for the answer. I'm reading this book you recommended me. – Red Banana Oct 28 '13 at 20:56
MixedMath, can you recommend me more books like this one? It seems to be a nice balance of teaching concepts, explorations and problem solving. – Red Banana Oct 29 '13 at 03:50
@Gustavo: you know, I wish there were more books like this one. But I don't know of any. Some Olympiad-style books are sort of nice, but they're a bit different. Maybe consider checking out Problem Solving through Problems? But certainly try it from a library before buying, as it's a different feel. – davidlowryduda Oct 29 '13 at 05:18
Yes. It seems that springer has a collection on problem solving books. But I still didn't check them. I really loved the way Polynomials is written. – Red Banana Oct 29 '13 at 06:17
The exercise asks me to show it, how can I do that? The only thing that comes in mind is to use brute force in Mathematica. – Red Banana Oct 31 '13 at 16:06
@davidlowryduda I have enjoyed this exploration myself, do you know of any references on this particular partitioning topic? – MaximusFastidiousIrreverence Jun 18 '19 at 21:52

Barbeau's Polynomials, Exploration 2

1 Answers1