GATE CSE 2003 | Question: 39

Question

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows:

$g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$.

Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$.

For a non-empty string $s=a_1 \dots a_n$, where each $a_i \in \Sigma$, define $f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$.

For a non-empty sequence$\left \langle s_j, \dots,s_n\right \rangle$ of stings from $\Sigma^+$, define $h\left(\left \langle s_i \dots s_n\right \rangle\right)=\Pi^n_{i=1}P_i^{f\left(s_i\right)}$

Which of the following numbers is the encoding, $h$, of a non-empty sequence of strings?

• A. $2^73^75^7$

• B. $2^83^85^8$

• C. $2^93^95^9$

• D. $2^{10}3^{10}5^{10}$

Comments

2003 Professor after giving this Question. 😎

Professor Rocked 😎, Students Shocked 🤡

---

Some questions and people are same,
you just see them , try to solve them , and move on .
They are meant to be left on .😌

---

f(s) - takes a stiring as input that is from characters in  given alphabet

for each character c in string s , we put i th prime number ^ g(c) and take product for such characters in the string.

h(s) - takes a string as input that is formed from characters in  given alphabet

for each character c in string s, we put i th prime number ^ f(c)

since we are giving one character at a time to f(s) it comes 2^g(s)

so basically the powers of prime number can be 8, 32, 128, 512 & 2048

Option A: 7 is not allowed

Option B: 8 is allowed and it corresponds to the string 'aaa'

Option C: 9 is not allowed

Option D: 10 is not allowed.

Option B is answer.

 

 

Answer 1

It is clear from the choices that there are $3$ strings in the sequence as we have the first $3$ prime numbers in the product. Now, in $f(s)$ the first term is $2^x$for some $x$, so, A and C choices can be eliminated straight away as neither $7$ nor $9$ is a multiple of $2.$

The sequence of strings are "a", "a" and "a"

$f(a) = 2^3 = 8$. So, we get $2^8 3^8 5^8$ as per the definition of $h$.

Correct Answer: $B$

Comments

Can someone please explain what f(s) and h(s) and its term mean?

---

not clear. Plz elaborate :(

---

If subsequence doesnt start with 1 then?

---

Arjun sir why not "c" "c" "c"???

Question is not clear!!!

---

@Abhisek Tiwari 4

for "c" "c" "c"

Encoding would be: 2¹²⁸3¹²⁸5¹²⁸

---

Also we can eliminate D since f(s) can't be multiple of 5 when it is not multiple of 3 ,because according to definition of f(s), f(s) can't have third prime number(which is 5, P3=5) as it's factor when it does not have second prime number(P2=3) as it's factor.

---

@Arjun sir, As u said f(a) = 2^{3 =}8. Similarly f(b) = 3^5 and f(c) = 5^ 7 (as per the question).

Then how come the answer is 2^8 2^8 2^8 ? Please explain..

---

@Shamim Ahmed

f(b) = 2⁵ because we have to start from prime numbers 2, then 3, then 5 .......

---

Explanation looks very tricky.

---

@Arjun

How did you conclude this part " A and C choices can be eliminated straight away as neither 7 nor 9 is a multiple of 2"

Please explain

---

What would f(aaa) be? Is it equal to $2^{3}3^{3}5^{3}$?

---

@rohith1001 no as f(s) is defined as product from i=1 to n (pi^g(ai))

now here f(aaa)= 2^³×3³×5³ 

which is equal to something calculate yourself 😊

---

Best answer

---

@rohith1001 Yes, $f(aaa) = 2^{3}* 3^3 * 5^3$

Answer 2

^{Option B is correct}

n=3 (in options length is given as 3)

Let s1=a,s2=a,s3=a

now,

f(s1)=f(a)=2³ 

f(s2)=f(a)=2³ 

f(s3)=f(a)=2³ 

p1=2,p2=3,p3=5

h(s1,s2,s3)=p1^f(s1)p2^f(s2)p3^f(s3)=2⁸3⁸5⁸

Comments

better soln

---

Why to take string aaa?
why not abc or any other one?

---

I think it's completely based on options.

If we take s1="abc" then f(s1)=2^3 * 3^5 * 5^7

If we take s1="bac" then f(s2)=2^5 * 3^3 * 5^7

If we take s1="cab" then f(s3)=2^7 * 3^3 * 5^5

then in final answer we will get 2^(2^3 * 5^5 * 7^7) * 3^(2^5 * 5^3 * 7^7) * 5^(2^7 * 5^3 * 7^5) 

but none of the options mathes with this

If we take only one string and which is "a" then f(s1)=f(s2)=f(s3)="a"=2*3

so in final answer we can get 2^(2^3) * 3^(2^3) * 5^(2^3) = 2^8 * 3^8 * 5^8

Even if we take another single string it doesn't matches with 8 in power it can be 2^5 or 2^7 or .....

And easily we can observe that with given g(ai) expect 8 we can't get remaining terms (7,9,10) in power's (according to options) due to pi should be start with 2 (given)  so we can eliminate A,C,D at a time and B is the answer

 

Answer 3

From $2^j⋅3^j⋅5^j=\prod_{i=1}^{3} p^{f(s_{i})}$ we deduce by the uniqueness of the prime decomposition that $f(s_{i})=j \ for \ i=1,2,3$

If $j=7$ we have for example$f(s_{1})=7^1$ and since $1∉{3,5,7,9,11}$ we conclude that it is not a sequence of words with the above encoding scheme.

If $j=8$ we have for example $f(s_{1})=2^3$and since $3∈{3,5,7,11}$ we conclude that is a sequence of words with the above encoding scheme.

If $j=10$ we have for example $f(s_{1})=2^1.5^1$ and since $1∉{3,5,7,9,11}$ we conclude that it is not a sequence of words with the above encoding scheme.

Similarly with $j=9$ you can conclude that it is not an encoding

 

SOURCE : https://math.stackexchange.com/questions/1499757/an-encoding-of-non-empty-sequence-of-strings

Comments

Amazing !

---

nice explaination this should be best answer

Answer 4

Since no sequence is given we need the help of options to identify the correct encoding.

h(⟨si…sn⟩)=Πni=1 Pi^f(si) =P1^f(s1) * P2^f(s2) * .....*Pn^f(sn) 
P1=2, P2=3, P3=5, P4=7 and so on...

g(a_i)={3,5,7,9,11}.

Since in all the options there are first 3 prime nos. given, we can conclude that the sequence s goes up to n=3.

Now, f(s)=Πni=1Pi^g(ai)= P1^g(s1) * P2^g(s2) * .....*Pn^g(sn). As it starts with P1 which is 2 and g(a_i)≠0 for any case, so the value of f(s) can never be odd. Thus we can eliminate option A and C.

Next we see the powers of 2 in option B and D. Concentrating only on the power of 2 we find--->

B shows 8 which can be obtained if for i=1, g(a₁)=3 and P1=2 we already know. 2³=8.
D shows 10 which can be obtained if  for i=1, g(a₁)=1 and P1=2 (we know) , for i=2,g(a₂)=0 and P2=3 (we know), for i=3, g(a₃)=1 and P3=5 (we know). Then (2¹)*(3⁰)*(5¹)=10. But we know that g(a_i)≠0 for any case. So D can't be the answer.

Hence B.

Comments

@MiNiPanda

10 which can be obtained if  for i=1, g(a1)=1 and P1=2 (we know) , for i=2,g(a2)=0 and P2=3 (we know), for i=3, g(a3)=1 and P3=5 (we know). Then (21)*(30)*(51)=10

. how ?

---

Finally understood! Thanks for the effort.

Answer 5

Understanding the question is the only tough part here , else is too easy.

Now, coming to f(s) , it says :$f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$ .

Lets say we have a string as = “bac”

then $f(bac)$ = $P_1^{g(a_1)}*P_2^{g(a_2)}*P_3^{g(a_3)}$

here, $a_1 = b , a_2 = a , a_3 = c $

Putting these into $f(bac)$ definition :

$f(bac)$ = $P_1^{g(b)}*P_2^{g(a)}*P_3^{g(c)}$

And also given that $P_i = $ i th prime number. So $P_1 = 2 ,  P_2 = 3,  P_3 = 5$. Therefore :

$f(bac)$ = $2^{g(b)}*3^{g(a)}*5^{g(c)}$

Now putting the mapping that is given into the question :

$f(bac)$ = $2^{5}*3^{3}*5^{7}$

$f(bac) = 6,75,00,000$

Let this sequence of  $”bac"$ be our $s_1$

Similarly lets have one more sequence $s_2 : “cab”$  

$f(s_2) = 1,08,00,000$

Therefore , we have two string $s_1, s_2$

Now , there’s another function $h(<s_i..s_j>)$ which does the encoding of the sequence of string in the same way we did string encoding: 

$h(<s_1,s_2>) = \Pi^2_{i=1}P_i^{f(s_i)}$ , which is equivalent to : 

$h(<s_1,s_2>) = P_1^{f(s_1)}*P_2^{f(s_2)}$

$h(<s_1,s_2>) = 2^{f(s_1)}*3^{f(s_2)}$

$h(<s_1,s_2>) = 2^{6,75,00,000}*3^{1,08,00,000}$

$h(<bac,cab>) = 2^{6,75,00,000}*3^{1,08,00,000}$

---

 

As you can see , the encoding is so big , from this we can kinda conclude by seeing the options that string must be of single alphabet and there are 3 strings as every option has 3 prime numbers.So given sequence has three strings of single alphabet . 

Now we can also see that every string starts with prime number $2$ $=>$ $(2^{something} * 3^{something} * 5^{something}...)$  , so $2$ must be a multiple , therefore by seeing this only we can remove options ‘a’ and ‘c’

Now option ‘d’ , also can be removed as we cannot get 10 anyhow in: 

$2^{something} * 3^{something} * 5^{something}$

 

We’re left with option ‘b’ only which has $8$ in it. Now we can get $8$ by $2^3$ and also $g(a) = 3$

So our sequence must be : $“a” , “a” , “a”$

Comments

best answer

Answer 6

 

For option (b) as f(s) is divisible by 2 only so 3,5,..... need not appear. so (b) is the answer.

Comments

Thanks for this. Have been struggling on same question since last 1 hour.