There are 2015 one's on a blackboard. Every turn, I erase two numbers a and b on the blackboard and replace them with 4 ( a + b − 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.
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.
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!
Two numbers a , b are replaced by 4 ( a + b − 1 ) 4 a b − 1 and so, if x , y > 0 , the numbers 2 1 + x − 1 and 2 1 + y − 1 are replaced by 2 1 + ( x + y ) − 1 . This proves the associativity of the replacement rule.
Since the 2 0 1 5 initial numbers are all equal to 2 1 + 2 − 1 , and 2 × 2 0 1 5 = 4 0 3 0 , it is clear that the final number must be 2 1 + 4 0 3 0 − 1 = 2 0 1 5 1 0 0 8 , no matter the order in which the numbers are removed.
[This is a hint.]
Consider a second blackboard where every number x on the first blackboard is replaced with the number 2 x − 1 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?)
Log in to reply
Yep, if you checked my comment below, I gave the answer.
If S is the set of numbers on the blackboard, then x ∈ S ∑ 2 x − 1 1 is invariant.
Log in to reply
@Daniel Liu can you please show how you obtained this invariant?? Great question though!
But what do we replace two quarters with?
Log in to reply
The point for this substitution is so you can see that the sum ∑ 2 x − 1 1 is constant throughout the process. In order to deal with x = 2 1 , 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.
Log in to reply
Ignoring that, how is the sum invariant?
Log in to reply
@Bogdan Simeonov – Did you check the problem again? I fixed a typo.
Sorry, there was a typo in the problem. It should be fixed now.
Problem Loading...
Note Loading...
Set Loading...
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 (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 (evident) and associativity, 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).