3,198 views
40 votes
40 votes

Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $c$ by subtracting the smaller number from the larger one. The numbers $a$ and $b$ are put back in the list. If the number $c$ is non-zero and is not yet in the list, $c$ is added to the list. The player is allowed to play as many rounds as the player wants. The score of a player at the end is the size of the final list.

Suppose at the beginning of the game the list contains the following numbers: $48, 99, 120, 165$ and $273$. What is the score of the best player for this game?

  1. $40$
  2. $16$
  3. $33$
  4. $91$
  5. $123$

4 Answers

Best answer
28 votes
28 votes

Option D is correct

Here the list is $(48, 99, 120, 165 ,273)$.

$\textsf{GCD}(48,99)=3,$ means if we subtract $99-48=51,$ then that number is also divisible by $3$,

So the numbers like $(3,6,9,\ldots,99)$ are added. Total numbers $=99/3=33$

Similarly, $\textsf{GCD}(48,120)=24.$ So the numbers divisible by $24$ are added like $(24,48,\ldots,120)$. Total numbers $=120/24=5$

Similarly $\textsf{GCD}(48,165)=3.$ So the numbers $(3,6,9,\ldots,165)$ are added. Totally, $165/3=55$

At end, $\textsf{GCD}(48,273)=3.$ So the numbers $(3,6,9, \ldots, 273)$ are added(which covers all the above numbers)

So total numbers added to this list $=273/3=91.$

edited by
8 votes
8 votes
(D) Answer will be 91

Because First we have to find the gcd of all the numbers

For example take any two numbers one of the gcd must be 3

Now here maximum number is 273

So, it can take (3, 273) as one of the sample of this game

Here we get all multiple of 3 upto 273

By getting this we also covered other numbers

So, ans is 91
3 votes
3 votes

Now this one is the most easy questions of all

As we can see that all numbers are divisible by 3 , thus when we subtract them with each other obviously we will get numbers which are divisible by 3 ….Point of observation is that suppose we select (48,99) then  99-48 = 51 so 51 will become part of this list ..now if we select (51,48) then 51-48 = 3 ...As we concluded initially that this list will surely contain all numbers divisible by 3 therefore 3 will be the smallest number of this list thus to find all other numbers we will subtract 3 from maximum of all ie 273 and will continue to add numbers in the list ie 270 , 267 ,264…...3  which will also include numbers given in the list , So max size of list will be = 273/3 = 91

1 votes
1 votes
take gcd of every number ... here it will be 3.. divide the highest number 273... it will give 91 ... 273 will cover all the numbers generated by this game...
Answer:

Related questions

49 votes
49 votes
7 answers
4