-
Hey Guest. Check out your NeoGAF Wrapped 2025 results here!
Can't solve this riddle
- Thread starter Two Words
- Start date
- Status
As it happens, I actually had the seed for the answer yesterday, but this was my stumbling block.
It's quite simple: if you start from the box with the target number, the previous box in the loop contains the ball that points to it. You just have to get to it the long way around!
It's quite simple: if you start from the box with the target number, the previous box in the loop contains the ball that points to it. You just have to get to it the long way around!
You can. Loosely speaking, swapping two elements of a loop serves to 'pinch' the loop at that point with the two halves becoming their own independent loops.
This doesnt work if each ball is in a correctly matched boxes, give or take a few off. If almost every box has the identically labelled ball excluding some, there is no way to loop through boxes.
Chainsawkitten
Member
If a ball, say ball 8, is in its own box, box 8, it can't be part of a loop. (Or rather, the loop consists only of itself.) How is one part of a loop? Well, being part of a loop means that some other ball points to your box, but there's only one 8 ball, and if the 8 ball is in its own box, it can't be anywhere else. So there has to be a loop.
weekend_warrior
Banned
Those boxes won't be part of any loops then. If player 2 get a ball number that happens to be in the same number box then the strategy still works, he'll select that box and be one and done.
His answer says you musnt swap more than twice one it dies say once.
How does player 2 know where to start? If box 1 -100 are labelled the same accordingly (player 2 doesnt know) he has to keep opening each box to find a loop.
Entryhazard
Banned
The first one is a classic
The second one I already heard of but you could ask a single question at each one
The second one I already heard of but you could ask a single question at each one
If all boxes contain the same labelled ball, player 2 can only assume that the box contains the number (since he does not know whats in the boxes), this is not a guarantee.
If all boxes contain the same labelled ball, player 2 can only assume that the box contains the number (since he does not know whats in the boxes), this is not a guarantee.
We know from the specifications that there are no duplicate balls.
Because there are no duplicate balls, every ball is guaranteed to be part of a loop, even if there are some single-element loops in there.
In other words: Player 2 knows where to start because the loop that contains the target number ball will also contain the target number box.
In other words: Player 2 knows where to start because the loop that contains the target number ball will also contain the target number box.
efyu_lemonardo
May I have a cookie?
bravo!
Also, I must add, it was really fun following your thought process over the last day.
edit: The interesting thing about this riddle, to me, is that the hard part isn't actually coming up with the winning strategy but rather convincing oneself that this strategy is guaranteed to work. As such, it seems like a lot of people get close to arriving at the correct strategy but believe their line of thinking is a dead end and don't pursue it to completion.
iosa
Member
Player 2 has to start with the box matching the number he got.
Let's say he need to find 56. He start by opening box 56 that contains 245 then he open the box 245.... At one point he'll find ball 56 witch will end the loop.
Player 1 job is to make sure there is no loop that has more than 100 box so at worst only 3 loop.
If he find a loop that as more, he just close it with one of the switches allowed.
Let's say he need to find 56. He start by opening box 56 that contains 245 then he open the box 245.... At one point he'll find ball 56 witch will end the loop.
Player 1 job is to make sure there is no loop that has more than 100 box so at worst only 3 loop.
If he find a loop that as more, he just close it with one of the switches allowed.
bravo!
Also, I must add, it was really fun following your thought process over the last day.
edit: The interesting thing about this riddle, to me, is that the hard part isn't actually coming up with the winning strategy but rather convincing oneself that this strategy is guaranteed to work. As such, it seems like a lot of people get close to arriving at the correct strategy but believe it is a dead end.
As I said a little earlier, that's pretty much exactly what I did!
It's the very first thing I tried, but didn't think through exactly what it meant when I'd looped back to the start, so I missed that that meant a successful outcome
efyu_lemonardo
May I have a cookie?
I did the same thing. Started with this line of thinking, then abandoned it and tried all kinds of other useless stuff, only to return to it much later
efyu_lemonardo
May I have a cookie?
In mathematical terms, the reason this strategy is guaranteed to work is because of the two following facts, which are often introduced and proven in some algebra/set theory/group theory classes:
1. Any permutation on a finite set can be uniquely expressed as a composition of mutually disjoint cycles.
2. In a permutation on a finite set, there is a strict relationship between the maximum number of cycles that compose the permutation, and the maximum length of each cycle.
MoonsaultSlayer
Member
Probably covered but these were written out wrong, no? We don't know who is lying, right? So we can't decide who to ask. Otherwise:
"Hey truth guy, this my path?"
"Hey truth guy, this my path?"
Because it's a loop.The final box in the loop contains the ball that points to the start box - and the ball that points to the start box is the target ball
iosa
Member
Ray Wonder
Founder of the Wounded Tagless Children
GG mclem, and efyu. That was a toughy. I would've try to figure it out, but my willpower to not look at the spoilers is as strong as wet bread. Really cool solve as well.
Yes. But I'm having a hard time visualizing how to follow/create the loops in my mind. I'm really bad at this -.-
efyu_lemonardo
May I have a cookie?
Let me try to give an explanation that will help visualize this fact:
Imagine I'm the person presenting the puzzle to players 1 and 2, meaning my job is to set everything up, even before player 1 enters the room.
Let's say that when I first show up initially everything is completely ordered, so that every box contains the ball with the same number inside it. It's up to me now to scramble the balls in the most complicated way I can manage, and then call in player 1.
I start by picking an arbitrary ball, say number 8, and taking it out of its box (box #8). I can't just throw ball 8 away though, I must put it somewhere. But where can I put it? All other boxes are occupied, and I can't have two balls in one box.... So I have no choice but to remove some other ball, say 200, from its box (#200) in order to "plug the hole" that exists due to box #8 currently being empty.
But now I realize that I've plugged one hole by creating another... I've still got ball 8 to deal with, and now box #200 is empty! I could plug this new hole by putting ball 8 into box #200. But then all I would have done is swapped between 2 balls... surely players 1 and 2 can manage to deal with such a lousy "random" scrambling. So I decide to plug the hole in box #200 with ball 68. And by the same thought process I figure "why not plug the hole in box #68 with yet another ball?" say ball 107. And so on and so forth.
After a while I'm feeling pretty good about how random my scrambling is. But I notice that I've still got one ball that I haven't dealt with yet. Which ball is that? Why ball 8 of course! The ball I kept "delaying" to place inside a box in order to improve the randomness of my scrambling. I have no choice but to put it in the only empty box available.
In mathematical terms, this is equivalent to stating that any permutation on a finite set, in addition to being represented by a composition of cycles, can also be represented as a composition of swaps!
And in fact cycles themselves are no more than compositions of swaps!
edit:
When player 2 enters the room and proceeds to open boxes with the same number as the ball in the previous box, what they are essentially doing is unswapping the swaps that I made when I set up the puzzle. They aren't physically moving the balls, but by following this strategy they are effectively performing the same actions that I did when I set up the puzzle, only in the reverse order!
Took me a bit to get this too, but if Player 1 did his job correctly, ie, split up the loops such that there are no more than 100 in a loop, then the ball he is looking for will be in that loop since the target box is in that loop (the one he starts with).
Edit: Oops, sorry for the double post.
What I'm having problems with is this:
Imagine balls 1-100 are in boxes 101-200 (ir order), balls 101-200 are in boxes 201-300 (in order) and balls 201-300 are in boxes 1-100 (in order). I want to create a loop there. I start counting from box 1 randomly. I'm guessing you should stop at box 34 because that is "100". So you move ball 1 to box 34 to close the loop. The problem is now you don't have a 100 loop, because you have removed one of the balls that was leading to the next box in what you have already counted (the third one, actually). Even worse, if you do that now box 1 has ball 234 because that's the ball that was inside box 34, which leads you to boxes you haven't even counted yet. How do you fix that?
Yes, I get that.
My problem is how to actually create the loops themselves, I understand everything else.
The issue is that it wasnt clarified that ball #8 orginated in box #8.
Edit: maybe not
efyu_lemonardo
May I have a cookie?
Something interesting to point out is that Player 1's job isn't actually very hard, in terms of number of operations required.
We know Player 1 opens all 300 boxes anyway, and the way they go about doing this is exactly the same way Player 2 does it. The only additional work they'd need to do is keep track (by having a list of the numbers 1-300 on a piece of paper and gradually crossing them out) of the balls already encountered. And whenever they reach a ball they've already encountered, count the number of boxes they've opened since their previous encounter with that ball. If that number is greater than 100, perform a swap. Otherwise do nothing. And we already know that this number will be greater than 100 at most two times. So besides opening every box once, they actually don't have much work to do.
Except the keeping track and counting balls. Meanwhile player 2 just opens boxes like a lazy bum. I'm being facetious of course
Ah, well, player 1 is actually only *closing* the loops and ensuring there are no more than 100 per loop. You could have some loops with less than 100 if some balls were in the same numbered box. The loop(s) were created by whoever scrambled the balls.
efyu_lemonardo
May I have a cookie?
It may not be obvious, but in fact it doesn't actually matter if ball 8 originated in box #8 or not. I just used that as a device to help visualize the process of scrambling the balls. If you prefer, you could imagine that when I (the person asking the riddle) showed up, the boxes were already scrambled and I just scrambled them further. That's the same as imagining that someone else was in the room before me and did some of my job for me
It doesn't actually make a difference.
It doesn't actually make a difference.
edit: In mathematical terms this is equivalent to stating that
the composition of permutations is also a permutation!
This fact is used throughout the riddle.
My mind is blown.
It helps to reduce the number set to 6 instead of 300 and let the player choose from 2 boxes instead of 100. Makes understanding it a lot easier.
If the balls are like that, you don't need to move anything because none of the loops are larger than 100. Say the random number is 1. All player 2 needs to do is go from box 1 to box 201 to 101 to find ball 1. The only thing that matters is that the loops are of size 100 or smaller.
Oh, you're right. I don't know what the hell I was doing.
Spycarnegy
Member
Awesome 3rd puzzle. Congrats on figuring it out I was definitely stumped. Bravo
Muppet of a Man
Member
You ask one of the guys which way the other guy would tell you to go and then always choose the opposite path because...
...if you ask the truthful man which way the untruthful man would tell you, the truthful man would tell the truth and it would be that the untruthful man would tell you to go on the wrong path.
...if you ask the untruthful man which way the truthful man would tell you, the untruthful man would lie and tell the opposite of what the truthful man would actually tell you, which is the correct way.
Either way, choosing the opposite path of what is told to you will be the correct path to your destination since both ways of asking effectively give you the "lie" answer.
...if you ask the truthful man which way the untruthful man would tell you, the truthful man would tell the truth and it would be that the untruthful man would tell you to go on the wrong path.
...if you ask the untruthful man which way the truthful man would tell you, the untruthful man would lie and tell the opposite of what the truthful man would actually tell you, which is the correct way.
Either way, choosing the opposite path of what is told to you will be the correct path to your destination since both ways of asking effectively give you the "lie" answer.
efyu_lemonardo
May I have a cookie?
Except the keeping track and counting balls. Meanwhile player 2 just opens boxes like a lazy bum. I'm being facetious of course
To clarify, keeping track is something Player 1 can do as they open the boxes, in the following way:
Open box #1, find ball 234 inside; Cross out number 234 from the list and put a '1' beside it; Open box #234, find ball 180 inside; Cross out number 180 from the list and put a '2' beside it; Open box #180, find ball 59 inside; Cross out number 59 from the list and put a '3' beside to it. The index beside each crossed out number signifies the amount of boxes opened so far by Player 1.
Now sooner or later Player 1, following this process, reaches a ball whose number on the list is already crossed out (this happens exactly when they reach a box that is already open). They look at their list of crossed out numbers to see the index of the previous number that was crossed out (this is just the highest index currently written on the page). If that index is less than or equal to 100, no need to swap. If it is more than 100, swap.
Now cross out all the indexes and pick a new arbitrary box that hasn't been opened yet; Open it to reveal the ball inside; Cross out that number and write down the number '1' beside it. Keep going as before.
The important observation is that if the balls are sufficiently scrambled, Player 1 won't need to do this a very large number of times. And regardless, their list of available numbers will be getting smaller each time they do. In fact the more actual work they have to do, the less scrambled the balls are! Which means that Player 2 will have correspondingly less work to do
efyu_lemonardo
May I have a cookie?
I feel like I haven't done my part unless anyone who seriously attempted to solve this puzzle fully understands the solution. As such I'll keep posting commentary if I think it is necessary.
The following observation is a fundamental one, when it comes to solving this puzzle:
No matter how the balls are scrambled there will always be loops. And every loop will always be closed no matter how the balls are scrambled. The only thing that the person scrambling can actually do is decide which balls belong to which loops, and how long those loops are (with the important restriction that the total sum of the length of all loops must be exactly 300).
In general, it is never possible to create an "open loop". My post at #176 is an attempt to explain why this is so.
iosa
Member
I didn't have time to read the whole of the 4th page, but
I don't know if I made myself clear or if I'm missing something, but that's my two cents.
aren't you supposed to swap the 1st box with the 101st box?
I mean, In doing so, you now made the 'box 1' part of the 'looping 2', closing 'looping 1' with 100 numbers.
For example, if you have the balls positioned as the box number plus 1, like:
box - 1 ----- 2 ----- 3 ----- 4 ... 300
ball - 2 ----- 3 ----- 4 ----- 5 ... 1
You should go until box 101 (with the #102) and swap this one with the ball in box 1 (#2).
Now you restart the count with box 1 (new #102) until box 201 (#202). Swap those again and you will end up with the following loops:
LOOP 1: box 2 (#3) to box 101 (#2)
LOOP 2: box 102 (#103) to box 201 (#102)
LOOP 3: box 1 (#202) and box 202 (#203) to box 300 (#1)
I mean, In doing so, you now made the 'box 1' part of the 'looping 2', closing 'looping 1' with 100 numbers.
For example, if you have the balls positioned as the box number plus 1, like:
box - 1 ----- 2 ----- 3 ----- 4 ... 300
ball - 2 ----- 3 ----- 4 ----- 5 ... 1
You should go until box 101 (with the #102) and swap this one with the ball in box 1 (#2).
Now you restart the count with box 1 (new #102) until box 201 (#202). Swap those again and you will end up with the following loops:
LOOP 1: box 2 (#3) to box 101 (#2)
LOOP 2: box 102 (#103) to box 201 (#102)
LOOP 3: box 1 (#202) and box 202 (#203) to box 300 (#1)
I don't know if I made myself clear or if I'm missing something, but that's my two cents.
You mean for my algorithm?
I said to count off 100 boxes, but I actually meant 100 steps, which would indeed make the one you stop on into the 101st. Poor choice of words!
I said to count off 100 boxes, but I actually meant 100 steps, which would indeed make the one you stop on into the 101st. Poor choice of words!
Yeah. My confusion was because of this part:
I mean, If I understand it correctly, you are supposed to follow the loop for 101 boxes (hence swapping the ball in the 101st, not the 100th) before restarting, because you will end up "eliminating" the first box from that loop and inserting it on the second loop (and then on the third).
Yep, exactly. That's just me being sloppy with phrasing. 100 steps = 101st box.
I'm a coder. It's default behaviour to start counting from 0!
Of course, you only do this if a loop already exists that's over 100 boxes.
I'm a coder. It's default behaviour to start counting from 0!
Of course, you only do this if a loop already exists that's over 100 boxes.
efyu_lemonardo
May I have a cookie?
Maybe a clearer way of describing the swap is to say that Player 1 swaps the ball in the 100th box in the loop with ball 1. Ball 1 will be located in a box that is further down the loop, say box #300 to stick with your example.
After that, box #1 points to box #2, which points to box #3 etc.. and the 100th box (box #100 in your case) now contains ball 1, for a loop with a size of exactly 100.
Sticking with your example, the ball originally inside box #100, ball 101, is now in box #300. So we now have a loop from 101 to 102 to 103... to 300 to 101.
We proceed to swap the ball in box #200 with ball 101. Ball 101 is, as we have already seen, located in box #300.
So now box #101 points to box #102, which points to #103 etc.. and the 100th box (box #200) now contains ball 101, for a loop with a size of exactly 100.
What do we have left at this point? We have box #201, which points to #202, which points to #203 etc.. which points to box #300. Which ball is in box #300? The ball that we swapped in from box #200. Which ball was that? Ball #201. So by creating two loops in this way we've automatically created the third loop, also with a size of exactly 100, with no additional work required.
After that, box #1 points to box #2, which points to box #3 etc.. and the 100th box (box #100 in your case) now contains ball 1, for a loop with a size of exactly 100.
Sticking with your example, the ball originally inside box #100, ball 101, is now in box #300. So we now have a loop from 101 to 102 to 103... to 300 to 101.
We proceed to swap the ball in box #200 with ball 101. Ball 101 is, as we have already seen, located in box #300.
So now box #101 points to box #102, which points to #103 etc.. and the 100th box (box #200) now contains ball 101, for a loop with a size of exactly 100.
What do we have left at this point? We have box #201, which points to #202, which points to #203 etc.. which points to box #300. Which ball is in box #300? The ball that we swapped in from box #200. Which ball was that? Ball #201. So by creating two loops in this way we've automatically created the third loop, also with a size of exactly 100, with no additional work required.
efyu_lemonardo
May I have a cookie?
nah, just a rephrasing of the pointer arithmetic. To me this one's clearer, but it's subjective.
Yours was: value in box 101 is swapped with value in box 1, creating the loop (2,3,4....101)
whereas mine was: value in box 100 is swapped with value in box containing ball 1, creating the loop (1,2,3...100)
efyu_lemonardo
May I have a cookie?
edit: see my post at the top of the next page for a clarified explanation of the riddle.
Hello again fellow riddle lovers!
Bumping this thread with a new doozy that I recently learned. As with the last riddle, knowledge of higher math is useful but not at all necessary, logic and perseverance are most important. I encourage everyone to participate and contribute! No one should feel bad for getting stumped, and the answer is (in my opinion) quite cool and satisfying.
Ten prisoners are placed in ten cells. Above each cell the warden places a random number selected from {1,2,3,4,5,6,7,8,9,10} - in other words repetition is allowed and not every number needs to show up.
Each prisoner is able to look outside their cell and see the nine other cells and their respective numbers. No prisoner is able to see the number above their own cell, and communication between the prisoners is forbidden.
The warden offers the following challenge to the group: If a single prisoner is able to correctly guess the number above their cell, the entire group will be set free. Each prisoner is given a piece of paper to write down their guess, and after a moment the warden goes around the room, collecting each paper and comparing it with the number above that prisoner's cell.
Before the challenge begins (and before the numbers are placed above the cells) the prisoners are given a moment to come up with strategy that is guaranteed to win. Can you find this strategy?
Here's a small optional tip to get you started:
GOOD LUCK!
Hello again fellow riddle lovers!
Bumping this thread with a new doozy that I recently learned. As with the last riddle, knowledge of higher math is useful but not at all necessary, logic and perseverance are most important. I encourage everyone to participate and contribute! No one should feel bad for getting stumped, and the answer is (in my opinion) quite cool and satisfying.
Ten prisoners are placed in ten cells. Above each cell the warden places a random number selected from {1,2,3,4,5,6,7,8,9,10} - in other words repetition is allowed and not every number needs to show up.
Each prisoner is able to look outside their cell and see the nine other cells and their respective numbers. No prisoner is able to see the number above their own cell, and communication between the prisoners is forbidden.
The warden offers the following challenge to the group: If a single prisoner is able to correctly guess the number above their cell, the entire group will be set free. Each prisoner is given a piece of paper to write down their guess, and after a moment the warden goes around the room, collecting each paper and comparing it with the number above that prisoner's cell.
Before the challenge begins (and before the numbers are placed above the cells) the prisoners are given a moment to come up with strategy that is guaranteed to win. Can you find this strategy?
Here's a small optional tip to get you started:
try to solve a simplified version of this riddle with 2 prisoners instead of 10. If you can, does your chosen strategy work with 3 prisoners as well?
GOOD LUCK!
liliththepale
Banned
Split the paper in two, write a new (same) number on both halves, and affix one of the halves to the top of the cell over the old number that the warden put there.
- Status