Seemingly IMPOSSIBLE Fox Puzzle || Fox in a Hole || Asked in Google Interview
ฝัง
- เผยแพร่เมื่อ 21 ก.ย. 2024
- There are five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?
The video has complete explanation of the logic behind the solution.
Please comment below your answers and suggestions. Also LIKE the video and SUBSCRIBE to my channel if you are new.
Also, please give a try to difficult puzzles and Interview Questions Answers specific to Puzzles and Riddles.
Gold bar break Puzzle : • Gold Bar Puzzle || Bre...
Pirates of the Caribbean Puzzle [100 Gold Coins & 5 Pirates] : • 5 Pirates PUZZLE || 10...
Stay awake for one night and catch it, when it tries to move one hole. Done.
Exactly this is the optimal strategy
Find out the fox's name and write it in the deathnote
@@two697 lol
@@two697 you have to see also 🤣🤣
@EruYagami You are selected ..
I solved it differently by visualizing where the fox can be each day.
1. Starting with hole 2 => the fox can be in any other hole (1, 3, 4 ,5).
2. Moving to hole 3 => the fox can be in three other holes (2, 4, 5).
3. Moving to hole 4 => the fox can be in three other holes (1, 3, 5).
4. Staying on hole 4 => the fox *has* to be in hole 2. (We could go grab it right now)
5. Moving to hole 3 => the fox *has* to be in hole 1. (What are you waiting for? Go grab it!)
6. Moving to hole 2 => It is caught. (Finally...)
My sequence is 2, 3, 4, 4, 3, 2; reversing the first half. But it's basically the same solution.
I liked my approach because I didn't have to assume anything.
However it is much simpler to generalize with the approach shown in the video.
Just start with the second slot and increment until n-1, then do that sequence again or in reverse and you are done in O(2(n-2))
just simply watch fox footprints on mud around hole lol..hahaha
Damn, I thought the same😂
THER IS A HARD COURT.
Smooth out the dirt around all five holes, come back the next day and look for tracks.
I'm glad the people at Google understand the old art of tracking 😂😂
They are good at tracking. Not just this kind of tracking.
Dig a trench between the holes.
I thought similar. Honestly, I would fill all the holes with mud and see which one he pops out of and say... there he was ...in that hole. or put different color paint at the bottom of each hole and then follow the tracks
@@phDST1913 Hell bring 4 friends to checkj the other holes -- if you're only permitted to check 1 hole per day.
@@uberfu lmao
First we should inspect the first hole and fill it with cement
Second day you should inspect the second hole and fill it with cement
And do the same process😂
Saved one day of inspection
I tried that, but I never found the fox. However, there was a fox foot sticking out of the cement.
QI 300! You are a CyberPunk living in 2070 XD
Actually saves two days of inspection 😂
Or save cement. And check same hole every day... 20 pct chance to catch
Fill the hole with concrete every day .......that's it
I was going to say sand, but concrete works.
The aim is to find the fox , not to kill it.
@@Shubham-np6od
No the aim was to find out what does the fox say?
How would filling an empty hole kill it?
@@mbearlover how would you know whether the hole is empty or there is fox in it.
2, 2, 3 ,4, 4, 3 ,2 this sequence will work very well. If the fox in 1st hole first day, it will catch in 2nd day. if the fox in 2nd hole it will be caught in the 1st day. if the fox in 3rd hole in first day, there are three ways to move: move to 2nd hole in the 2nd day(it will be caught in 2nd day), move to 4 in the 2nd day then 5 then 4 holes in 3 and 4 days (it will be caught in the 4 th day based on my sequence ), move to 4 in the 2nd day then 3 then (it will be caught in the 3 rd day) . if the fox in the 4 hole in the first day, so there are 11 scenarios can be happened; move to 5 then 4 then 5 then 4 (it will be catch in 5th day ), move to 5 then 4 then 3 then 4 (it will be catch in 5th day), move to 5 then 4 then 3 then 2 then 3 (it will be catch in the 6 days), move to 5 then 4 then 3 then 2 then 1 then 2 (it will be catch in 7 days), move to 3 then 4 then 5 then 4 (it will be catch in 5 days), move to 3 then 4 then 3 then 4 (it will be catch in 5 days), move to 3 then 2 then 3 then 4 (it will be catch in 5 days), move 3 then 2 then 3 then 2 then 3 (it will be catch in 6 day), move 3 then 2 then 3 then 2 then 1 then 2 (it will be catch in 7 days), move 3 then 2 then 1 then 2 then 1 then 2 (it will be catch in 7 days), move 3 then 2 then 1 then 2 then 3 (it will be catch in 6 days). If the fox in 5th hole, there are two scenarios for moving: move to 4 then 5 then 4 (catch in 4 th days). Move to 4 to 3 (it will be caught in three days).
solve by Ala Zayed
Of course, your solution is better than mine due to the fact the maximum number of days that I need is 7, but you need only 6 and your method also is easier than my method.
Mind blowing Zayed... that's truly interesting solution. You really solved it in a natural way. Although it took an extra day but it's a beautiful approach. (I checked for all the possibilities and all of them seem to be solved with your approach)
Nice work, but sorry for the spoiler. The sequence u mentioned 2, 2, 3, 4, 4, 3, 2 will definitely work as it has a subset sequence 2, 3, 4 ,4 ,3, 2 which is optimal.
So even the sequence 5, 2, 3, 4, ,3, 2 will work and also 4, 2,3,4, 2, 3, 4 as the have the subset optimal sequence of 2, 3, 4,2, 3, 4 or 2, 3, 4, 4, 3, 2
Thanks, and and nice effort. appreciate it, as I think u tried it before you learned about the optimal solution sequence.
Great approach. This is optimal if the fox starts on hole 1.
Two possible ans from my side-
2,4,3,2 2,3,4
2,4,3,2 4,3,2
There can be many possible answers
I solved it too in a similar way, but ans by channel is the most elegant as it takes 6 days instead of 7
You can actually generalize this to any number of "holes" (memory addresses, etc.) with a guaranteed worse case of 2(N-2).
Bro where did you learn your algorithm and data structure?
I want to improve in those.
Please help me
Bro tell me also
I used to be a fox. Always staying ahead of the neighbouring husbands.
The easiest way would be to go and select a hole in the morning, if you are lucky enough you catch the fox and if not fill up that hole and come next morning and keep doing until you catch the fox 😃
Keep the food outside with strong aroma....and sit back relaxed
Mission accomplished in 10 second 😋
Only problem is: I smell the food, come over, and eat it not knowing why it is there.
It would make more sense to present this as a friend offers you the riddle as a party game that he will move an object from one cup to another while you cooperate and do not look, there is no looking through the cups and no other forms of bypassing your choice to guess blindly or optimize probability and ensure you guess right.
People won't cover a cup if they are told it is cheating but if you say there is a fox you want to stop it just check all the holes in one day or cover the holes when you know it has this strange compulsion to move around that foxes usually do not have.
PARTY GAME, PLEASE.
My solution was 1-2-3-4-5-5-4-3-2-1 (every hole is inspected twice, once on an even-numbered day and once on an odd-numbered day, and you're inspecting them in systematical order, so that if the fox is in an odd-numbered hole on the first day then you'll find it in the first five days; otherwise you'll find it in the last five days).
I hadn't realized that we can ignore hole 1 and hole 5 because if the fox is there then it is forced to a certain hole the next day anyway.
So the optimal solution is 2-3-4-4-3-2, or 4-3-2-2-3-4, or 2-3-4-2-3-4, or 4-3-2-4-3-2.
Anyway, excellent puzzle, and excellent solution!
Hi Yuri... Your first approach shows that you are a real puzzle solver.... although you missed to optimize it as you explained later... but still the first part of your comment shows the simplest way to solve this puzzle. I will certainly use your explanation when we will have some theoretical videos on 'Art of solving puzzle'.
Thanks for the contribution Yuri... :)
@Logically Yours, thanks for your kind reply. Several of your puzzles seem to contain a certain twist that I can't just solve with only mathematics; it really requires puzzle-solving skills. The one about crossing the bridge in 17 minutes on a dark knight really fooled me! (Very fun puzzle, once I heard the answer it seems so simple!) I would be interested in theoretical videos on "The Art of Puzzle Solving". Keep up the good work! :)
You mention 1-2-3-4-5-5-4-3-2-1 as a non-optimal solution. With the same reasoning, another non-optimal solution would be 1-2-3-4-5-1-2-3-4-5. Am I correct?
Dimitrios Kalemis,
Yes, I think that's correct. I don't know why I hadn't thought of that order before.
A strategy can be checked visually by drawing an N-by-5 "chessboard" (with black and white squares), where N is the number of days in the strategy. So the columns correspond with the five holes, and the rows correspond with the days. In each row, we put a mark (X) in the column that corresponds to the hole that we're checking that day. The strategy 1-2-3-4-5-1-2-3-4-5 would then look like this:
Holes:
1 2 3 4 5
||X|| ::: ||||| ::: |||||| day 1
| ::: |X|| ::: ||||| ::: | day 2
|||||| ::: |X|| ::: |||||| day 3
| ::: ||||| ::: |X|| ::: | day 4
|||||| ::: ||||| ::: |X||| day 5
| X ||||| ::: ||||| :::: | day 6
|||||| X ||||| ::: |||||| day 7
| ::: ||||| X ||||| :::: | day 8
|||||| ::: ||||| X |||||| day 9
| ::: ||||| ::: ||||| X | day 10
The fox would start in one of the five holes on day 1, and move to a diagonally neighbouring square on the next day (like a Bishop in chess, but only one diagonal step at a time). It would then have the task to find a way to make it to day 10 without hitting on a square with a mark.
If the fox starts on day 1 on a "black" square ( "||||" ), it's easy to see that it's either discovered on the first day, or it would not manage to move past the diagonal of X's before day 5. If the fox starts on day 1 on a "white" square ( " ::: " ), then it manages to pass the diagonal of the first five days, but it won't manage to go past the second diagonal on days 6-10; on one of those days, it's forced to move to a square with an X, which means it will be found on that day. So this strategy of X's is successful.
We can draw a similar diagram for a shorter strategy, 2-3-4-2-3-4:
Holes:
1 2 3 4 5
|||||| X ||||| ::: |||||| day 1
| ::: ||||| X ||||| ::: | day 2
|||||| ::: ||||| X |||||| day 3
| ::: |X|| ::: ||||| ::: | day 4
|||||| ::: |X|| ::: |||||| day 5
| ::: ||||| ::: |X|| ::: | day 6
Again we can see that if the fox starts on a "white" square, there's no path to to make it past day 3; and if the fox starts on a "black" square, the fox makes it through day 3, but it will not manage to avoid a marked square in days 4, 5 and 6. So this is also a successful strategy.
1234554321 and 1234512345 wont work man, wew
I can probably see everything in the holes from the window of my 3 story house.
That's more logical
Then yu broke first rule.
How would the problem change if the holes were arranged in a ring, where the Fox may move from Hole 1 to Hole 5 or vice-versa?
Hi Jason, I can roughly say it would not be possible to catch the fox at all as there is no corner hole to avoid the escape.
I had the same thought long back... glad to see your comment... now I can look into this type of circular arrangement with some additional constraints/arrangements.
@@LOGICALLYYOURS
Simply check 2 holes each day. Start at any pair of neighbouring holes, A, number N, and B, number N +1. Check the pair twice, move the pairing to A1, number of hole A -1, and B1, number of hole B + 1. Repeat until all the holes have been checked twice. The space between each pairing will allows be fox free assuming the fox never moves more than 1 square.
I would check all the hole at once cause I like to work smarter not harder lol
You contradict your own statement about you by checking all holes at once (which is equivalent to working harder) 😆
@@cool-aquarian no, thats a lot easier than checking 6 holes on 6 different days
@@william7yifans great.. your boss would be happy to know. He would like you to wrap up whole of week's work tomorrow.
@@cool-aquarian you are seriously telling me youd rather walk to work every day for a week to sign one paper and go home than to sign 5 papers at once? cuz that's what this is comparable to
@@william7yifans yes because once you sign 5 papers together, your boss will expect you to sign 5 papers everyday from then onwards for same pay. 😷
Awesome thanks, caught the fox in my yard and it bit me!
If it's that hard to look into 5 holes in one day, then use a camera over night, capture it on day 2 for sure.
We can easily solve this as:-
We can cover each hole with air exchange cloth and fox would always remove cloth when want to move to specific hole and now we can easily track fox movement.
Better strategy for more general problems is apply Dynamic programing. It was not intuitive how we arrive at even/odd guess. We start from the last day and go back. Say All possible ways the fox can move are caught in say day T (terminal state). Lets pick 4 as terminal state (4/2 will work but not 5/3/1) as for say 1 fox could have been in hole 2 earlier and could move to 3 to avoid getting caught. If 4 was the last possibility then fox was in 5 previous day. So previous day better to look at 3, to make sure fox can move only from 2 -4 and not 2-3, and so on. Sorry difficult to explain in words, pic would have been easier. You will see you will get the same answer pointing to even/odd intuition
Check hole 3 every day until it’s in there. Maybe the fox just goes back-and-forth from 1 to 2 or 4 to 5 and never comes to 3, but there’s already nothing logical about a fox changing holes every day, so I’ll add my own assumptions and can’t be wrong.
No, you can be (and definitely are) wrong. If you refuse to comprehend that a logic puzzle serves as a catalyst for critical and logical thought then you're simply stagnating your own mental growth by being obstinate. This has nothing to do with a fox.
@@shivafatalis4368 Thanks for your opinion.
@@shivafatalis4368 Imagine checking the hole requires a camera. Perhaps setting it up at hole 3 is the best idea because it’s far more expensive to have multiple cameras. Fuck it!
Staying at 3 until it happens require the least amount of effort and resources (and has a small chance of never happening but ‘probably’ will eventually) and may be a more ideal solution. It just depends on what the business’s priorities are.
Bill Gates once said something along the lines of ‘ask a lazy man to perform a task and he’ll show you the easiest way to do it’…. Which may be a boon for whatever project. Ya know, something like that.
It may be an advantage to find the highly probably solution in less time as well, when an absolute answer may have wasted a day to develop.
@@shivafatalis4368 this also brings up the idea of cheap-fast-good: pick two.
If it’s cheap and good, it’s not fast.
If it’s fast and cheap, it’s not good.
If it’s good and fast, it’s not cheap.
What’s the goal, given a situation? Is one of these objectively better than the others?
@@drummyt7166 I'm really not sure why you're suggesting these various trivialities to me. Maybe you misread my response or completely missed the point, because you took this a completely different direction.
I made it in a paper and got to this other answer:
2-2-4-4-3-2, the logic being you discard the fox being in one corner, then the other, and finally... you catch it
Never knew what he wanted in solution. He didn't mention he was looking for minimum number of days to find the fox.
Yeah. Just said make sure he's eventually caught. That problem solves itself. Eventually.
@@jeffreywilliamson4863 I mean if you're not doing it the right way you aren't guarantee to catch the fox ever.
I paused this approx a week ago. finally got the answer this morning, I hope I am right - 234234 will ensure the fox get caught eventually
Hmm I got the exact same answer, although my thought process wasn't the same. Instead of focusing on determining whether the fox started on an even or odd hole, I had made a chart of sorts of all possible fox locations and checked spots with the intention of lowering the possible locations he could be in while keeping in mind that if the fox is at the edge he's forced to move to only 1 possible location the next day. Interesting how different outlooks still converge to the same solution.
Yea in the chart I noticed the foxes superposition was like a checkerboard where he lived on all black squares or all white squares. The fox was either black or white so I did two sweeps one going left then repeating that square so that I would switch from black to white then sweep right. Boom.
My thought was far simpler, start at hole 2, and repeat hole 2. If the fox is not caught you know the fox is not in holes 1 or 2.. Try hole 3 if not caught the fox is in hole 4,5 or 6. Repeat hole 3, to catch any fox moving from 4 to 3. If not caught repeat hole 4. The last hole to repeat is 5. The holes for repetition is 2, 3, 4 and 5, a total of 8 moves.
@@michaeledwards2251 Hey bro, your solution is wrong. when you will cheak hole 3, then you said that the fox will be in hole 4 or 5. But the fox can be in hole 2 also. as on day 2 if the fox is in hole 3, then the fox can go inhole 2 or hole 4 on day 3. so your assumption is wrong here. Please think again :)
@@Sanket_Jagtap
Did you not wonder why I started at hole 2, and repeated. If the fox was in hole 1, it will move 1 hole, putting it in hole 2. This means checking each hole N twice in 2 to N -1, ascending by 1 hole each time, all holes prior to the hole being checked are empty of a fox.
The problem is the use of a fox as an image. A real fox would be unpredictable and could move any number of holes with an awareness you are trying to catch it. I prefer my solution as it assumes the fox behaves in a more cautious manner the closer you are to it, and does not assume the fox always moves 1 hole when it would be more difficult to observe.
You’re not getting it. On day two when you check hole 2 the second time, If the fox was in hole 3 then on day 3 he could have moved to hole 2.
I was thinking about always looking at hole 3, which will always have a 33% chance on having the fox after night 1. I'll explain: If the fox isn't in hole 3, then it's, obviously, on holes 1, 2, 4 or 5. If it's on holes 1 or 5, it will have only one movement, which is to move to holes 2 or 4 respectively. If it's on holes 2 or 4, it will have a 50% chance on moving to holes 1-5 and a 50% to move to hole 3. That's 2 movements out of 6 possible ones, which will lead the fox to the hole 3.
But this approach doesn't GUARANTEE catching the fox in 6 days or less.
Some quick math, it gives me a rough 70% chance by the 6th night. This is by having 20% on the first night, and 33% on the next nights. Anyone who could confirm, plz comment below.
what if the fox decides to *never* enter hole 3? how many days would it take to catch it? :)
Yes, and that's why my approach is not the best approach, but it gives a fair chance of success. But if you bring it to the example given, there's two times it actually coincides that the fox should be in there. As you said, no 100% guarantee, but that's what I thought before looking st the answer. Like, the first 20 seconds.
2,2,3,4 then if you haven’t caught him go 4,3,2. I think that should work but I haven’t written anything down.
Please reply if I am wrong
Balzsack... it's really nice to see your approach. It works perfectly.
I think you can improve on this because you dont need to search hole 2 twice at the beginning. 2,3,4,4,3,2 works just the same and so does 4,3,2,2,3,4.
@@AA-100 and so 4,3,2,4,3,2 I assume
I liked your approach to this one.
I have my own approach ->
5,4,3,2,1,1,2,3,4,5
Or 1,2,3,4,5,5,4,3,2,1
Anywhere the fox goes it will get eventually caught while u implement this system
Prove ->
Suppose
Fox choose 3rd hole
Start from side (hole 5th or hole 1st)
Next day check hole 4th if u took side 5th
Or hole 2nd if u took side 1st.
Continue in this sequence.
If fox jumped twice towards your last observed hole then on your third day it is caught.
If it ran away from u then don't worry
Just keep on doing it eventually u will find out fox is getting trapped after it makes escape jump.
*Logic goes that if u have observed 1st hole but fox was at odd no. now, then it would be eventually caught and if it was at even then we simply made it to jump at odd no.*
The riddle is easier to solve by visualizing each day's status
?X???
0?X??
?0?X?
0?0X0
?0X00
0F000
where:
X is the hole we check today
? is possible current location of the fox
0 is 100% empty hole
F is the fox caught by it's tail
A Very smart visualization; what is your background? Programming? Math?
@@Asdfgfdmn thanks, i do programming
Smart one!
If you label the holes 1 2 3 4 5 then the sequence of holes you should check to grab the fox should go 3 4 3 2 2 3 4, or the reverse (3 2 3 4 4 3 2). 3 4 3 2 4 3 2 and 3 2 3 4 2 3 4 should both also work.
EDIT: After watching the video I realized that going with the latter sequence first (234 or 432) gets the first sequence (3432 or 3234) cut a day short by starting with an even rather than an odd. Although I do wonder if you averaged the catch rate of both approaches if they would equal out; the 6 day approach is more likely to catch the fox later while the 7 day approach is more likely to catch the fox earlier.
Actually, why not do the math here?
The chance the 7 day sequence catches the fox on day 1 is 1/5. The chance it catches the fox on day 2 is also 1/5. Day 3 is 1/10. Day 4 is also 1/10. Day 5 is 1/5. Day 6 is 1/10. Day 7 is 1/10.
Ok, so the chance you catch the fox by day 1 is 1/5, by day 2 is 2/5, by day 3 is 1/2, by day 4 is 3/5, by day 5 is 4/5, by day 6 is 9/10, and by day 7 is 5/5
The chance the 6 day sequence catches the fox on day 1 is 1/5. On day 2 it is 1/10. On day 3 it is 1/10. On day 4 it is 1/5. On day 5 it is 1/5. On day 6 it is 1/5.
So the chance you catch the fix by day 1 is 1/5, by day 2 is 3/10, by day 3 is 2/5, by day 4 is 3/5, by day 5 is 4/5, and by day 6 is 5/5.
On average the 7 day approach will get you the fox on day 3.6 while the 6 day approach will get you the fox on day 3.7. That means my hypothesis is correct, the 7 day approach will, on average, give you the fox sooner than the 6 day approach. Which is really weird to think about.
Hi... I have noted down your comment and I will analyze it carefully. I am really glad to see that you have analyzed it so deeply. Let me summarize your comment.
Which one is a better appraoch :
1 - An approach with least number of attempts/iterations.
2 - An approach with least average value of number of attempts (based on probability)
It's a challenging question and needs great analysis. I will try my level best to analyze it.. but I request all the comment readers to share their thoughts.
LOGICALLY YOURS I screwed up. Day 4 on the 6 day strategy should have a 3/10 chance of nabbing the Fox, with days 5 and 6 having a 3/20 chance each. This results in an average catch rate on day 3.55, making it still the optimum strategy.
@@LOGICALLYYOURS So after more thought, there might be a way to, on average, get the days down from the 6 day approach. To start, I want to try 2234432, although I think 224422442244... repeating might be the optimum solution for netting you the fox the earliest on average.
So let's do the math and see if I'm wrong or right. We'll start on the 2234432; I'm not sure if I want to do the 22442244... on this comment.
Ok, so on day 1 (2) you have a 1/5 chance of catching the fox. On day 2 (2) you have a 3/10 chance of catching the fox. Day 3 (3) is a 3/20, day 4 (4) is also a 3/20. Day 5 (4) has a 1/8 chance, while days 6 (3) and 7 (2) each have a 3/80 chance.
Averaging these results out, we get an average of 2.9625 days to catch the fox on average, with a guaranteed catch by day 7. Yeah, that is way shorter than the average method.
What is going on here is you are starting with an even to try to catch the fox whether it starts on an even or odd (which is more efficient than starting on an odd and trying to catch the fox that way), but instead of focusing down the fox starting on an even first you focus down the fox starting on an odd first, which is more likely. But you first take your chance at an even fox. You get your 2 best chances to catch the fox at the start and from there-on out the chances decrease.
The 22442244... method, although never guaranteeing you the fox, should mean you always pick the highest chance you catch the fox (or picking for having the highest chance to catch the fox on the next pick). By placing the higher chances of you picking the fox sooner and the lower chances later, you might be able to get the average down as low as it can go even if you can theoretically never catch the fox.
This is an interesting question, but remember to consider conjunction. The probability of any strategy succeeding on day 1 is 1/5. If you picked 2 or 4 on day 2, then day 2's probability of success is 1/4 because 1 or 5 is impossible given day 1's guess, but you still have to multiply .25 by .8 because you only get to day 2 if day 1 did NOT succeed. And then you have to multiply day 3's success probability by .75 and by .8 because you only get to day 3 if you did NOT succeed day 1 and did NOT succeed day 2. And so on. By day 6, using the deductive strategy, you are multiplying everything times 1, so the conjunctions stop meaning anything.
Maybe some strategies have a steeper probability curve early on, but getting to 100% sooner probably helps the average...
Thanks for sharing..very interesting puzzle..
I solve it like this: F denotes the possibility of the fox being there and N: the absence.
On the first morning, the fox can exist anywhere so FFFFF denotes it. In the next morning a hole can have fox only if there's at least one fox in its neighborhood. So it goes like this:
FFFFF: FNFFF(checking hole 2):NFFFF(next morning):NFNFF(checking hole 3):FNFFF:FNFNF(hole 4): NFNFN:NNNFN(hole 2): NNFNF:NNNNF(hole 3):NNNFN
And finally checking hole 4
So in short check like this and surely you'll find the fox: holes 2 3 4 2 3 4
I like this notation
I look in every hole each day because I'm not bound by your rules and I'm trying to find a dang fox.
If you fill it with mud every other day you'll catch the 🦊 in 3 days
This was close to my solution to just cover each hole, one per day, until you catch the fox.
Damn... Even I wish I would get to enter a different hole every day ( if you know what I mean ).
Do you want a job of call boy 🍌
Wow 2 years old comment but got only 5 likes ....lol
what do you mean?
is this a practical solution?. Should the fox wait or move according to the human Trial & error procedure.
This didn't seem impossible but took long time to solve for me lol
According to your strategy it takes atmost 6 days
But if u start from day 1 from hole 1 and next day hole 2 and next day hole 3 and next day hole 4 and at last however it must caught at 5 th hole
atmost it must caught within 5 days (atmost 5)
Rip logic..what happen it was in hole 2 on day 1 and hole 1 all other days
I thought this: name the consecutive holes A B C D E. Check B - C - D - B - C - D. In the word case you find the fox at sixth check in D.
that's perfect :)
LOGICALLY YOURS that's exactly same as ur method, just manipulated it into alphabets
Or sooner. And to quote the narrator, "then, it's fine."
Whilst this method is the quickest surefire way of finding the fox, there is another method which has a smaller expected value for the number of days it takes to find the fox, but has a maximum number of days of 8:
day 1: try hole 2 (if not found, it could be in 1, 3, 4 or 5) - success rate 20%
day 2: try hole 2 (if not found, it could be in 3, 4 or 5) - cumulative success rate 50%
day 3: try hole 4 (if not found, it could be in 2, 3, or 5) - cumulative success rate 75%
day 4: try hole 3 (if not found, it could be in 1, 2, or 4) - cumulative success rate 77.5%
day 5: try hole 2 (if not found, it could be in 1, 3, or 5) - cumulative success rate 80%
day 6: try hole 2 (if not found, it could be in 4 only) - cumulative success rate 87.5%
day 7: try hole 3 (if not found, it could be in 5 only) - cumulative success rate 93.75%
day 8: try hole 4 where you will find it - cumulative success rate 100%
The expected days needed to find the fox is 3.1625 which is lower than the 3.55 days described in the video.
Very nicely explained. Thanks!
Why would i do these things !!
(Go out of box) keep piece of meat .
And see from which hole he is coming from 😄
Your strategy is taking six days mine just 2 min 😄😂
Can't we just wait in any one hole🐾!
no because it can jump from left to right indefinitely
In that case there will be another man the next day searching for fox as well as you ..But he wont be able to find you somehow
To be honest, since it wasn't specified other than "What strategy would ensure that the fox is eventually caught?", I would start at the far left hole and if he's there' great, and if not then I FILL THE HOLE. I would continue moving to the right-most hole repeating my filling of a hole he wasn't in until he was eventually found as he would run out of left/right decisions quick enough. The best part is, if I saw that a previously filled hole was now open again, that's the first hole I would check when it's time and BOOM...fox.
Remember, they just asked what strategy would ensure capture, and didn't mention that I couldn't think outside the box. So that would be my strategy.
If fox had a google account, they'll track the fox for you ;)
Super answer
while not the most optimal solution it would be fairly easy to code
the sequence 1-5 will catch the fox if he starts on any odd hole
if 1-5 misses, do sequence 5-1. if the fox is in an even hole on your 5th check at hole 5 then if you check hole 5 on your 6th check the parity of the fox reverses meaning you'll find it within 10 moves
even though the example in the video can solve it in 6, I think my solution for code is slightly better since it's far more extendable.
if there were 7 holes you'd have to add extra logic for the optimal solution, but if compute time isn't an issue hitting all the holes in forward then reverse order works for any number of holes with no need for any updates to the algorithm.
(I'm sure an optimal algorithm that handles any number of holes is possible, but that would require more time to implement. if would take about 5 minutes to implement my proposed solution, which would be enough to use until a better more efficient algorithm could be implemented)
Checking the outer holes is unnecessary. So an algorithm that always works (with N holes) is "from hole 2 to hole (N-1), and then from hole (N-1) back to hole 2", which will take 4 days less than your solution.
So for example, with seven holes, an optimal solution would be 2-3-4-5-6-6-5-4-3-2 , which takes (at most) 10 days.
Holy shit, I actually solved it with the method in the video.
Congratulations you have been selected in google
Holy shit
If fox can only go over one hole then how could it be in odd numbered hole.
Either you choose 2 or 4 and move rightwards and left wards respectively, then we'll get the fox.
If i have chosen H2 for inspection then that time fox is either in H4 or in H2, Because as per question it'll move every night one hole only. So, it would neither be in H3, H1 nor in H5.
Then what is the basis of case 2, I know there is some reason that's why include Case2 and which I am missing. Please clear my confusion.
This test is strangely written.. if I have to "eventually" catch it, I'd just check the same hole every day. Given an infinite amount of days then my chance of catching it is so close to 100% so as to not make a difference.
Incorrect, as you have no idea where the fox is when it starts, it could be bouncing between two holes that you never check.
I heard a similiar riddle, but there was 100 holes and fox could just jump between the same 2 holes all the time
Update the question as follows: the fox knows your future actions and she will do everything (within the rules) to protect herself.
I have a strategy in 8 days: 2-2-4-4-2-2-3-4.
You start with 2-2: No catch? You know the fox is not in 1 or in 2.
Then you continue with 4-4: you know the fox is not in 4 or in 5. So it means it was in 3. But it has moved two times. So now the fox is in 1 or 3.
You continue with 2. Still no fox? It means it was not in 1 and it was in 3. Now you have to catch him.
2 again. Still not? The fox must have moved to the right in 4.
3. We're all most finished. If there's no fox in 3, he must be in 5
4. The fox was in 5 and has to move the left and here you catch him!
Here you go, it's not the best solution but it works :)
If fox goes 4-3-2-3-4-3-2-1 your solution fails
Guys, why not just bring a couple of friends to help? Forget the cement, and checking hole 3 everyday. Bring 4 friends and have it done and dusted by dinner time : )
This works with 2, 2, 4, 4, 3, 2
In the first 2 , 2 you know fox is on 3, 4 or 5. Then you pick 4 and again 4 so you know the fox was not in 4 and 5 so when you picked the second day, the fox was in box 3. So from box 3 she can be either in box 1 or 3 since she moved 2 times when you picked the 4 and 4 so you pick box 3 so if she is not there, you pick box 2 since she is at 1 and she will move to 2
+1
Explain question clearly 😅😅😅
Indeed
Another valid sequence is 2, 2, 4, 4, 3, 2. (Why? Left to the reader as an exercise)
I'm assuming that's a typo for 2,3,4,4,3,2.
This solution has the advantage of generalising better than the solution in the video, specifically to even numbers of holes. E.g. 2,3,4,5,5,4,3,2 would catch a fox from 6 holes, but 2,3,4,5,2,3,4,5 would not, to use an ascending sequence for both parities you would have to waste a day: 2,3,4,5,*,2,3,4,5.
@@Smithers888 if the fox starts in hole one, you'll never catch the fox.
@@treytavares1727 where is your fox going on subsequent days and which of my sequences are you looking at? If the fox alternated between 1 and 2 it gets caught by the 2 in the second half of the sequence.
Easier logic to catch the fox: Tie a piece of meat to a trap and wait till the fox takes the bait. Sometimes common sense works better than mathematics😂
yup
That's not useful to a programming logic tho. This is a software company interview.
Your common sense has no value here
Wow!!! I paused the video after question.. and solved it in couple of minutes.. Then ask my friend the same question and explained the answer to her when she couldn't solve. Then watched the video further, and my explanation was line by line same as the video.. She even asaked if I watched the . video before :P :P
Kejriwal is the best person to solve this puzzle
😂😂😂😂😂
He is a Kharagpuria IITian, mind it. Never underestimate an "AAM AADMI".
He's an IITian after all
maybe i'm wrong but you can catch the fox in *max 5 days with the sequence of checks - 2,2,3,4,4.*
1 day: check 2 hole. if not there, then either in 1 or 3,4,5 holes.
2 day: check 2 hole. if it was in 1 hole, it must be in 2 in the morning ( also in case if it went to the left from 3 hole). if not we know for sure that the fox is hiding in one of 3,4,5 holes.
3 day: check 3 hole. if not found, then the fox must be in 4 or 5 hole. because the left holes were empty during all previous checks,so it cant come from the left.
4 day: check 4 hole. if not found we already know that is is hiding inside 5 hole, from which it can only move to the left 4 hole.
5 day: check 4 hole and catch it.
there is an issue... if the fox follows the seqence 4,5,4,3,2 then you will miss it. :)
LOGICALLY YOURS yup. totally missed that point.
The other challenge is to understand him
Yeah,try your luck in understanding a fox while you are being watched by human foxes
He means understand lector :D
He's quite easy to understand if you have a basic grasp of the english language.
@@dallan7740 dude I forgot about that,you think people watching an English video does not have a basic grasp of English
Yeah, the guy talking is definitely not a native English language speaker. However, I can still understand him, but with lots more intuitive attention to what he is trying to pronounce. You must have your ears out and process quickly all he is trying to say...this would not happen if a native English speaker would be presenting the video...👂👂👂
54322. This would solve it in 5 days max, possibly less. Start on the 5th hole, if the fox is not there it must be in one of the 4 other holes. Try the 4th hole on the 2nd day. If it's not there it must be in 1,2 or 3 since there is no way for it to get to the 5th. Try the 3rd hole on the 3rd day. If its not there it must be in 1 or 2 since there is no way for it to have moved to 4 or 5 based on the constraints of this question. Try the 2nd hole on the 4th day. If it is not here then it must be in the 1st hole, which means it will have to move to the 2nd hole on the 5th day. This solution could also work in the order 12344.
If the fox goes 21234 (or _any_ other route that brings hiim to hole 4 on day 5) then it doesn't get caught.
Several logical options include;
1. Learn about the natural predators of the fox species involved, then buy 4. Or
2. Obtain 5 baited traps. Havahart (tm) live traps will not kill the fox. Or
3. Hire a Hunter looking for fox fur.
2,2,3,4,4,3,2,2,3,4,4,3... until you find him. He won't be able to avoid you.
Put some food near there the fox will come out itself. 🤣
First day, check hole 2, let us consider it is not found, then it must be in hole 4.
2nd day, check hole 3, let us consider it is not found, then it must be in hole 5.
3rd day, check hole 4, it must definitely be found in hole 4 because it is the only option beside hole 5.
This is the optimal solution, because, we will find it definitely in less than or equal to 3 days
or may be if you choose it may be in 1st hole and if you move to third rat will move to 2nd
I found the answer in a different way. It took me more days than the optimal solution though.
Label the 5 holes, A, B, C, D, E.
1. Check B. If the fox is not found in B, then the fox moved from B->A, B->C, C->D, D->E, or E->D.
2. Check B again. If the fox is not found in B, then the fox moved from C->D, D->E, D->C, or E->D.
3. Check B again. Now you have two possibilities. 1) The fox moved from initial position D to a different position (D->C or D->E). or 2) The fox moved from a different position to D (C->D or E->D).
4. Check C. For possibility 1, the fox would have moved from C->B or E->D. For possibility 2, the fox would have moved from D->E, and that's the only possibility if the fox is not found in step 4.
5. Check D. If the fox is not found in position D, then possibility 2 is no longer valid. Therefore, we can conclude one of two possibilities - Possibility 1: the fox moved from C->B just before step 4 Possibility 2: the fox moved from D->C just before step 5. If possibility 1 is true, then the current position of the fox would either be A or C.
6. Check D again. If the fox is not found in this step, we can conclude two possibilities. For initial possibility 1, the fox would have to move from A->C or C->B. For initial possibility 2, the fox would have to move from C->B.
7. Check C. If the fox is not found in this step, then the fox must have moved from B->A.
8. Check B. The fox is found.
You can omit step 3. With the step 2 you can come to the same conclusion as step 3.
By my strategy, you will need only 4 days
1. Start with 2 or 4 ( if u catch he was here )
2. Stay in the same place ( if u catch he was in the corner )
3. Move towards the longer stretch, ie towards 3
4. Continue in the direction from 2>3>4 or from 4>3>2
That should be it..
If you start with hole 2 and the fox started in hole 4, then no matter how the fox moves, it will not get caught. (Likewise if you start with hole 4 and the fox started in hole 2.)
Love these questions... Looking forward to more :)
Solved in 3 minutes:) maybe I should apply to Google:)
Night 1 waite for the fox to move holes and shoot it. How hard was that?
Laughing. like hard to get a job. no offence.
As hard as it is for you to read and follow directions.
@@drewpierpont3361 I try to leave "following directions" for people that cant think for themselves.
lol dude. You wont even get hired for 'thinking outside the box' since the solution you came up with is not only avoiding the spirit of the puzzle, but also inconvienient. Why stay awake all night if you could just inspect all 5 holes one by one on the same morning?
@@ullrichbrand7994 That's ok i have a great job. Lately iv bin saving them a whole lot of money thinking outside of the box.
My solution, check holes 2, 2, 2, 3, 4
On the last day - if the fox isn't in hole 4, then it's in hole 5.
What about foot prints of fox, we could easily find out where the fox is by just inspecting where the footprint goes......
Feeling bad for Hole 1
Think outside the hole??
Here’s how to simulate the fox movement in Google Sheets. Put this formula into cell A1:
=RANDBETWEEN(1,5)
Put this formula into A2:
= if(A1=1, 2, if(A1=5, 4, if (RANDBETWEEN(1,2)=2, A1+1, A1-1)))
Copy cell A2 into cells A3 through at A6. The cell references will update automatically. You will get the random movements of the fox.
This will allow you to see how a pattern that you try out against the fox will work. You should be able to test which solutions will work consistently against the fox. (If you want to test patterns of more than 6 movements then copy the A2 cell down through at least cell A20 or so.)
The correct strategy is to check all of the holes in the first morning.
The only strategy that I came up with was to check either 2 or 4 but stick to the same option, 2 or 4. I don't think you can add anything to a strategy by stating initial condition of odd or even, because this is not known and there is no stipulation that the starting state would ever change or reset, so that can be totally removed from a strategy.
Same here. 2, 2, 3, 4, 4.
@@nmklpkjlftmch That was exactly my solution as well. Except I needed one more 3 at the end.
@@nickmatveev2670 I think I've just seen a flaw in my plan. If the Fox is in 3 after the second day, then he can jump to 2 when I look in 3.
Solution in the video is the fastest method to be certain to catch the fox in 6 days. Checking a box twice in the beginning does nothing, as the fox can just jump back and forth somewhere else.
@@ne5o2 ahhhh.. I see.
Took me about an hour of thinking, but yeah. I was correct.
Good luck! You're gonna get job in Google
Hole 1 be like....
Oo bhai maaro mujhe maaro...
Ni ye majak ho raha h
Start with hole 2 then hole 2 again
If you didn't catch it you now sure hole1&2 are empty
Then go to hole 4 if it is empty you now sure hole 1& 4 are empty
Then go again to hole 4
If you didn't catch it now you sure that hole 4 & 5 & 2 are empty
Now the Fox in hole 1 or 3
So go to hole 2 if you didn't catch it now you sure that the Fox in hole 4
Then go to hole 3 if you didn't catch it now you sure that the Fox in hole 5 now you can catch in next day in hole 4 because no choice for him .
Ali Shaker same here, just need 4 days
after second time checking 4th hole you know 4&5&3 are empty, but it could be in 2...
IF: Fox start in 3, you check 2. Fox jumps to 4, you check 2. Fox jumps to 3 you check 4. Fox jumps to 2!! and you check 4 second time.
U r wrong bro. The second reply answers perfectly for your statement
If it starts from the middle hole. Let it be H1 to H5
From H3, it can hop to H2 or H4. Worse case scenario, you check H2, it's at H4. Next, it can move to H5 or H3. Check H3. If it's not there, check H4 the next day bcuz there's no where left to run
If it starts in a random hole, block H1 on day 1, H2 on day 2, etc.
Haven't watched the vid btw.
Edit I'm wrong
Fox puzzle was easy. The more challanging puzzle was to decrypt your accent
His accent is similar to 84% of google employees
Decrypt?
The bigger challenge is to improve your English. Idiot. Wannabe Einstein
How many languages do YOU speak?
"encrypt your accent"
I didn't think of this odd even method, but my solution also relied on holes 2 and 4.
I start at 2 and repeat it to catch the fox in case it was in 1. Otherwise I know it was in 3, 4 or 5. Then I check 4 twice with the same idea. Since it wasn't in 4 or 5, it had to have been in 2 or 3 at the time I checked 4 the first time. Now I could calculate all the possible moves by the fox and try to catch it at 2, checking it twice again. Since I didn't catch it, it must've moved from 4 to 3 to 2 to 3 to 4. So now I know the last location was 4 and thus the fox must now be at 3 or 5 and I can solve the end like in the video. This method took 8 days, however. Less elegant, but it worked. :)
After checking 4 twice, the fox can be in 1, 2 or 3, so you're exactly back to the case where you have eliminated 2 positions, so if your method works, it can probably be reduced to 6 days by removing the first two.
However, I don't think it works: over the 8 days, the fox could do 3-4-3-2-3-4-3-2 while you check 2-2-4-4-2-2-4-4.
Pick a random one, if you don't find it , block that hole... it will take 5 days..
idiot read the question properly
The question didn't give any limitations. Why do we only block one hole per day? Just look at every whole on the first day. Gg
Can't the rule is 1 hole a day.
I can tell two of you tried to pull this shit on board games when you were little. "You don't HAVE any money because I'm stealing it and I'm bigger than you!!" How's that working out in life outside of youtube riddles?
My solution was 223344. If it's in hole 2, you caught it. If it's in hole 1, you caught it on day two. If you didn't find it then, you ruled out holes 1 and 2. Move to hole 3 to catch it day three or four. If not, it's either in hole 4 or 5, which you will catch on day five or six. Same time it would take the uploader. Either way works.
I guess it could pass from 4 to 3 when I go from 3 to 4. I concede. My theory is flawed.
Logic says look at all the holes on the same day, this has nothing to do with logic lol
Exactly! logically correct
I think that your thoughtprocess is correct, but how do you determine whether the fox started in an even or an odd hole? It has to be given to follow a strategy
It doesn't have to be given, because the strategy is the same strategy regardless. Search hole 2, then 3, then 4, repeat. On or before day 6, the fox will be found with 100% certainty. Finding it on day 6 with this strategy is a worst case scenario, making this the optimal solution (along with similar solutions, like 2,3,4,4,3,2).
Just check the same hole every morning....
All you need to do is "ensure the fox is eventually caught."
yup
I solved this guaranteed in 5 tries. Am I wrong. Check hole 2 twice and hole 3 twice, then you have your answer. I'm pretty sure this scenario captures all processes of elimination? Please reply if I am wrong! Thanks!
it could jump between 4 and 5
or u check 2 its in 4 u check 2 again and its in 3 , then u check 3 but its moved to 2 , u check 3 again and its in 1
Check the centre hole repeatedly as statistically it's the one he'll spend the most time in. Eventually he will land in it and you will catch the fox.
Assuming his motion is random that is
@@richardhp77 suppose the fox only shifts between 1 and 2 or 4 and 5 and never jumps to the center hole. The movement will be allowed coz it is alternate right & left movement. So, always looking at the center doesn't count for all cases.
@@kruz2919 it will eventually. Every other day, you’ll have a 50/50 of it being in 3, if it wasn’t there the first day.
@@richardhp77 yeah totally, I agree. If you hang out at 3 and it never comes to 3 because it’s afraid you will be there, then yeah this doesn’t work. Like you said, we are assuming his movement is random.
@@drummyt7166 if motion is random then ofc....that's why I stated not in all cases but in these puzzles u gotta cover the edge cases as well since u have to consider all possible cases and if ur solution checks for every single one of them with the smallest possible sequence then that's the optimized one.
I think 2, 2, 3, 4, 4 should catch him no matter what. Nice puzzle
If fox goes 4->3->2->1->2, you won't have caught him.
Actually your solution is correct but it is not an optimal one in all cases. Your solution has the lowest max days to find the fox.
Optimally though, one could consider the best solution to be the one that has the lowest average number of days to find the fox OR even the lowest average number of holes that need to be searched (how much effort you have to do). Its pretty amazing. All of them have different solutions!!
Your solution: { 2, 3, 4, 2, 3, 4 } :
Max days to find fox = 6, Average days to find fox = 3.55, Average effort needed = 3.55 hole searches
Alternate optimal solution #1:
{
2, 2, 4, 4, /* this search pattern is repeated forever */
3, 2, 2, 3, 4 /* will never be reached, but can truncate forever loop early and execute this to get arbitrarily close to values */
} :
Max days to find fox = INFINITE, Average days to find fox = 2.93333..., Average effort needed = 2.93333... hole searches
Alternate optimal solution #2:
{
X /* skip searching this day */,
2, 2, 4, 4, /* this search pattern is repeated forever */
3, 2, 2, 3, 4 /* will never be reached, but can truncate forever loop early and execute this to get arbitrarily close to values */
};
Max days to find fox = INFINITE, Average days to find fox = 3.73333..., Average effort needed = 2.73333.... hole searches
HERE IS THE CODE: (You can run it on any online C++ compiler and engine)
#include
using namespace std;
// This is the probability that the fox is in particular hole
float prob[5] = { 0.2, 0.2, 0.2, 0.2, 0.2 };
// These are various choices of hole indices (zero-based) to search (uncomment exactly one of them to try it out)
//int choices[] = { 1, 2, 3, 1, 2, 3 }; // 3.55, 3.55 (Worst case is 6 days)
//int choices[] = { 1, 2, 3, 1, 2, 3 }; // 3.55, 3.55 (Worst case is 6 days)
/*
int choices[] = { 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3,
1, 1, 3, 3, // this is repeated forever
2, 1, 1, 2, 3 }; // 2.93333...., 2.93333.... (Worst case is you find the fox after an unbounded number of searches)
*/
int choices[] = { -1, // Negative number indicates skip searching on that day
1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3,
1, 1, 3, 3, // this is repeated forever
2, 1, 1, 2, 3 }; // 3.73333..., 2.73333... (Worst case is you find the fox after an unbounded number of searches)
int main()
{
int effort = 0;
float totalEffort = 0.0;
float totalDays = 0.0;
for (int day = 0; day < sizeof(choices)/sizeof(choices[0]); ++day) {
cout
The problem clearly states: "what strategy would ensure that the fox is *eventually* caught". Any option which has max-time=infinite is not a solution to the given requirements. :)
Most of the time, a well done requirement analysis can save you months of coding ;)
And you should read the code before commenting. It clearly does not go on forever. You can terminate the infinite loop at whatever time and find the fox. You can get arbitrarily close to those numbers by terminating early. In fact the solutions in the code do terminate early. In fact it does not really take too many iterations to be very close indeed and have much better results on average than the proposed solution.
P.S. That's not months of coding (just takes about 20 minutes or so)
Ameya Limaye how did you get the average number of days as 3.55?
What if suppose I check first hole in day 1, if found, fine; if not then it is in rest 4 holes... The only possible case it can came back to hole 1 in day 2 is if in day 1 it was in hole 2 --> come back to hole 1 in day 2 as well, if found fine, if not there is no chance that the fox will be able to get back to hole 1 in day 3 --> hole 1 is out of consideration now.
In Day 3 come and check the hole 2, if found okay o.w. it must be on hole 3,4,5...since the fox can't came back to hole 1 in day 3.
Iteratively in this way we can eliminate all the holes staring from hole 1 untill the fox is found.
This works na ??..
Do some investment and put a camera with tripod in front of hole.... Very next morning fox will be caught... Change with technology dude 🤖
1 off from optimal, got 3, 4, 3, 2, 2, 3, 4. The fox is still caught, but the solution is not optimal because I started looking for the fox with odd parity, which will always require an extra step. I missed that starting even would shorten the length, since finding an even fox is an odd number of steps, which switches a fox starting in an odd hole to the even holes, again requiring only three steps
I'll Just look at one hole everyday
Great one! I thought the puzzle didn't have an answer.
So close.. I solved it on 8 days with a different strategy... but this one is 2 days faster
So did I.. out of curiosity did you start at the end and go 5,5,4,4,3,3,2,2?
@@matthewfinis6723 falsified by fox: [2, 3, 2, 3, 4, 5, 4, 3, 4]
I found a different way
224432
You start with hole 2. If it's there, you catch it. Then you check it again. If it was in 1, or moved there from 3, you catch it. If you haven't, you now know it's in 3,4or 5.
Now we apply the even odd logic. If it's in an even hole, it's in 4. If it's in an off hole, it's 3 or 5. You check 4. If you find it, it's done. If not, it's odd. So it was in 5 or 3. If it was in 5, it must move to 4. If it's 3, it can move to 2 or 4. Check 4. If you find it, it's caught. If not, it was on 2.
From 2, it could move to 3 or 1. Check 3. If it's not there, it moved to 1, so it must move to 2 afterwards, and checking 2 will catch it.
Fox could go 432123 and would not get caught.
Ah, I wasn't properly tracking how the knowledge of where it is expands between steps
You can catch it by just inspecting each hole twice and then moving to the next. Lets say you do 1, 1, 2, 2, 3, 3, 4, 4, 5, eventually you will catch it but its not best case. Your algorithm is better for the best case
this will not work
@@karunesh26march why would it not work? You go from one side to the other thus youndont give him a chance to dodge it
For example, say day one you inspect hole 1 but the fox is in hole 4.
Day 2 you inspect hole 1 again, the fox moves to hole 3.
Day 3, you inspect hole 2, fox goes to hole 4.
Day 4, you inspect hole 2 again, fox moves to hole 3.
Day 5, you inspect hole 3, fox moves to hole 2.
From here on the fox goes between hole 1 and 2 every day and you wont catch it.
+1up, Your proposed strategy is flawed. Even _two_ independent foxes that are restricted to not occupy the same hole at the same time, could still both escape from being caught. For example:
Day : 1 2 3 4 5 6 7 8 9 10
Fox 1: 2 3 4 3 2 1 2 1 2 1
Fox 2: 5 4 5 4 5 4 3 2 3 2
You : *1 1 2 2 3 3 4 4 5 5*
The solutions given by the video will catch _all_ foxes (even if there are two or more foxes that are also not prohibited from sharing a hole at the same day).
Yes - but there is no need to visit hole 1. Since the fox always has to move each night, visiting hole 2 twice will catch the fox if it started in hole 1.
Case 1 : 2-3-4
Case 2 : leave day one. 2-3-4
3+3 days of inspection