Probably incorrect example in problem 279 Two Buckets Advanced

Have a look at a small example: 7, 4 and 5. What do you get: 6 or 8? What do you get if you do it by hand?

PS Related: My solution contains the following comment: "I do not fully understand this special case". :)

Btw, please feel free to share (in a private thread) if you work out why this case is different (see my comment above).

I have only just spotted this thread and wanted to add some comments.

First I would like to explain why I prefer to comment in a public rather than a private thread. I quite agree that we don't want to tell others how to solve a problem in a public thread. However, I think that certain elements of problem discussion should be perfectly acceptable in a public thread. I think that most of us are capable of judging what is reasonable and what is not. Comments in a public thread are likely to give other users the interest and encouragement to tackle problems that they would not otherwise have attempted. My comments on this problem (see below) are deliberately designed to be readily understood by those who have already solved it (because they will almost certainly have had similar thoughts themselves). For someone who has not given any thought to the problem my comments will make little sense and be of no real use. For someone who is prepared to put in the necessary effort to understand the problem these comments might be sufficient encouragement for them to explore the ideas behind the problem in order to discover for themselves what is going on. If this leads to them solving the problem then we have achieved a successful (and well-deserved) solution which might not otherwise have happened.

My comments which are relevant to the initial ideas in the thread are as follows:

There are two repetitive sequences of moves in this problem. Following either of them results in a cycle of positions which eventually returns to the starting point. Following the other repetitive sequence simply follows the same cycle but in reverse order. The cycle contains every possible target value so these can be reached by going around the cycle in either direction. Clearly one of these directions will be shorter than the other for a particular target. The "special cases" referred to by Mathias are reasonably common. They come about because some target values can be achieved in either bucket while others can be achieved in only the larger bucket. If we follow the cycle in one direction we find that, for a target value that fits into both buckets, we hit this target value 4 times in a consecutive sequence of 4 moves. It occurs first on two moves in the larger bucket. This is followed by two moves where the target is in the smaller bucket. When we consider targets which cannot fit into the smaller bucket we clearly cannot see the same group of 4 moves containing the target value. Only the first 2 of these, with the target in the larger bucket, occur. When following the cycle in this direction we hit the target in the larger bucket first so the location of the first hit is in the same relative position for all targets.

When following the cycle in the opposite direction we have a difference, determined by whether or not the target will fit into the smaller bucket. If the target does fit into the smaller bucket we will first hit it in that bucket. The next move sees the target again in the smaller bucket. After that we have two moves with the target in the larger bucket. For targets which do not fit into the smaller bucket we will first hit the target in the larger bucket. This is two moves further into the cycle than the position where we would expect to meet a smaller target. It is this difference of two moves which causes the apparent discrepancy. The fact that it applies only to one of the two directions of travel around the cycle has probably added to the potential for confusion.

I see that Alexandr has now added a private thread on this topic. As I have not yet submitted a solution to the problem I am not able to check what has been posted. If I have just repeated what is already there then I apologise to those who have already solved the problem. However, for those who are yet to solve it, I hope that these ideas are sufficient encouragement for you to explore it for yourself in greater detail.

Hi, thank you very much for the additional insight.

However I think the "special case" is a little bit more difficult, or should I say puzzling. All three of us solvers to date struggled with a) identifying and b) handling it correctly, at least initially. Nonetheless the solutions passed the checks, so the "special case" is not too common it appears (at least for the examples).

Confusing is for instance that with buckets of sizes 4 and 7, it applies to a target of 5 but not to a target of 6.

Mathias,

In the example you gave, the targets of 5 and 6 are reached by traversing the cycle in opposite directions. Hence the difference. In a general case half of the targets will be approached in one direction around the cycle and vice versa. So half of the target values which are larger than the smaller bucket are going to appear as special cases.

On reflection, if I had foreseen that people were going to miss this aspect of the problem I should have asked for 8 sets of test data rather than 3. This would have helped to focus minds on the problem.

I know, my "special case" handling is not quite complete/correct (realised it when I cycled through solutions by hand). Results for u=2, v=9 and t=2/4/6/8 are all wrong right now I believe (for example).

I read the explanation, I kind of understand it, but my mind is still struggling to translate this to a mathematical justification. Good discussion!

In view of all of the discussion above, it seems sensible for me to post my solution to the problem. I have added comments to it which (hopefully) will make it easier to understand.

When setting the problem I had no intention of asking for target values of U, V or 0 since these are trivial and it would require only a trivial addition to the code to trap these values.

Similarly, I ensured that all examples had gcd(U,V) = 1. Any examples where gcd(U,V) = g (> 1) are trivially converted to the former by dividing U, V and T by g. (Note that T must be divisible by g or the problem has no solution.)

In view of the above my solution does not cater for any of these possibilities. The code is trvially modified to include them but the problem generator will not set them.

Alexandr,

Apologies. I thought I had pointed out the assumptions that I had made in the problem generator. I forgot that one of these was to make U greater than V. Again it is a trivial change to the code to swap U and V if they are in the wrong size order. This wasn't necessary for my solver since I knew that the order of U and V would always be U > V.

I hope this now clarifies the issue.