TIFR CSE 2014 | Part B | Question: 20

Question

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?

• A. $40$
• B. $16$
• C. $33$
• D. $91$
• E. $123$

Comments

for those who might be wondering how 3 and rest are coming.

below is a one way to get the numbers and there are many other ways possible.

take 99 and 48 then we get 99-48= 51 (added in list)

Now, 51 and 48 we get 51-48= 3(added in list)

Now, 273 and 3 we get 273-3=270 (added in list)

Now , 270 and 3 we get 270-3 = 267 (added in list)

.

.

.

we continue like that and then our list contains,

[3,6,9,12……………………………..270,273]

total = 273/3 = 91 elements

and that’s answer.

 

PS  :  from 3^rd round I take 273 to get the maximum elements inserted in the list (and i will go till 3).

---

Hy this question has been pestering me.

as according to the question asked. we can also generate. common divisor as low as 1 .consider this way:

i choose 99-48 = 41 //reinserted in list

i choose 165-120 = 45 //reinseted in list

i choose 45-41 = 4 //reinserted in list

i choose 41-4 = 37 // reinserted and choosed repeatedly so that in the end i end up with 1

now 1 is added to the list. since we have 1 we can generate every possible value in range in 1-273 . therefore the max score that can be achieved is 273.

Please do correct me if i am wrong. since as given in question.

“The player is allowed to play as many rounds as the player wants”.

so why do we choose 91. instead of 123 (which is also a possible high score) while the highest possible is 273

---

@solaikannan, 99-48 = 51 not 41

Answer 1

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.$

Comments

Can anyone tell what is the time complexity.

is it O(n)??

---

Let’s estimate this algorithm’s time complexity (based on n = a+b). The number of steps can be linear, for e.g. gcd(x, 1), so the time complexity is O(n). This is the worst-case complexity, because the value x + y decreases with every step.

Referrence: https://codility.com/media/train/10-Gcd.pdf
The worst case occurs when ‘a’ and ‘b’ are consecutive fibonacci numbers and we want to compute gcd(a, b).

---

Hy this question has been pestering me.

as according to the question asked. we can also generate. common divisor as low as 1 .consider this way:

i choose 99-48 = 41 //reinserted in list

i choose 165-120 = 45 //reinseted in list

i choose 45-41 = 4 //reinserted in list

i choose 41-4 = 37 // reinserted and choosed repeatedly so that in the end i end up with 1

now 1 is added to the list. since we have 1 we can generate every possible value in range in 1-273 . therefore the max score that can be achieved is 273.

Please do correct me if i am wrong. since as given in question.

“The player is allowed to play as many rounds as the player wants”.

so why do we choose 91. instead of 123 (which is also a possible high score) while the highest possible is 273

Answer 2

(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

Comments

OK ...So after finding gcd the lagest among them is enable to find the all possibilities??

---

See here how game is going on

It taking two numbers and subtracting smaller from larger

that we do only in GCD of a programming

Now, try to do it manually

---

ok got

Answer 3

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

Comments

brilliant answer

Answer 4

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...