The Majority Name

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.

Ambiguous Clock

The hands of my alarm clock are indistinguishable. How many times throughout the day their positioning is such that one cannot figure out which is the hour hand, and which is the minute hand?

Remark: AM-PM is not important.

Imagine that you have a third hand which moves 12 times as fast as the minute hand. Then, at any time, if the hour hand moves to the location of the minute hand, the minute hand will move to the location of the imaginary hand. Therefore, our task is to find the number of times during the day when the hour hand and the imaginary hand are on top of each other, and the minute hand is not.

Since the imaginary hand moves 144 times faster than the hour hand, the two hands are on top of each other exactly 143 times between 12AM and 12PM. Out of these 143 times, 11 times all three arrows are on top of each other. Therefore, we have 2 × (143 – 11) = 264 times when we cannot figure out the exact time during the entire 24-hour cycle.

Puzzle Giveaway 3

Our third giveaway is over. Congratulations to Steven W. who won a whole pack of socks which he plans to wear in his future Escape Room adventures.


Hey, puzzlers, our friends at Soxy are offering their comfy socks in a new puzzle pattern and want to share 5 pairs with you. Solve the puzzle below, post the answer on our Facebook wall, and you can be the lucky winner of a whole set of fun socks. Click the banner below to check Soxy’s other cool items.


Last week, I got from Soxy 1 pair of brown socks, 3 pairs of brown shoes, 2 pairs of black socks, 2 pairs of black shoes, and put them all in a wooden chest. How many times should I pick a random item from the chest, so that I end up with all-matching shoes and socks to wear on Comic-Con?

ANSWER ON FACEBOOK

You need to pick at least 14 items from the chest. If you pick 13 items, you can end up with 1 brown sock, 3 left brown shoes, 3 right brown shoes, 4 black socks, and 2 left black shoes.

Vectors -1, 0, 1

Consider all 1024 vectors in a 10-dimensional space with elements ±1. Show that if you change some of the elements of some of the vectors to 0, you can still choose a few vectors, such that their sum is equal to the 0-vector.

Denote the 1024 vectors with ui and their transformations with f(ui). Create a graph with 1024 nodes, labeled with ui. Then, for every node ui, create a directed edge from ui to ui-2f(ui). This is a valid construction, since the vector ui-2f(ui) has elements -1, 0, and 1 only. In the resulting graph, there is a cycle:

v1 ⇾ v2 ⇾ … ⇾ vk ⇾ v1.

Now, if we pick the (transformed) vectors from this cycle, their sum is the 0-vector:

f(v1) + f(v2) + … + f(vk) = (v2 – v1)/2 + (v3 – v2)/2 + … + (v1 – vk)/2 = 0.

Thoka’s Rebus 2

Can you figure out which word is depicted by this rebus?

The first image depicts a SEA. When you switch the third letter to C, you get SEC. The second image depicts RED. When you make the third letter a hard consonant, you get RET. The last two images depict a DIARY and DI (501 in Roman numerals). Therefore, you get:

SEC + RET + DIARY – DI = SECRETARY

Creepy Beasts Inc.

At Creepy Beasts Inc., three of the most dreaded animals, a tiger, a wolf, and a bear, sat in their boardroom in silence while they awaited their boss. Then, Mr. Tiger broke the silence.

“Isn’t it odd that our three surnames are the same as our three species, yet none of our surnames matches our own species?”

The wolf replied, “Yeah, but does anyone care?”

They sat in silence again…

Can you figure out the surname of each animal?

Since the wolf replied to Mr. Tiger, his surname can be neither Tiger nor Wolf. Therefore, the wolf’s surname is Mr. Bear. Subsequently, Mr. Tiger must be a bear, and finally, Mr. Wolf must be a tiger.