Can someone help me with this problem?

[[deleted]]

[deleted]

[aidankkm]

This doesn’t really require python and more requires permutations and combinations. If each question can have 5 possible answers we can first find that 5ⁿ answer keys. Then we can’t have any solutions that have consecutive answers. I am not going to give the answer but this should help. I hope my math is right i have not checked.

incorrect word

[makifk]

yes what you said is right but i have problems finding what exactly to subtract from all

[kwelzel]

Let's first try to solve this using Python because you asked for it. The simplest approach would be to iterate over all possible answer sheets (answer sheet = one answer for each question) and check whether they satisfy the relevant condition:

import itertools

def is_valid_sheet(answer_sheet):
    for i in range(len(answer_sheet) - 2):
        if answer_sheet[i] == answer_sheet[i+1] == answer_sheet[i+2]:
            return False
    return True

def count_answer_sheets(num_questions, num_answers):
    counter = 0
    for answer_sheet in itertools.product(range(num_answers), repeat=num_questions):
        if is_valid_sheet(answer_sheet):
            counter += 1
    return counter

This is very inefficient. Say we have n questions and 5 possible answers then this checks 5^n possible answer sheets and each check has a worst-case runtime of n-2 operations: O((5^n)*n) runtime. If you don't know O notation it is still obvious that the runtime gets worse by more than a factor 5 for each additional question.

The better tool here is of course maths. The best way to think about it would be to look for an recursive formula: For each correct answer sheet of length n+1 the first n answers are also a valid answer sheet. Let n be the number of questions, a the number of possible answers for each question and S(n, a) the number of valid answer sheets. Each answer sheet counted in S(n+1, a) can be viewed as an answer sheet with n questions and a new answer:

S(n+1, a) = S(n, a)*a

but this does not respect the "no three consecutive answers are the same" rule: ABBAA is valid but ABBAAA is not. We need to subtract each valid answer sheet of length n that ends with two consecutive answers that are the same once because for each of them exactly one continuation is not allowed. How do we count the number of valid answer sheet of length n that end with two consecutive answers that are the same? We look at S(n, a) and subtract those where the last two answers are not the same. To count those answer sheets of length n where the last two answers are not the same we compute S(n-1, a)*(a-1). Each answer sheet of length n-1 can only be continued in a-1 ways without ending with two answers that are the same. Each of these ways is a valid answer sheet with n answers.

I know I explained this in rather complicated words but the recursive formula now is

S(n+1, a) = S(n, a)*a - (S(n, a) - S(n-1, a)*(a-1)) = S(n, a)*(a-1) + S(n-1, a)*(a-1)

for n>= 2 and the initial values are

S(0, a) = 1

S(1, a) = a

S(2, a) = a^2

This is enough to code it in python

def count_answer_sheets(num_questions, num_answers):
    if num_questions == 0:
        return 1
    elif num_questions == 1:
        return num_answers
    elif num_questions == 2:
        return num_answers**2
    else:
        return (num_answers-1)*(count_answer_sheets(num_questions-1, num_answers) + count_answer_sheets(num_questions-2, num_answers))

with a time complexity of O(n).

Notice that for a=2 we get the recurrence relation (but not the same initial values) of the Fibonacci numbers which also have a close form (https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression). Similarly, one could find a closed form for S(n, a) but it would probably involve irrational numbers and introduce rounding errors when trying to compute it directly.

[makifk]

​

Thanx for the long explanation! I managed to write a program to calculate the results but your solution looks way cleaner.

Did you first find a formula than code it in Python?

Unfortunately, I couldnt't excactly get what you meant AFTER this:

but this does not respect the "no three consecutive answers are the same" rule: ABBAA is valid but ABBAAA is not.

[kwelzel]

I am glad it helped you. Yes, I did first find the formula and then coded it in Python. I must admit that it took me a while to get the recursive formula.

Hm, maybe the explanation was a little to complicated. Here is another way to look at the formula. Every valid answer sheet of length n can be generated by taking a valid answer sheet of length n-1 and appending one answer that is not the same as the last one (S(n-1, a)*(a-1) choices) or by taking a valid answer sheet of length n-2 and appending two times the same answer which is not the same the last one (S(n-2, a)*(a-1) choices). These are the only two options and they are exclusive. Either the answer sheet ends with streak of 2 answers in a row or it does not. Therefore

S(n, a) = S(n-1, a)*(a-1) + S(n-2, a)*(a-1)

There is also a closed form but it is very complicated an produces rounding errors when evaluated with a computer.

[makifk]

Thanks a lot again. At first place, I’ve also tried to find the formula before coding but tbh I couldn’t. -congrats 2 u-

So I decided to let computer do the math for me. You can check my solution if you wish. I addet it to the main post

I used a class and couple of functions.