Problem of the Week

A quadrilateral and a pentagon (both not self-intersecting) intersect each other at N distinct points, where N is a positive integer. What is the maximal possible value of N?

Taotao wants to buy a bracelet. The bracelets have 7 different beads on them, arranged in a circle. Two bracelets are the same if one can be rotated or flipped to get the other. If she can choose the colors and the placement of the beads, and the beads come in orange, white, and black, how many possible bracelets can she buy?

There were no submissions so this problem may be reused in the future.

Let AA1 and BB1 be the altitudes of acute triangle ABC. Points K and M are midpoints of AB and A1B1, respectively. Segments AA1 and KM intersect at point L. Prove that points A, K, L, and B1 are noncyclic.

Starting from the 14th floor is the best strategy.

If the first egg breaks at the 14th floor, then we should check the first floor, then the second one, until the 13th floor. Doing this the total number of attempts would be 14.

If it doesn't break, then you should check the 27th floor. Why? Because if it breaks, you would have to check all the floors from the 15th until the 26th one (thirteen floors), which keeps the total number of attempts at 14 (first attempt at the 14th floor, second at the 27th floor, and the twelve remaining drops from the 15th floor until the 26th floor).

And if it doesn't break, you would have to check the 39th floor; if it breaks you would have to check all the floors from the 28th until the 38th one.

Using the same reasoning, you should check the 50th floor, the 60th, the 69th, the 77th, the 84th, the 90th, the 95, the 99th, and finally the 100th one. Using this strategy you would cover all the floors and the number of attempts would never be greater than 14, even in the worst case.

Suppose you have two eggs and you want to determine from which floors in a 100-floor building you can drop an egg such that it doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.

- If the egg doesn't break at a certain floor, it will not break at any floor below.

- If the eggs break at a certain floor, it will break at any floor above.

- The egg may break at the first floor.

- The egg may not break at the last floor.

Using Toom-3, it takes 25 multiplications, which is the least needed.

What is the least number of multiplications required to multiply two 9-digit numbers?

Is it possible to place 2025 different natural numbers along a circle so that for any two adjacent numbers, the ratio of the greatest to the least is a prime?

First, we find that δ(871) = 8! + 7! + 1! = 45361. Therefore, δ(45361) is equal to 871, and as we already concluded that δ(871) = 45361, 45361 is another solution. We can also get a number one greater than 871, which is 872, and δ(872) will give a result which is one greater than δ(871) as 2! - 1! = 1. δ(872) will result in 45362, and therefore, applying the same logic as above, 45362 is also a solution. Therefore, the solutions are 871, 872, 45361, and 45362.

Define the factorial function of n, denoted δ(n), as the sum of the factorials of the digits of n. For example, δ(2025) = 2! + 0! + 2! + 5! = 125. There are four positive integers such that δ(δ(n)) = n and δ(n) ≠ n. Given that n = 871 is one of them, compute the sum of the other three.

Stephen has the expression 1 + 2 + 3 + ... + 8. He replaces two different addition symbols with multiplication symbols uniformly at random. Find the value that he obtains on average.

For each palindrome substring appearing in x, consider only the leftmost position in which it appears. I claim that now, no two substrings share the same right endpoint. If two do, then you can reflect the smaller one about the center of the larger one to move the smaller one left. Thus, there are at most n distinct palindromic substrings of x.

Let x = x1x2...xn be a word. For some pair of positive integers 1 ≤ a ≤ b ≤ n, define a substring of x to be a word of the form xaxa+1...xb−1xb. Show that there are at most n distinct palindromic substrings of x.

On each turn, the man who does not speak gains information about their own number. Let A be the first person who speaks, and B be the second.

— B knows his number is not 1.

— A knows his number is not 1 or 2.

— B knows his number is not 2 or 3.

— A knows his number is not 3 or 4.

— B knows his number is not 4 or 5.

— A knows his number is not 5 or 6.

— B knows his number is not 6 or 7.

— Then I know my number!

When B says he knows his number, we know that A ≥ 7 and B ≥ 8. If A’s number is 7, B’s must be 8. If A’s number is 8, B’s must be 9. A’s number can not be greater than 8, because then there would still be two possible values for B’s number. Therefore, the answers are (7, 8) and (8, 9).

Two wise men are each wearing a hat labeled with a positive integer. They know the two numbers differ by 1 but do not know which is larger. They take turns speaking:

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— I don’t know my number.

— Then I know my number!

What are the two numbers?

The answer is that on the 100th day, all 100 blue-eyed people will leave.

If you consider the case of just one blue-eyed person on the island, you can show that they obviously leave the first night, because they know they're the only one the green-eyed person could be talking about. They look around and see no one else, and know they should leave. So: [Theorem 1] If there is one blue-eyed person, they leave the first night.

If there are two blue-eyed people, they will each look at the other. They will each realize that "if I don't have blue eyes [Hypothesis 1], then that guy is the only blue-eyed person. And if they're the only person, by Theorem 1 they will leave tonight." They each wait and see, and when neither of them leave the first night, each realizes "My Hypothesis 1 was incorrect. I must have blue eyes." And each leaves the second night.

So: [Theorem 2]: If there are two blue-eyed people on the island, they will each leave the 2nd night.

If there are three blue-eyed people, each one will look at the other two and go through a process similar to the one above. Each considers the two possibilities -- "I have blue eyes" or "I don't have blue eyes." They will know that if they don't have blue eyes, there are only two blue-eyed people on the island -- the two they see. So he can wait two nights, and if no one leaves, they know they must have blue eyes -- Theorem 2 says that if they didn't, the other guys would have left. When they see that they didn't, they know their eyes are blue. All three of them are doing this same process, so they all figure it out on day 3 and leave.

This induction can continue all the way up to Theorem 99, which each person on the island in the problem will of course know immediately. Then they'll each wait 99 days, see that the rest of the group hasn't gone anywhere, and on the 100th night, they all leave.

A group of people with assorted eye colors live on an island. They are all perfect logicians--if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their own eyes. Every night, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. On this island, there are 100 blue-eyed people, 100 brown-eyed people, and 1 green-eyed person. So any given blue-eyed person can see 100 people with brown eyes, 99 people with blue eyes, and 1 person with green eyes, but that does not tell them their own eye color. The only exception to the no communication rule is when the green-eyed person says right before the first night, "I can see someone who has blue eyes." Who leaves the island, and on which night?

Hint: The answer is not that nobody leaves.

The polynomial evaluated at some N can be thought of as an integer in base N. We can only fully discern the original coefficients of p(x) if N is greater than all the coefficients, so then there won't be any carry-overs. To do this, we can have N=p(1)+1. Thus, the only two questions he needs to ask are p(1) and p(p(1)+1). 

Alice's favorite polynomial is p(x), with nonnegative integer coefficients. Bob wants to find this polynomial by asking Alice the value of p(x) for some integer x he chooses. What is the minimal number of questions Bob needs to ask Alice in order to determine p(x)?

First, a small clarification: the prisoners can't communicate in any way. The only things they can do are look at each other's caps and say a color.

Denote white and black as 1 and 0. The first prisoner, our 'sacrifice', should say the sum of all the other prisoners' numbers modulo 2 (i.e. if everybody else is wearing white, they should say 9 x 1 = 9 ≡ 1 (mod 2)). Note that this operation is equivalent to the bitwise XOR operation on the nine "bits" of the prisoners. Now, each of the other nine prisoners immediately knows their number, as they can cross-reference the nine numbers they see with the number the first prisoner speaks to get their own number. Thus, with this optimal strategy, 9 prisoners are guaranteed to live.

Ten prisoners stand in a circle, wearing caps colored white or black. The color of a prisoner's hat is unknown to themself, but everybody else can see their hat. Going around the circle, each prisoner guesses their hat color. They are freed only if they guess correctly. What is the maximum number of prisoners that are freed, and what is the prisoners' strategy for this to happen? Assume that the prisoners can discuss a strategy beforehand.