Tag: Algorithm

In a long list of names, one of the names appears more than half of the time. You will be read the names one at a time, without knowing how many they are, and without being able to write them down. If you have a very weak memory, how can you figure out which is the majority name?

Remember the first name and then keep track of whether it has been repeated more than half of the time. To do that, simply add 1 if you hear the name or subtract one when you hear another name. If the list finishes and your counter is positive, then the first name is the majority. If your counter drops to 0, simply restart the procedure with the next name you hear.

This algorithm, invented by R. Boyer and J. Moore, works, because if the counter ends up at 0, then each of the names up to that moment has been read at most half of the time. Therefore, the majority name appears more than half of the time in the remainder of the list.

I give you a pen and paper and ask you to write the numbers from 1 to 100 in succession so that there are no three numbers such that twice the second one is equal to the sum of the first and the third one. The three numbers do not need to be successive in the sequence.

You have 5 minutes, what do you do?

Remark: The sequence 3, 1, 2, 5, 4 works, but the sequence 1, 4, 2, 5, 3 does not because of the numbers 1, 2, and 3.

Start with the following sequences:

1  →  1, 2  →  2, 4, 1, 3  →  4, 8, 2, 6, 3, 7, 1, 5  →  8, 16, 4, 12, 6, 14, 2, 10, 7, 15, 3, 11, 5, 13, 1, 9

and keep iterating until you get a sequence with all numbers from 1 to 128. On each step you take the previous sequence, multiply all elements by 2, and then add the same result but with all elements decreased by 1. This will ensure that the first half contains only even numbers and the second half contains only odd numbers. Since the sum of an odd and an even number is not divisible by 2, if some sequence violates the property, then the previous sequence would have violated it as well.

Once you construct a sequence with 128 numbers, simply remove the numbers from 101 to 128 and you are done. To speed up the process, you can reduce the sequence 8, 16, 4, 12, 6, 14, 2, 10, 7, 15, 3, 11, 5, 13, 1, 9 to 8, 4, 12, 6, 2, 10, 7, 3, 11, 5, 13, 1, 9 and then continue the process.