# Todai Entrance Exam: Subject 2017 – Problem 3

**(1)**

Let be the values of after processing .

**(2)**

We use induction proof: If a list has the number of varieties of user IDs being at most one then .

__Base case:__ , so when .

__Induction step:__ At the th iteration, we assume that . We prove that if , .

If is empty then , so .

In the case is not empty, is added to if it is already included in , so . If is not already included in , it will not be added to , moreover one number of will be excluded in , so .

So the statement follows.

**(3)**

If exists then frequencies of must be larger than , which implies .

So if numbers in the list are not , then they are guaranteed to be removed all in step *ii-(b)* by the corresponding numbers (or by other numbers of different values).

If the numbers in list are , then it is guaranteed to have at least one number left for step *iii* as the total number of values different from must be less than the frequency of by definition.

So the statement follows.

**(4)**

a = read_log()

L = -1

while a != -1:

if L == -1:

L = a

else:

if L != a:

L = -1

a = read_log()