Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "KGS math club/solution 6 1"

(proof)
 
(→‎Solution for rational weigths)
 
(3 intermediate revisions by 2 users not shown)
Line 5: Line 5:
  
 
== Solution for rational weigths ==
 
== Solution for rational weigths ==
 +
 +
'''First, reduce the problem a bit.'''
  
 
We number the balls from 0 to 2n.
 
We number the balls from 0 to 2n.
Line 10: Line 12:
 
If we subtract the same mass from each ball, the property outlined in the problem statement shouldn't change. Each group of <math>n</math> balls will lose <math>n*w_{subtracted}</math> of their weight, preserving equality or inequality.
 
If we subtract the same mass from each ball, the property outlined in the problem statement shouldn't change. Each group of <math>n</math> balls will lose <math>n*w_{subtracted}</math> of their weight, preserving equality or inequality.
  
−
Since the weights are assumed to be rational, we can transform them all to integers for example by multiplying them by the product of all their divisors. Then we can subtract the smallest integer from all of them, leaving the smallest zero. If all balls weigh the same, we are done with the proof; if not, at least some of the integers must be positive. Now, we divide the whole bunch of integers by their greatest common divisor, leaving us with gcd = 1. So, the whole transformation was essentially <math>w_i = (p_i/q_i - p_j/q_j) * k</math>, where <math>p_i/q_i</math> are the original rational weights, <math>w_i</math> is the resulting integer, <math>j</math> is the ball weighing the least and <math>k</math> a certain rational number, namely <math>k = Q / gcd_i((p_i/q_i - p_j/q_j) * Q)</math>, where <math>Q = \prod_i q_i</math>
+
Since the weights are assumed to be rational, we can transform them all to integers for example by multiplying them by the product of all their divisors. Then we can subtract the smallest integer from all of them, leaving the smallest zero. If all balls weigh the same, we are done with the proof; if not, at least some of the integers must be positive. Now, we divide the whole bunch of integers by their greatest common divisor, leaving us with gcd = 1. So, the whole transformation was essentially <math>w_i = (p_i/q_i - p_j/q_j) * k</math>, where <math>p_i/q_i</math> are the original rational weights, <math>w_i</math> is the resulting integer, <math>j</math> is the ball weighing the least and <math>k</math> a certain rational number, namely <math>k = Q / gcd_i((p_i/q_i - p_j/q_j) * Q)</math>, where <math>Q = \prod_i q_i</math>.
 +
 
 +
Thus, unless all weights were the same, we have found integers <math>w_i</math> such that <math>w_j=0</math> for some <math>j</math> and <math>gcd_{w_i>0}(w_i) = 1</math> and that the integers <math>w_i</math>, each associated with the ball number <math>i</math>, can be grouped according to the desired property exactly the same way the original balls can. That is, <math>\sum_{i\in G}w_i=\sum_{i\in H}w_i</math> exactly when the balls in G weigh the same in total as the balls in H.
 +
 
 +
'''Less formally''': We transform the set of rational weights into a set of integers without a common factor such that the smallest integer will be zero. This makes solving the problem easier. Such "smallest integers" must always exist ''if the weights are not the same'' and can be obtained using the method described above. The transformation is "ok", because if we can do the same division thing to the new integers, we can divide the original weights in the very same way; that is to say, as far as the problem is concerned, the original weights act in the same way as the new integer weights do.
  
−
'''TL;DR''': unless all weights are the same, there surely must exist integers <math>w_i</math> such that <math>w_j=0</math> for some <math>j</math> and <math>gcd_{w_i>0}(w_i) = 1</math> and that the integers <math>w_i</math>, each associated with the ball number <math>i</math>, can be grouped according to the desired property exactly the same way the original balls can. That is, <math>\sum_{i\in G}w_i=\sum_{i\in H}w_i</math> exactly when the balls in G weigh the same in total as the balls in H.
+
'''Then solve.'''
  
 
Let <math>W</math> be the total weight of the balls. If we remove each ball in turn from the collection, we know that <math>\forall i: 2 | (W-w_i)</math>, that is, each remaining ball-mass is divisible by two.
 
Let <math>W</math> be the total weight of the balls. If we remove each ball in turn from the collection, we know that <math>\forall i: 2 | (W-w_i)</math>, that is, each remaining ball-mass is divisible by two.
Line 19: Line 25:
  
 
This would mean that all <math>w_i</math> are of form <math>a + 2b</math> <math>(a\geq 0,b\geq 0)</math>, that is, their difference is divisible by 2 as shown. But since the smallest <math>w_j=0</math>, we have <math>a=0</math>. Thus we can drop the <math>a</math> and write <math>w_i = 2b</math> <math>(b>0)</math>. But that would mean that <math>gcd(w_i) = 2</math>, a contradiction!
 
This would mean that all <math>w_i</math> are of form <math>a + 2b</math> <math>(a\geq 0,b\geq 0)</math>, that is, their difference is divisible by 2 as shown. But since the smallest <math>w_j=0</math>, we have <math>a=0</math>. Thus we can drop the <math>a</math> and write <math>w_i = 2b</math> <math>(b>0)</math>. But that would mean that <math>gcd(w_i) = 2</math>, a contradiction!
−
 
  
 
== Solution for real weights ==
 
== Solution for real weights ==
  
−
WIP
+
Take a basis of <math>\mathbb{R}</math> as <math>\mathbb{Q}</math> vector space. If the weights of the balls have the property of the problem also each of the coordinates of the weights on this base share the same property (This is because taking coordinates is a linear map). Then (using the result for rationals weights) follows that each coordinate is constant and hence all the weights are constant

Latest revision as of 05:27, 18 July 2009

Problem statement

I'm going to write a solution for general $n$ (number of the balls in a group, set to 5 if you like). The problem statement is thus following:

You have a collection of $2n+1$ balls with the property that if you remove any one of the balls, the other $2n$ can be split into two groups of $n$ so that each weighs the same. If you assume that all of the balls have rational weight, there is a cute proof that they all must weigh the same. Can you find a proof? Can you find a way to extend the result to the general case where the balls have real weights?

Solution for rational weigths

First, reduce the problem a bit.

We number the balls from 0 to 2n.

If we subtract the same mass from each ball, the property outlined in the problem statement shouldn't change. Each group of $n$ balls will lose $n*w_{subtracted}$ of their weight, preserving equality or inequality.

Since the weights are assumed to be rational, we can transform them all to integers for example by multiplying them by the product of all their divisors. Then we can subtract the smallest integer from all of them, leaving the smallest zero. If all balls weigh the same, we are done with the proof; if not, at least some of the integers must be positive. Now, we divide the whole bunch of integers by their greatest common divisor, leaving us with gcd = 1. So, the whole transformation was essentially $w_i = (p_i/q_i - p_j/q_j) * k$, where $p_i/q_i$ are the original rational weights, $w_i$ is the resulting integer, $j$ is the ball weighing the least and $k$ a certain rational number, namely $k = Q / gcd_i((p_i/q_i - p_j/q_j) * Q)$, where $Q = \prod_i q_i$.

Thus, unless all weights were the same, we have found integers $w_i$ such that $w_j=0$ for some $j$ and $gcd_{w_i>0}(w_i) = 1$ and that the integers $w_i$, each associated with the ball number $i$, can be grouped according to the desired property exactly the same way the original balls can. That is, $\sum_{i\in G}w_i=\sum_{i\in H}w_i$ exactly when the balls in G weigh the same in total as the balls in H.

Less formally: We transform the set of rational weights into a set of integers without a common factor such that the smallest integer will be zero. This makes solving the problem easier. Such "smallest integers" must always exist if the weights are not the same and can be obtained using the method described above. The transformation is "ok", because if we can do the same division thing to the new integers, we can divide the original weights in the very same way; that is to say, as far as the problem is concerned, the original weights act in the same way as the new integer weights do.

Then solve.

Let $W$ be the total weight of the balls. If we remove each ball in turn from the collection, we know that $\forall i: 2 | (W-w_i)$, that is, each remaining ball-mass is divisible by two.

Combining these, we get $\forall i,j: 2 | (w_i-w_j)$ by subtracting the case i from the case j.

This would mean that all $w_i$ are of form $a + 2b$ $(a\geq 0,b\geq 0)$, that is, their difference is divisible by 2 as shown. But since the smallest $w_j=0$, we have $a=0$. Thus we can drop the $a$ and write $w_i = 2b$ $(b>0)$. But that would mean that $gcd(w_i) = 2$, a contradiction!

Solution for real weights

Take a basis of $\mathbb{R}$ as $\mathbb{Q}$ vector space. If the weights of the balls have the property of the problem also each of the coordinates of the weights on this base share the same property (This is because taking coordinates is a linear map). Then (using the result for rationals weights) follows that each coordinate is constant and hence all the weights are constant

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=KGS_math_club/solution_6_1&oldid=32376"