All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 From right to left (Posted on 2017-06-01)
On a teacherâ€™s desk sits a balance scale, on which there is a set of weights.
On each weight there is the name of at least one student. As each student enters the classroom, she moves all the weights that bear her name to the other side of the scale.
Before any students enter, the scale is tipped to the right.

Prove that there is some set of students that you can let into the room that will tip the scale to the left.

Source: Soviet Union Mathematical Competition

Comments: ( Back to comment list | You must be logged in to post comments.)
 n = 3, and beyond (spoiler) Comment 2 of 2 |
ah, the n = 3 case was illuminating, and can be extended to all n

proof for n = 3
---------------
There are 7 different combinations of names that can be called.

Each of the weights will wind up on the left side for exactly 4 of those 7 combinations.

For instance:
Weight A winds up on the left side if the called names are (A) or (A,B) or (A,C) or (A,B,C)
Weight AB winds up on the left side if the called names are (A) or (B) or (A,C) or (B,C)
Weight ABC winds up on the left side if the called names are (A) or (B) or (C) or (A,B,C)

That means that the average weight across all combinations is 4/7 of the initial weight on the right,
and this means that at least one of the combinations is greater than 1/2 of the initial weight on the right,
in which case the scale will tip left.

Proof for any n (with details skipped)
--------------------------------------
There are 2^n - 1 different combinations of names that can be called.

Each of the weights will wind up on the left side for exactly 2^(n-1) of those 2^n - 1 combinations.

That means that the average weight across all combinations is 2^(n-1)/(2^n - 1) of the initial weight on the right, which is greater than 1/2.
This means that at least one of the combinations results in a left hand weight greater than 1/2 of the initial weight on the right.

 Posted by Steve Herman on 2017-06-02 13:49:57

 Search: Search body:
Forums (0)