What's his last name? Of the Southern aisles

Logic Level 4

You are given a list of the first one trillion positive integers and you must perform the following steps:

Step 1) Pick any two numbers at random from this list.
Step 2) Find the sum and the product of these numbers.
Step 3) Find the sum of the numbers found in step 2.
Step 4) Remove the two chosen numbers in step one from the list.
Step 5) Add the new number found in step 3 into the list.
Step 6) Repeat steps 1 to 5 until there is only one number left.

What is the last 9 (rightmost) digits of the one remaining number?


The answer is 999999999.

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.

2 solutions

Abhinav Raichur
Jul 11, 2015

Let the list A = 1 , 2...... c , b , a A = {1,2 ...... c,b,a } ( c , b and a are the last three numbers )

S T E P 1 : STEP - 1 : Let the two numbers be a and b

S T E P 2 : STEP - 2 : Sum = a + b product = ab

S T E P 3 : STEP - 3 : adding numbers in step 2 we get a + b + a b = ( a + 1 ) ( b + 1 ) 1 a + b + ab = (a+1)(b+1) - 1 This realization is crucial (You might want to remember this as a beautiful binary operation)

S T E P 4 : STEP -4 : adding number to list and eliminating a and b from the set we have A = 1 , 2 , . . . . . . . . . c , ( a + 1 ) ( b + 1 ) 1 A = {1,2, ......... c , (a+1)(b+1) - 1}

Now if we pick up the pair ( c , ( a + 1 ) ( b + 1 ) 1 ) (c, (a+1)(b+1) - 1) Letting A = ( a + 1 ) ( b + 1 ) 1 A = (a+1)(b+1) - 1 we see that the pair ends up being ( A + 1 ) ( c + 1 ) 1 (A+1)(c+1) - 1 OR equivalently ( a + 1 ) ( b + 1 ) ( c + 1 ) 1 (a+1)(b+1)(c+1) - 1 .... And so on

So at the end it is easy to see that WE HAVE A VERY BIG NUMBER

( 1 0 12 + 1 ) ! 1 (10^{12} + 1)! - 1 A TRILLION FACTORIAL! it has a very large number of trailing zeroes ........ minus one yields a number with a greater number of trailing 9's

Hence the answer is 999999999 \boxed{999999999}

NOTE : The identity in step 3 is folklore and employed in many problems of the recursive kind ....... try this

Nice solution.

There is an error which does not change the answer. The final number would be ( 1 0 12 + 1 ) ! 1 (10^{12} + 1)! - 1 .

Pranshu Gaba - 5 years, 11 months ago

Log in to reply

@Pranshu Gaba Thank you. ...... Edited :)

Abhinav Raichur - 5 years, 11 months ago

THANKYOUUUUU

Pi Han Goh - 5 years, 11 months ago

you asked for the last digit, not the whole number.

Som Ghosh - 5 years, 11 months ago
Tan Li Xuan
Aug 29, 2015

Define a set A A as the set of the first one trillion positive integers. Then, define set B B as the set containing every element in set A A plus one (i.e. set B B initially contains the positive integers 2 , 3 , 4 , 5 , 6 , 7......... , 1000000000 , 1000000001 2,3,4,5,6,7 ... ... ... , 1 000 000 000, 1 000 000 001 ).

When we apply the given operation on two integers from set A A , we are replacing the positive integers x x and y y with x + y + x y x + y + xy . So, the operation replaces the positive integers x + 1 x + 1 and y + 1 y + 1 with x y + x + y + 1 = ( x + 1 ) ( y + 1 ) xy + x + y + 1 = (x+1)(y+1) in set B B .

Therefore, in set B B , the given operation is simply replacing two numbers with their product. So, when only one number is left, the number will be 2 × 3 × 4 × 5......... × 1000000000 × 1000000001 2 \times 3 \times 4 \times 5 ... ... ... \times 1 000 000 000 \times 1 000 000 001 This number obviously has at least 9 zeros at the end.

The final element in set A A will be 2 × 3 × 4 × 5......... × 1000000000 × 1000000001 1 2 \times 3 \times 4 \times 5 ... ... ... \times 1 000 000 000 \times 1 000 000 001 - 1 The last nine digits of this number are obviously 999999999 \boxed{ 999 999 999 }

Moderator note:

Good observation with the invariance!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...