A Giant Blackboard

Positive integers from 1 to 3141 (inclusive) are written on a blackboard. Two numbers from the board are chosen, erased, and their greatest common divisor is written.

This is repeated until only one number remains on the blackboard. What is the maximum possible value of this 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.

2 solutions

Pranshu Gaba
May 30, 2016

For any positive integer n n , we see that gcd ( 1 , n ) = 1 \gcd(1, n) = 1 . We see that, irrespective of the order in which we choose the numbers, the number 1 1 cannot be removed from the blackboard. Every other number will be eliminated when it is paired with 1 1 . Hence only 1 1 remains at the end.

Relevant wiki: Greatest Common Divisor

Every time we choose the number 1, doesn't matter what number we choose next, because their greatest common divisor will be 1. Therefore, 1 wil be always on the board... thus, when there's only 2 numbers left, one of them is a 1, so the final number is still 1.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...