Groundhog Puzzle [duplicate]Sink the SubmarineWhy does this solution guarantee that the prince knocks on the right door to find the princess?Pythagorean walkBlock the snake from reaching pointsThe Circular Prison of Unknown SizeFind the fastest path through this Brazilian concretist poemThe lost drone at the Great Wall of ChinaOptimal path around a variable-position wallPFG: A pretty spiral!Prison Pizza Partylolcatz can haz ur infinit cheeseboard
How is Arya still alive?
Identity of a supposed anonymous referee revealed through "Description" of the report
Why does this pattern in powers happen?
Is there a reason why Turkey took the Balkan territories of the Ottoman Empire, instead of Greece or another of the Balkan states?
Steganography in Latex
How can it be that ssh somename works, while nslookup somename does not?
What is the Ancient One's mistake?
Movie where heroine wakes up to a mirror image enemy that copies her every move?
Align a table column at a specific symbol
What computer port is this?
How do I politely tell my players to shut up about their backstory?
Creating Stored Procedure in local db that references tables in linked server
I want to write a blog post building upon someone else's paper, how can I properly cite/credit them?
Can the president of the United States be guilty of insider trading?
Exactly which act of bravery are Luke and Han awarded a medal for?
Can you turn a recording upside-down?
Why did Missandei say this?
Was Mohammed the most popular first name for boys born in Berlin in 2018?
Why are thrust reversers not used down to taxi speeds?
Is it safe to keep the GPU on 100% utilization for a very long time?
How do I minimise waste on a flight?
What will Doctor Strange protect now?
How long can fsck take on a 30 TB volume?
How do I give a darkroom course without negatives from the attendees?
Groundhog Puzzle [duplicate]
Sink the SubmarineWhy does this solution guarantee that the prince knocks on the right door to find the princess?Pythagorean walkBlock the snake from reaching pointsThe Circular Prison of Unknown SizeFind the fastest path through this Brazilian concretist poemThe lost drone at the Great Wall of ChinaOptimal path around a variable-position wallPFG: A pretty spiral!Prison Pizza Partylolcatz can haz ur infinit cheeseboard
$begingroup$
This question already has an answer here:
Sink the Submarine
3 answers
A groundhog has made an infinite number of holes one metre apart in a straight line in both directions on an infinite plane. Every day it travels a fixed number of holes in one direction. A farmer would like to catch the groundhog by shining a torch into one of the holes at midnight when it is asleep.
What strategy can the farmer use to ensure that he catches the groundhog eventually?
mathematics
$endgroup$
marked as duplicate by Jaap Scherphuis, Glorfindel, Gareth McCaughan♦ Apr 29 at 16:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Sink the Submarine
3 answers
A groundhog has made an infinite number of holes one metre apart in a straight line in both directions on an infinite plane. Every day it travels a fixed number of holes in one direction. A farmer would like to catch the groundhog by shining a torch into one of the holes at midnight when it is asleep.
What strategy can the farmer use to ensure that he catches the groundhog eventually?
mathematics
$endgroup$
marked as duplicate by Jaap Scherphuis, Glorfindel, Gareth McCaughan♦ Apr 29 at 16:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Sink the Submarine
3 answers
A groundhog has made an infinite number of holes one metre apart in a straight line in both directions on an infinite plane. Every day it travels a fixed number of holes in one direction. A farmer would like to catch the groundhog by shining a torch into one of the holes at midnight when it is asleep.
What strategy can the farmer use to ensure that he catches the groundhog eventually?
mathematics
$endgroup$
This question already has an answer here:
Sink the Submarine
3 answers
A groundhog has made an infinite number of holes one metre apart in a straight line in both directions on an infinite plane. Every day it travels a fixed number of holes in one direction. A farmer would like to catch the groundhog by shining a torch into one of the holes at midnight when it is asleep.
What strategy can the farmer use to ensure that he catches the groundhog eventually?
This question already has an answer here:
Sink the Submarine
3 answers
mathematics
mathematics
edited Apr 29 at 13:24
Glorfindel
15k45788
15k45788
asked Apr 29 at 13:14
Jeff BehJeff Beh
391
391
marked as duplicate by Jaap Scherphuis, Glorfindel, Gareth McCaughan♦ Apr 29 at 16:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Jaap Scherphuis, Glorfindel, Gareth McCaughan♦ Apr 29 at 16:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The farmer can
enumerate all the possible groundhog-trajectories -- there are only countably many of them -- and then on day N shine the torch into the hole the groundhog will be in on day N if it is on trajectory N.
More concretely
associate with the number $2^a3^b5^c7^d$ where $a,b,c,d$ are non-negative integers the possibility that the groundhog is at position $(-1)^acdot b$ on day 0, and moves by $(-1)^ccdot d$ on each day. List all positive integers in order, one per night, and when on night $n$ you find one of the form $2^a3^b5^c7^d$ shine the torch into hole $(-1)^acdot b + ncdot(-1)^ccdot d$. (There are much more efficient strategies than this one, but clearly the farmer has all the time in the world and more in any case.)
$endgroup$
1
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
2
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
add a comment |
$begingroup$
Extending Gareth McCaughan's answer, the farmer can:
Enumerate all the possible options. Draw a diagram with "starting position" on the X axis, and "groundhog speed" on the Y axis. Hit all the points on the integer grid for that diagram.
For example, follow the path:
Start at the red "X" (the origin) on day 1, then follow the arrows to all the grid points.
To determine which hole to illuminate each day:
Pick an arbitrary hole to label hole zero, then number the rest like a number line. The hole ($H$) to illuminate on day $d$ is: $H = x + d times y$. For example, on day 1, illuminate the arbitrarily chosen hole 0. On day 2, illuminate hole 1. On day 3 illuminate hole 3, etc. On day 16, the grid position is (1,2), so the hole would be number 33.
This ensures that no matter which hole the groundhog started in or how many holes it moves each day, the farmer will eventually catch him.
$endgroup$
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
add a comment |
$begingroup$
The farmer should
Look in the hole that is the number of days since started squared (e.g. 1, 2, 9, 16, etc.).
Because of this, the farmer will eventually catch the groundhog on day N, where
N is the number of holes the groundhog moves per day.
EDIT: Just realized that this will only work assuming you know which direction the groundhog starts travelling in. I will leave it here in case it gives someone an idea though.
$endgroup$
1
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The farmer can
enumerate all the possible groundhog-trajectories -- there are only countably many of them -- and then on day N shine the torch into the hole the groundhog will be in on day N if it is on trajectory N.
More concretely
associate with the number $2^a3^b5^c7^d$ where $a,b,c,d$ are non-negative integers the possibility that the groundhog is at position $(-1)^acdot b$ on day 0, and moves by $(-1)^ccdot d$ on each day. List all positive integers in order, one per night, and when on night $n$ you find one of the form $2^a3^b5^c7^d$ shine the torch into hole $(-1)^acdot b + ncdot(-1)^ccdot d$. (There are much more efficient strategies than this one, but clearly the farmer has all the time in the world and more in any case.)
$endgroup$
1
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
2
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
add a comment |
$begingroup$
The farmer can
enumerate all the possible groundhog-trajectories -- there are only countably many of them -- and then on day N shine the torch into the hole the groundhog will be in on day N if it is on trajectory N.
More concretely
associate with the number $2^a3^b5^c7^d$ where $a,b,c,d$ are non-negative integers the possibility that the groundhog is at position $(-1)^acdot b$ on day 0, and moves by $(-1)^ccdot d$ on each day. List all positive integers in order, one per night, and when on night $n$ you find one of the form $2^a3^b5^c7^d$ shine the torch into hole $(-1)^acdot b + ncdot(-1)^ccdot d$. (There are much more efficient strategies than this one, but clearly the farmer has all the time in the world and more in any case.)
$endgroup$
1
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
2
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
add a comment |
$begingroup$
The farmer can
enumerate all the possible groundhog-trajectories -- there are only countably many of them -- and then on day N shine the torch into the hole the groundhog will be in on day N if it is on trajectory N.
More concretely
associate with the number $2^a3^b5^c7^d$ where $a,b,c,d$ are non-negative integers the possibility that the groundhog is at position $(-1)^acdot b$ on day 0, and moves by $(-1)^ccdot d$ on each day. List all positive integers in order, one per night, and when on night $n$ you find one of the form $2^a3^b5^c7^d$ shine the torch into hole $(-1)^acdot b + ncdot(-1)^ccdot d$. (There are much more efficient strategies than this one, but clearly the farmer has all the time in the world and more in any case.)
$endgroup$
The farmer can
enumerate all the possible groundhog-trajectories -- there are only countably many of them -- and then on day N shine the torch into the hole the groundhog will be in on day N if it is on trajectory N.
More concretely
associate with the number $2^a3^b5^c7^d$ where $a,b,c,d$ are non-negative integers the possibility that the groundhog is at position $(-1)^acdot b$ on day 0, and moves by $(-1)^ccdot d$ on each day. List all positive integers in order, one per night, and when on night $n$ you find one of the form $2^a3^b5^c7^d$ shine the torch into hole $(-1)^acdot b + ncdot(-1)^ccdot d$. (There are much more efficient strategies than this one, but clearly the farmer has all the time in the world and more in any case.)
answered Apr 29 at 13:36
Gareth McCaughan♦Gareth McCaughan
70.3k3179274
70.3k3179274
1
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
2
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
add a comment |
1
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
2
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
1
1
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
$begingroup$
Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions.
$endgroup$
– visualnotsobasic
Apr 29 at 15:40
2
2
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
$begingroup$
@visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff...
$endgroup$
– colmde
Apr 29 at 15:52
add a comment |
$begingroup$
Extending Gareth McCaughan's answer, the farmer can:
Enumerate all the possible options. Draw a diagram with "starting position" on the X axis, and "groundhog speed" on the Y axis. Hit all the points on the integer grid for that diagram.
For example, follow the path:
Start at the red "X" (the origin) on day 1, then follow the arrows to all the grid points.
To determine which hole to illuminate each day:
Pick an arbitrary hole to label hole zero, then number the rest like a number line. The hole ($H$) to illuminate on day $d$ is: $H = x + d times y$. For example, on day 1, illuminate the arbitrarily chosen hole 0. On day 2, illuminate hole 1. On day 3 illuminate hole 3, etc. On day 16, the grid position is (1,2), so the hole would be number 33.
This ensures that no matter which hole the groundhog started in or how many holes it moves each day, the farmer will eventually catch him.
$endgroup$
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
add a comment |
$begingroup$
Extending Gareth McCaughan's answer, the farmer can:
Enumerate all the possible options. Draw a diagram with "starting position" on the X axis, and "groundhog speed" on the Y axis. Hit all the points on the integer grid for that diagram.
For example, follow the path:
Start at the red "X" (the origin) on day 1, then follow the arrows to all the grid points.
To determine which hole to illuminate each day:
Pick an arbitrary hole to label hole zero, then number the rest like a number line. The hole ($H$) to illuminate on day $d$ is: $H = x + d times y$. For example, on day 1, illuminate the arbitrarily chosen hole 0. On day 2, illuminate hole 1. On day 3 illuminate hole 3, etc. On day 16, the grid position is (1,2), so the hole would be number 33.
This ensures that no matter which hole the groundhog started in or how many holes it moves each day, the farmer will eventually catch him.
$endgroup$
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
add a comment |
$begingroup$
Extending Gareth McCaughan's answer, the farmer can:
Enumerate all the possible options. Draw a diagram with "starting position" on the X axis, and "groundhog speed" on the Y axis. Hit all the points on the integer grid for that diagram.
For example, follow the path:
Start at the red "X" (the origin) on day 1, then follow the arrows to all the grid points.
To determine which hole to illuminate each day:
Pick an arbitrary hole to label hole zero, then number the rest like a number line. The hole ($H$) to illuminate on day $d$ is: $H = x + d times y$. For example, on day 1, illuminate the arbitrarily chosen hole 0. On day 2, illuminate hole 1. On day 3 illuminate hole 3, etc. On day 16, the grid position is (1,2), so the hole would be number 33.
This ensures that no matter which hole the groundhog started in or how many holes it moves each day, the farmer will eventually catch him.
$endgroup$
Extending Gareth McCaughan's answer, the farmer can:
Enumerate all the possible options. Draw a diagram with "starting position" on the X axis, and "groundhog speed" on the Y axis. Hit all the points on the integer grid for that diagram.
For example, follow the path:
Start at the red "X" (the origin) on day 1, then follow the arrows to all the grid points.
To determine which hole to illuminate each day:
Pick an arbitrary hole to label hole zero, then number the rest like a number line. The hole ($H$) to illuminate on day $d$ is: $H = x + d times y$. For example, on day 1, illuminate the arbitrarily chosen hole 0. On day 2, illuminate hole 1. On day 3 illuminate hole 3, etc. On day 16, the grid position is (1,2), so the hole would be number 33.
This ensures that no matter which hole the groundhog started in or how many holes it moves each day, the farmer will eventually catch him.
answered Apr 29 at 15:43
user3294068user3294068
5,7841729
5,7841729
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
add a comment |
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1.
$endgroup$
– Bass
Apr 30 at 7:22
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
$begingroup$
It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted.
$endgroup$
– user3294068
Apr 30 at 16:45
add a comment |
$begingroup$
The farmer should
Look in the hole that is the number of days since started squared (e.g. 1, 2, 9, 16, etc.).
Because of this, the farmer will eventually catch the groundhog on day N, where
N is the number of holes the groundhog moves per day.
EDIT: Just realized that this will only work assuming you know which direction the groundhog starts travelling in. I will leave it here in case it gives someone an idea though.
$endgroup$
1
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
add a comment |
$begingroup$
The farmer should
Look in the hole that is the number of days since started squared (e.g. 1, 2, 9, 16, etc.).
Because of this, the farmer will eventually catch the groundhog on day N, where
N is the number of holes the groundhog moves per day.
EDIT: Just realized that this will only work assuming you know which direction the groundhog starts travelling in. I will leave it here in case it gives someone an idea though.
$endgroup$
1
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
add a comment |
$begingroup$
The farmer should
Look in the hole that is the number of days since started squared (e.g. 1, 2, 9, 16, etc.).
Because of this, the farmer will eventually catch the groundhog on day N, where
N is the number of holes the groundhog moves per day.
EDIT: Just realized that this will only work assuming you know which direction the groundhog starts travelling in. I will leave it here in case it gives someone an idea though.
$endgroup$
The farmer should
Look in the hole that is the number of days since started squared (e.g. 1, 2, 9, 16, etc.).
Because of this, the farmer will eventually catch the groundhog on day N, where
N is the number of holes the groundhog moves per day.
EDIT: Just realized that this will only work assuming you know which direction the groundhog starts travelling in. I will leave it here in case it gives someone an idea though.
answered Apr 29 at 14:40
AProughAPrough
5,9061245
5,9061245
1
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
add a comment |
1
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
1
1
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
doesn't this also assume that the farmer knows where the groundhog started?
$endgroup$
– Bass
Apr 29 at 14:43
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
$begingroup$
@Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point.
$endgroup$
– APrough
Apr 29 at 14:47
add a comment |