|
|
Go to page 1~2 [Next] | ||||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
- imagine a long corridor full of doors numbered 1 to N+1.
- each door is leading to a room where a number is written on the floor (the number can be in the range 1 to N) - obviously since there are N+1 doors/rooms and only N numbers, at least two rooms share the same number. - you have a writing pad, where only a few numbers can be written on and no other memory element. - you would like to identify A number which is appearing twice in the rooms. - you can only visit each room a small constant amount of times - say 1,2,3 (but not dependent on N!!!) find a way, using the writing pad and minimum amount of work to detect A number which appears twice in the rooms. please note, you can not mark which rooms you visited, and the amount of rooms is very large. you also can NOT remember (even if you are an accomplished memory expert) the numbers in all the rooms you already visited (but you could for instance hold a running sum). enjoy this gem ND |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Some with CS background complained on the formulation -
so in CS language: we need O(n) operations and O(1) memory |
|||||||||
stanalger Special user St. Louis, MO 998 Posts |
Still thinking...
|
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
I smelled something burning, I knew it was you stan...
|
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Is it correct that your mind, that can hold a single number, is allowed O(n) memory? Or is that memory element also limited to O(1)?
/Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Hint:
which number is definitely NOT in its corresponding room ? |
|||||||||
NJJ Inner circle 6437 Posts |
I can't even do the first step
"imagine a long corridor full of doors numbered 1 to N+1" |
|||||||||
stanalger Special user St. Louis, MO 998 Posts |
I want to keep "bumping" this so that Nir isn't tempted to give more clues.
I might change my mind later...and beg for mercy. But for now, I'm enjoying the "burning." Let's hope that the "early" solvers don't immediately post a solution here, ruining the fun for the rest of us. (This will not be a concern if TomasB, a likely first solver, sees the light. He always exhibits great restraint and politely makes use of the PM feature of the Café.) |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
TomasB indeed started thinking on the right track.
but as I encouraged him - the easy part is behind him now... enjoy, ND |
|||||||||
stanalger Special user St. Louis, MO 998 Posts |
I suspect Tomas has already finished this off...and both he and Nir are keeping quiet about it.
I THINK I get the point of the clue, but it hasn't gotten me very far. Stan |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
No one has cracked this one yet...
I could give more hints on demand Nir |
|||||||||
cafeinst Elite user 489 Posts |
I don't think it's possible to do with O(1) memory. For large N, how could you even write a solution (or distinguish a solution) on the notepad? It's probably possible with O(log N) memory though, i.e., a notepad of size O(log N).
|
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Agreed. I had the same problem as Caféinist. Am very curious about the solution.
But to be honest, I'd not find the solution anyway. /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
That is correct that the pad gets larger (width-wise) as the number of doors increase.
what I wanted to reflect (without confusing everyone) was that you are allowed to remember a number or two of the n doors. and not for example have a list of them. N |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Caféinst solved the problem!
maybe there is a better way of solving it - but we both thought of the same solution |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Wow! And I just gave up.
Good work, Caféinst! /Tomas |
|||||||||
cafeinst Elite user 489 Posts |
That was a great problem. I've seen a similar problem posted on the internet by Winkler.
|
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Caféinst - can you refer me to it.
I really liked both of winkler's books |
|||||||||
cafeinst Elite user 489 Posts |
||||||||||
TomasB Inner circle Sweden 1144 Posts |
Apparently no solution has yet been found which solves
"find a way, using the writing pad and minimum amount of work to detect A number which appears twice _IN_ the rooms." [emphasis added by me] /Tomas |
|||||||||
The Magic Cafe Forum Index » » Puzzle me this... » » A new tough one (0 Likes) | ||||||||||
Go to page 1~2 [Next] |
[ Top of Page ] |
All content & postings Copyright © 2001-2024 Steve Brooks. All Rights Reserved. This page was created in 0.02 seconds requiring 5 database queries. |
The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement < |