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

question is easy when you actually understand what is f(s) and h means

---

is there any video solution to this problem??

---

@Deepak Poonia

 

sir not abel to understand the solution properly

want a video or your approach to solve

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

@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 calculated yourself 😊

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

examples always makes it easy to understand. Thanks!

---

Lucid.

Answer 3

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 4

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 !