Numbers on a Blackboard, Extreme Edition

There are 2015 one's on a blackboard. Every turn, I erase two numbers a a and b b on the blackboard and replace them with 4 a b 1 4 ( a + b 1 ) \dfrac{4ab-1}{4(a+b-1)}

After 2014 turns, there is one number remaining. Find the number of possible values of this number.

Details and Assumptions :

If the number you get is over 1000, then submit your answer as the last three digits of that number.


The answer is 1.

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.

3 solutions

A common idea to prove these problems (where no. of ways is 1):

In general let a # b = 4 a b 1 4 ( a + b 1 ) a \# b = \frac{4ab-1}{4(a+b-1)} (this is the definition of the operation #). Now all that is sufficient to prove uniqueness of end result is to show commutativity, a # b = b # a a \# b = b \# a (evident) and associativity, a # ( b # c ) = ( a # b ) # c a \# (b \# c) = (a \# b) \# c (some algebra). Now any order of applying operations on any pairs of the 2015 numbers will always yield the same result after 2014 turns.

Now to find that last remaining number you can simply choose any systematic way to apply the operations that makes induction convenient.

Of course, this may not be the elegant solution (like finding the invariant), especially if you need to find the remaining number). However, it is the most flexible as it applies to most of these type of questions (note that if an invariant can be found, the operation is commutative and associative).

Ah, that's a nice way to think about it. I never realized that proving commutativity and associativity will also prove that there exists one end result. Thanks!

Daniel Liu - 6 years, 4 months ago
Mark Hennings
Dec 11, 2015

Two numbers a , b a,b are replaced by 4 a b 1 4 ( a + b 1 ) \frac{4ab-1}{4(a+b-1)} and so, if x , y > 0 x,y > 0 , the numbers 1 2 + x 1 \tfrac12 + x^{-1} and 1 2 + y 1 \tfrac12 + y^{-1} are replaced by 1 2 + ( x + y ) 1 \tfrac12 + (x+y)^{-1} . This proves the associativity of the replacement rule.

Since the 2015 2015 initial numbers are all equal to 1 2 + 2 1 \tfrac12 + 2^{-1} , and 2 × 2015 = 4030 2\times2015 = 4030 , it is clear that the final number must be 1 2 + 403 0 1 = 1008 2015 \tfrac12 + 4030^{-1} = \tfrac{1008}{2015} , no matter the order in which the numbers are removed.

Daniel Liu
Feb 1, 2015

[This is a hint.]

Consider a second blackboard where every number x x on the first blackboard is replaced with the number 1 2 x 1 \dfrac{1}{2x-1} on the second blackboard.

Does the rule change into something more easy to work with?

Great question. Is still didnot understand what you are hinting at? (Invariance?)

Sualeh Asif - 6 years, 4 months ago

Log in to reply

Yep, if you checked my comment below, I gave the answer.

If S \mathbb{S} is the set of numbers on the blackboard, then x S 1 2 x 1 \displaystyle\sum_{x\,\in\, \mathbb{S}}\dfrac{1}{2x-1} is invariant.

Daniel Liu - 6 years, 4 months ago

Log in to reply

@Daniel Liu can you please show how you obtained this invariant?? Great question though!

Sualeh Asif - 6 years, 4 months ago

But what do we replace two quarters with?

Bogdan Simeonov - 6 years, 4 months ago

Log in to reply

The point for this substitution is so you can see that the sum 1 2 x 1 \displaystyle\sum\dfrac{1}{2x-1} is constant throughout the process. In order to deal with x = 1 2 x=\dfrac{1}{2} , just clear denominators (as this restriction of the domain is introduced only after substitution).

EDIT: hmm, I see what you mean.... maybe this problem is just proposed badly.

Daniel Liu - 6 years, 4 months ago

Log in to reply

Ignoring that, how is the sum invariant?

Bogdan Simeonov - 6 years, 4 months ago

Log in to reply

@Bogdan Simeonov Did you check the problem again? I fixed a typo.

Daniel Liu - 6 years, 4 months ago

Sorry, there was a typo in the problem. It should be fixed now.

Daniel Liu - 6 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...