Today I want to share some interesting problems, that are very algorithm-like/logical in terms of thinking but are not really standard (kind of like some good ad-hoc question you can share with your friend). I'm not exactly sure what to call these, but they are very interesting to me and I hope they are interesting to you as well. If you have something similar, please share.
For some people they are quickly solvable and for other people (like me lol) it is near impossible. I tried to make the problem statements as interesting as possible. Images and problem statements are mostly compiled by me.
I will put up solutions in a day or two (viewing the solution kind of ruins the problem, much more than for ordinary Codeforces problems). Think! It's really much more fun than regular problems. Double promise!
Two papers
source: unknown
You are playing a game against a magician! (You slept at 4 am last night. Who knows how you got here? Maybe you should sleep more. cough cough Savior-of-Cross) The guy says he's in charge of every const int MAGIC ever written. He also promises to show you some magic in his new mind game. You're a little skeptical.
Here's how it works. The magician enters the magic room and takes two pieces of paper, and writes two arbitrary real numbers on them, each in range from $$$0$$$ to $$$1$$$. Once the numbers are written, they cannot be changed. Then, you enter the magic room. You can pick exactly one piece of paper and look at the number written on it. Then, you must submit one of the two papers to the magician. Your goal is to submit the paper which has the greater number written on it. (If the two numbers are the same, then you win by default.)
Example: The magician writes down numbers $$$0.7$$$ and $$$0.8$$$ on a paper. You pick one paper and it is revealed to have the value $$$0.7$$$. If you submit the paper you looked at, you'll lose, because $$$0.7$$$ < $$$0.8$$$; by the same logic, if you submit the paper you did not look at, you'll win.
Figure 1: All the information you'll get.
One last thing: The magician is also a mind reader. He will know everything about your strategy before he even writes the numbers down. And when he knows your strategy, it will be hard to beat him!
You hate losing, and you love winning. Luckily for you, there's a strategy that guarantees you a win probability strictly greater than $$$50$$$%. You're going to show that pesky magician what you're made of, right? His magic constants have given you wayyyyyy too many FSTs. Now it's your chance to get back at him by beating him at his own game. What's your plan?
One hundred prisoners
source: unknown
Uh oh. After you cheesed a data-structure-heavy problem that was meant to be solved in $$$O(n\ \sqrt{n}\ log\ n)$$$ with some sketchy $$$O(n^2)$$$ with pragmas, bitset, and the magic of low constant, the Codeforces Police (who strictly enforce algorithmic ideas) have finally caught you. You've just been put in Algorithm Prison, where inmates are condemned to solve high constant implementation problems with 0.5 second time limits for the rest of their lives. There are a total of $$$n = 100$$$ prisoners in the prison (including yourself).
The guards have a special challenge, since you're so smart. If you solve it, then you get to go free! No pragmas this time, though.
Each prisoner is assigned an integer from 0 through $$$n - 1$$$, inclusive. There can be multiple inmates with the same number assigned to them. There can be numbers that are not assigned to any prisoner.
The numbers are hidden from anyone's knowledge from an entire week, giving you ample time to strategize with your fellow inmates. The guards have already told you how it works ahead of time: On the day of the challenge, all prisoners are put in a giant circular room. No communication of any form is allowed between prisoners once they've entered the room. (This is strictly enforced by the Magic Duck, who will instantly eat any bit of information transmitted between prisoners, no matter what form this information takes.) Each prisoner can see the numbers assigned to all the other prisoners, but cannot see the number assigned to them.
Figure 2: The Magic Duck. He's hungry — for KNOWLEDGE. Quack.
After everyone has seen everyone else's numbers, all prisoners are taken into solitary rooms. Each prisoner must attempt to guess his or her own number. If at least one prisoner guesses his or her number correctly, everyone gets to go free!
But you hate relying on luck and probabilities. Remember that one time when you wrote a randomized hashing solution that was just impossible to break, but you ended up getting Wrong answer on test 147? That ain't happening again. This time, you're going to find a mind-blowing, stunning algorithm that guarantees victory for you and all your buddies. The question is: What's the algorithm?
My favorite:
There are $$$2n$$$ IOI gold medalists in the jail. antontrygubO_o, the evilest person in the world, gives them the chance to escape with the following procedure: he will take a photo of each medalist and put all the photos in the room with image down in order, unknown to the medalists. Today they can discuss their strategy, but will be separated tomorrow. After that, they will come into the room one by one, and will have $$$n$$$ attempts to find their own photo. One attempt is: flip the photo you choose to see the image on it. If you don't find your photo in $$$n$$$ attempts, antontrygubO_o will force you to read his dunk memes. (After a medalist finished, all cards are placed back image down).
However, antontrygubO_o didn't know that medalists have an accomplice farmersrice, who can look at the photos beforehand and can swap any two photos he wants (at most once).
Help them to define a strategy so that no one has to read dunk memes
it is easy, how could it be your favourite smh
Lol, I don't think it's easy Even if it was, it's still really beautiful
i think it is easy for those who are familiar with
permutations
Does this work:
Basically you have a permutation $$$P$$$ and you have to find $$$P^{-1}$$$. Using one swap it is possible to ensure all cycles have length $$$\leq n$$$ (there can be at most one cycle of length $$$>n$$$ and we can split it in half) and then for each point keep querying its cycle until you find its inverse.
Very nice...
Yes!
Doesn't this require the pictures and inmates to be numbered? Otherwise, how will you know which cycle contains your photo?
They can discuss strategy, so they will just number each other off.
Still, photos need to be numbered, don't they?
The photo number is the same as the number of the prisoner who is in the photo.
How do you know which picture to flip first? Obviously, you do not know whose face is on the picture before making a move.
Subsequently, which photo to flip next? You cannot know, if they are not numbered (e.g. chaotically layed out in the room).
The images are not thrown around randomly. You can pick any picture you want to flip. The photo you flip next is given by the index of the current photo's person's number.
I don't understand why farmersrice can't just put the first person's photo farthest to the left (for example) then person 1 comes in, looks at (n-1) other cards, puts them back on the table at the positions they occur, and then picks the leftmost card. Now all the rest of the medallists can immediately get their photo or look at the n photos the first medallist didn't look at...?
I think this doesn't work because the order of entrance is arbitrary (possibly picked by anton).
Do the participants know the order of entry (I guess Anton chooses the queue, but can they see queue once it is chosen...?)?
No, they do not know the order of entry.
Two papers:
Pick a random paper, see number $$$x$$$ and then submit it with probability $$$x$$$. Otherwise, submit the other paper.
For numbers $$$a$$$ and $$$b$$$ ($$$a < b$$$), you submit the latter with p-bility $$$(b + (1 - a)) / 2$$$, which is greater than $$$0.5$$$.
My friend found this paper.
Two papers (same solution with thought process).
The only input you receive in the task is one of the numbers in exactly one of the papers and you should output a Boolean value, whether you are staying with this number or you are choosing the other.
So we can fully describe our strategy with a function $$$f(x) = p$$$ that can be read as: If we see number $$$x$$$ on the paper we are staying with this paper with probability $$$p$$$ and choose the other paper with probability $$$1 - p$$$.
If they numbers written in the papers are $$$a < b$$$ we win with probability: $$$p_a \cdot (1 - f(a)) + p_b \cdot f(b)$$$ where $$$p_a$$$ is the probability of selecting the paper which contains the number $$$a$$$ and $$$p_b$$$ is the probability of selecting the paper which contains the number $$$b$$$. We would like to select the parameters $$$f, p_i$$$ in such a way that we maximize the worst case (this will be the case selected by the magician).
Notice that since we don't know what paper contains each number, we don't really have control on the parameters $$$p_i$$$, we can only select first paper with probability $$$p_1$$$ and second paper with probability $$$p_2$$$, but magician has control over which paper to write each number so he will play this against us. To avoid such situation the best strategy to select $$$p_i$$$ is just set $$$p_1 = p_2 = \frac{1}{2}$$$ (select one paper randomly).
So the probability of winning for a pair $$$a < b$$$ is $$$\frac{1}{2} \cdot (1 - f(a) + f(b))$$$. We want that the probability is always strictly greater than $$$\frac{1}{2}$$$ (for every pair $$$a < b$$$). But this is just:
So we want that for every pair $a < b$, $$$f(a) < f(b)$$$. This is just that the function is strictly monotonically increasing. Remember that the image of this function must be $$$[0, 1]$$$ since it is a probability. The function proposed by Errichto ($$$f(x) = x$$$) does the work very well, but there are a lot of functions that work too.
source: some drank dude told this problem to Marcin_smu
Somewhere in the server room of ITMO, there lies an $$$8 \times 8$$$ chessboard where every cell is white or black, possibly forming some mysterious pattern. One of the cells contains a secret to becoming nutella in CF. Mike doesn't normally let anyone near the chessboard (well, Gennady sometimes comes there to play some crazy version of checkers with himself) but there are two possible exceptions for people with rating at least 2600.
One day, you got an interesting message from a stranger:
That indeed sounds like the best possible plan. You can discuss the strategy with your new friend now. After that, you will sell your own soul, see the grid and know which cell is special, repaint at most one cell, and then your friend will try to guess the special cell just by looking at the grid. What strategy you two should choose?
Related pic, Gennady playing checkers against himself:
Enumerate every field in table and xor indices of fields with ones.
Similar to problem B from GP of SPb 2019.
Isn't it from the last gp of spb?
I didn't participate and I heard this puzzle more than a year ago. But apparently it's same :(
I've seen this puzzle on at least 3 different occasions not even including gp of spb XD Seems like this is pretty popular.
Most of the problems you mentioned can be found here: http://datagenetics.com/blog.html
The $$$i$$$-th prisoner assumes that the sum of all numbers is $$$i$$$ molulo $$$n$$$ and submits the remaining number requires for the sum to equal what he wants.
I have another one :)
https://puzzling.stackexchange.com/questions/81684/blindfold-bingo?fbclid=IwAR050_tzo9qA4dcKnls_6N5zeCf9svToeBjcz86xNz_uDMB7jcCW5AoQzDQ
I think its harder than all of them mentioned above
(Countably) infinitely many mathematicians walk into a
pubqueue. Each of them is given a hat, either white or black; nobody knows which hat he has (they were distracted by calculating the value of $$$(-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3$$$ at the very moment of obtaining a hat). There is no first person in this queue, but there is the last one.Each of them is promised to receive a free pint of beer if he guesses his hat color only seeing all the guys before him in the queue. At 11:55 the first of them is asked to give his answer so that nobody except the beer guy hears it. At 11:57.5 the second of them is asked, at 11:58.75 the third etc. Mathematicians will be happy iff only finite number of them doesn't get any beer by 12:00.
By a happy coincidence, all these mathematicians discussed a strategy yesterday (just in case). Can they succeed independently of the beer guy's actions
There is even harder version of this — someone wrote a real number on their hats instead of 0/1.
The solution to the first subproblem is basically the same
Any hints?
For the first subproblem:
Consider the equivalence relation where two sequences of hats are equivalent iff they have a different color in a finite number of places. Every mathematician knows which equivalence class our sequence belongs to.
Second subproblem:
Now consider the equivalence relation where two sequences are equivalent iff after removing or adding finite amount of elements, possibly zero, to the beginning they have a different color in a finite number of places. Can every mathematician know how many shifts is between their sequence and
the axiom of choice representative of the sequence's equivalence class.
How does the sequence look like if they don't know that?
Ok, Unless this is not a joke I'm going to put some concerns which were born during discussion of this task with my fellows.
If we want to use AC (Axiom of Choice) or any its equivalent from Set Theory prospective (such as Zorn's statement) mathematicians should agree on a fixed function of choice for 'algorithm' to work right? If there're several such functions, how do they agree on such a function?
Yes, AC is needed. They can just remember the whole choice function.
This itself sounds like philosophy more than a math, but:
How to agree on one function of choice? Again to use AC?:)
I'm leaving it as an exercise for the reader
Wait, what?
The last of them is asked, then the second from the end, etc. Also position = the number of guys after him, not before
Source: someone in the IMC 2019
All the $$$n$$$ people who solved the other puzzles in this thread are taken to a prison for being too smart. As an ironic punishment, they can get free if they solve the following supposedly impossible puzzle.
The prisoners are given a short time to discuss strategy. After that they are put into solitary confinement. At irregular intervals one prisoner is brought to a dark cellar with only a lamp in it. (edit: Initially the lamp is turned off.) The prisoner can switch the lamp on or off, or exclaim "All of us have already been here!". If he or she is right, everyone is set free. If he or she is wrong, they are all sent to an even worse prison with an even harder puzzle.
To ensure no one forgets why they are being punished, it is guaranteed that everyone is brought to the lamp room an infinite number of times.
Obviously the guards thought this is impossible to solve. Is it?
Is this FFT?
Only the first person should turn the lamp on. Everyone else should turn it off if and only if it's their first time in the room with the lamp on. The first person should just count the number of times he walked into the room and saw the lamp is off. If it's $$$n$$$, everyone else must've been in.
I think it should be clear that the first person is not the first person entering the room, because nobody knows if they are the first one entering the room; but rather someone they agreed.
It is the last, sixth task for 9 classes at the Moscow Mathematical Olympiad 2003.
i have solution for the problem two papers but im not sure about it can someone pls tell me whether is it correct or not solution :: pick a paper see the number if the number is strictly greater than 0.5 pick it otherwise pick the other paper
The wizard knows that you are going to do that. So he can for example will put 0.7 and 0.8 on the papers. You will succeed with probability 0.5, but you want to succeed with probability strictly greater than that.
I have modification of Prisoners problem brought by a discussion with my colleague.
So, we have $$$N$$$ wizard sitting at the round table. Every wizard wears a hat colored in one of three ways (see the picture). Every wizard can see hats of his/her neighbor (left and right).
They can't exchange any bit of information (again Magic Duck wearing special magic hat will swallow every bit of information). Everyone should guess (with one attempt) what's the type of hat they're wearing.
Again their goal is to guarantee that one wizard will guess correctly.
I don't think it's solvable for every N, but for some there's an algorithm.
P.S. $$$N=3$$$ is just the same as prisoners problem.
It bothers me that the first hat has two colors :|
Is this some modified version of the German flag?
I'm not into any kind of things related to any particular nation:) It's just modification related to CF-ranking system :P
Oooh, I'm stupid.
It is not solvable for $$$N=1, 2$$$ otherwise it is solvable, isn't it? Moreover $$$N - 3$$$ wizards can get drunk in the table and don't need to tell any color, and you just solve the problem with remaining 3 wizards, as in the original problem for $$$N = 3$$$. Did I miss something in the new problem?
True for $$$N=1,2$$$, nut for general case this probably won't work.
Well, if you choose only 3 wizards it's not the same as we have in case of $$$N=3$$$. The reason is if you choose A,B,C to reside consecutively at the table then B can see A and C while A can see only B (and other wizard but not C, only in case $$$N=3$$$), same for C accordingly.
Other words, the circular property plays crucial role here.
Ok, we found a paper related for this problem. Even though it looks similar to Prisoners, we solution is kinda hardcore for Hats Problem. For those whoa are interested:
https://arxiv.org/pdf/1412.3435.pdf