A farmer has raised several turkeys and has sold all but one of them. The remaining turkey is destined for the farmer's family's Christmas dinner. Unfortunately for the farmer (but maybe fortunately for the turkey) a week before Christmas the turkey realises what is going on and decides to hide.
There are five huts in which the turkey can hide numbered one to five, all in a row, and the turkey hides in one of them during the night. The pattern for the ensuing search is as follows:
- Each morning the farmer looks in one of the huts.
- If the turkey is in the hut the farmer locks the door, the turkey is trapped, and Christmas dinner is saved.
- If the hut is empty the farmer leaves and overnight the turkey moves to one of the adjacent huts. For example, if it is in hut two it must move to either hut one or hut three, and if it is in hut five it must move to hut four.
- The next morning the farmer has another look, and so on.
The farmer has only six mornings left to find the turkey. Can you devise a method that guarantees that the farmer will find the turkey within six searches?
Assume for the time being that the turkey hid the first night in an even numbered hut. That is hut two or hut four.
So the farmer looks in hut two on the first morning. If the turkey is there then the search is over, and if not, the turkey must be in hut four.
On the second morning, as the turkey must now be in hut three or hut five after its overnight move, the farmer looks in hut three. If the turkey is there then the search is over, and if not, the turkey must be in hut five.
On the third morning, as the turkey must now be in hut four after its overnight move, the farmer looks in hut four and finds the turkey.
So if we know the turkey is in an even numbered hut we can always catch the turkey within three searches. However, we can't guarantee the turkey started in an even numbered hut, so this will not catch the turkey if it started in an odd numbered hut.
The good news is that if the turkey started in an odd numbered hut, after three days (and three moves) it must now be in an even numbered hut, and it can be found within three more searches.
Searching in the order two, three, four, two, three and four must find the turkey within six searches.