Register

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 44

• retagged by
637 views
7 votes
7 votes
Acceptable input for a certain pocket calculator is a finite sequence of characters each of which is either a digit or a sign. The first character must be a digit, the last character must be a digit, and any character that is a sign must be followed by a digit. There are $10$ possible digits and $4$ possible signs If $N_k$ denotes the number of such acceptable sequences having length $k$, then $N_k$ is given recursively by

$N_k=a N _{k-1}+b N _{k-2}$, for $k \geq 3$.

What is $a+ b?$
• retagged by
User Avatar

2 Answers

7 votes
7 votes

N1 = 10, As for 1 length string it can be only digit so 10 strings possible

N2 = 100, Again as the string has to start and end with digits so 10*10 strings possible

We would have to find N3 and N4 and then need to compute a and b by solving equation

N3 = 10*4*10  (because starts and ends with digit so 10 choices and in between 4 choice of operators) + 10*10*10 (all three digits) = 1400

Similarly

N4 = 10*4*10*10 + 10*10*4*10 + 10*10*10*10 = 18000

so we get two equation,

1400 = 100a + 10b [ N2 = 100, N1 = 10]                                     – eq 1

18000 = 1400a + 100b [N3 = 1400, N2 = 100]                            -eq 2

Solving the above Linear Equation;

Multiplying eq 1 with 14 on both sides

19600 = 1400a + 140b

18000 = 1400a + 100b                -eq2

=> 1600 = 40b

=> b = 40

And from eq1 e can get a = 10.

Hence, a + b = 50

 

• edited by
User Avatar
3 votes
3 votes
We know that if the first character must be a digit and the last a digit, that gives $N_1 = 10$ and $N_2 = 100.$
$$
\begin{aligned}
& N_1=10 \\
& N_2=100 \\
& N_k=10 N_{k-1}+40 N_{k-2}
\end{aligned}
$$
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

650
views
1 answers
5 votes
GO Classes asked Jan 13
650 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 43
Consider the following $6 \;\mathrm{I} / \mathrm{O}$ operations and their respective cylinder locations on disk. Seek time is $0.1$ milliseconds per cylinder traversed. The ... $10 \ast(\mathrm{X}-\mathrm{Y})?$
User Avatar
513
views
1 answers
5 votes
GO Classes asked Jan 13
513 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 46
The following table lists the arrival time and execution time of $5$ ... starts at zero, what is the time at which $\mathrm{E}$ finishes its execution?
User Avatar
516
views
1 answers
6 votes
GO Classes asked Jan 13
516 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 48
Consider the following pair of mutually recursive functions. What does $g(g(2))$ evaluate to?int f(int n){ if (n==0) return 0; return f(n-1)+g(n-1); } int g(int n){ if (n==0) return 1; return g(n-1) + f(n); }
User Avatar
701
views
1 answers
5 votes
GO Classes asked Jan 13
701 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 56
Host A has to inject' $30$ Mbits of data into a network via a token bucket regulator. The token bucket has a capacity of $15$ Mbits and is filled with ... host sends at a peak rate of $20$ Mbps and the token bucket is initially full?
User Avatar
Link Copied!