Pip Magic

[Istvan Lauko]

Pip the magician is to perform a magic trick with dice. He has 20 dice. The dice are regular, except that the pips (dots) on the dice could not be felt by touch.
He promises that he would rearrange the randomly rolled 20 dice into two groups so that the total number of pips on the top faces in the two groups would be equal.

In the process he can move, possibly turn any of the dice.

But you need to know that Pip is blind, so he would ask for a little help from the audience. He could ask a helper from the audience

1. To give him the total number of pips shown on the 20 dice.
2. To hand him at most two dice showing the number on the top face that he specifies.

After that he rearranges the dice as promised (of course without seeing anything).

How did he do it? Can you steal his trick?

[David Ash]

It is unclear from the problem statement whether Pip is allowed to request the audience help just once in each of the two categories or an arbitrary number of times.

If just once I am having a very hard time seeing how he would have enough information to solve the problem. Once he requests two dice with a given number, he knows the value of those two dice. He may also know the sum of the other 18 dice, but he has absolutely no information that would allow him to distinguish one of those 18 dice from any of the others, and no way of getting any more information. When he reveals his final rearrangement of the dice, he would have absolutely no basis for why he has put one of those 18 dice in one group and one in another group. And he would need such a basis to solve the problem, because he cannot guarantee that all 18 dice are showing the same number, and exchanging two of them would result in his rearrangement no longer working.

If he can repeat #2 an arbitrary number of times it is much easier. Pip keeps asking the audience for 1's and turns them over (recall that opposite a '1' on a die is a '6') so they are 6's. When there are no more 1's left he starts asking the audience for 6's, turning those over to 1's until there are no more 6's left. At this point Pip has a pile of 1's and knows exactly how many 1's he has and that there are no 6's.

Pip then does the same thing with 2's and 5's and then with 3's and 4's. At this point he has divided the dice into three groups, the size of which he knows: 1's, 2's and 3's (at this point there are no remaining 4's, 5's, or 6's). If the overall total is odd (note that he can now compute this without needing further help) he then needs to pick one last die and turn it to give an even total. He then has enough information to make the required rearrangement.

[Istvan Lauko]

Both 1. and 2. are used only once.

[Istvan Lauko]

1. To give him the total number of pips shown on the 20 dice.

2. To hand him at most two dice showing the number[s] on the top face that he specifies.

he will ask for a total, then he can ask for one die (e.g. a 3) or two dice (e.g. a 2 and a 3) to be handed to him -- once , then he rearranges.

(this assumes that all 20 dice is at his hand, i.e reachable to him). Yes, he would turn some of them over.

[Istvan Lauko]

one last attempt to clarify: in 2. if his request cannot be carried out, he can change his request until it can be carried out.

[t...@bellefleurbooks.com]

Dear Istvan:

I agree with David. As stated, the problem looks impossible. Twelve is
the greatest possible total of one or two dice, and eighteen is the
least possible total of the remainder of the twenty dice. Consequently,
you have to break up the eighteen or nineteen remaining dice when you
separate all the dice into two groups with equal totals. You know
nothing about these eighteen or nineteen dice, other than their total,
so once you split them up--unless all eighteen or nineteen happen to
roll the same--you do not know each of the two subtotals for sure, so
you have no way to know for sure whether the two groups have equal
totals.

Sincerely,

Tom

On 2021-09-30 01:24, Istvan Lauko wrote:
> one last attempt to clarify: in 2. if his request cannot be carried
> out, he can change his request until it can be carried out.
>
> On Thursday, September 30, 2021 at 1:04:55 AM UTC-5 Istvan Lauko
> wrote:
>

>> 1. To give him the total number of pips shown on the 20 dice.2. To

> --
> You received this message because you are subscribed to the Google
> Groups "Competition Corner Participant Discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to
> competition-corner-partici...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/competition-corner-participant-discussion/9805b1db-3440-4a74-93b9-7c312c26b5ddn%40googlegroups.com
> [1].
>
>
> Links:
> ------
> [1]
> https://groups.google.com/d/msgid/competition-corner-participant-discussion/9805b1db-3440-4a74-93b9-7c312c26b5ddn%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

The problem is a bit more nuanced than I originally thought, because Pip can request either one or two dice, and if Pip requests two, can request two of different denominations. Additionally, although in general Pip cannot make request #2 more than once, he apparently is allowed to do so if the previous requests couldn't be fulfilled.

Even with this slightly increased flexibility on Pip's part, however, I'm still having a hard time how Pip has even close to enough options to successfully rearrange the dice.

[t...@bellefleurbooks.com]

Dear David and Istvan:

Being able to request a particular sum on two dice--as distinct from two
dice with a particular value each--is an important clarification that
should be in the statement of the problem. To request the sum,
obviously you can go through the permutations one by one, if necessary.

Maybe instead of specifying a specific numeric total on two dice, by
naming an amount, the blind magician can specify a formula, whose
numeric value he does not know.

For example, he could first ask the total of all the dice. If odd, he
flips one die over, in order to make the total even.

Next, he divides the dice into two sets of ten dice. Then he asks for
one or two dice from the set with the greater total that sum to half of
the difference between the two respective sums of the two sets. If
given them, then he moves them to the other set. Otherwise, if not
given them, then he flips one of the two sets of ten over, in order to
make its total equal to seventy minus whatever it was before. Then he
asks for one or two dice from the set with the greater total that sum to
half of the difference between the two respective sums of the two sets.

This means being able to specify taking the one or two dice from a
particular set this way. As long as this sort of specific request is
allowed, the trick should work . . . eventually.

If the second request does not work, then the blind magician must do
something else, such as flipping an even number of dice, and/or moving a
few dice from one set to the other. There has to be a methodical way to
do this, but it may involve a lot of tedious cases.

Sincerely,

Tom

On 2021-10-02 19:16, 'David Ash' via Competition Corner Participant

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/f58a3c66-3d95-4df8-85f5-c046521d9346n%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/f58a3c66-3d95-4df8-85f5-c046521d9346n%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

Hi Tom and István,

While this could be the correct solution--and more importantly the correct interpretation of the problem--it should be noted that Pip, in making request #2, has no way of knowing what the difference is between the sums of the two subsets. So to solve this problem assuming that this is the correct interpretation requires us to make two additional assumptions:

• In making request #2, Pip is allowed to restrict the request to a subset of the original 20 dice, not necessarily all 20 dice
• In making request #2, Pip is allowed to specify an algorithm for computing the dice total (one or two dice) that he wants that the sighted audience is then tasked with executing, rather than just giving the number he wants

I think both of these should be stated in the problem statement if this interpretation is correct.

[David Ash]

Additionally if this is the correct interpretation, it leaves Pip's option #1 as a bit meaningless--knowing the overall pip total of the 20 dice doesn't really help much in determining the difference between two subsets. It does help in determining if the overall total is odd. This is of limited help though. The problem can't be solved as long as the overall total is odd, true. But the converse isn't true. If we have one 2 and nineteen 4's, the overall total is even, but there is still no way to solve the problem without turning some dice.

[Istvan Lauko]

As a hint, let us assume a pretty extreme case:

1. is given, and the total is 21.

then Pip says he does not need 2.

He can go straight ahead, turn some dice and split them up into two groups without knowing any of the face values.

[Istvan Lauko]

Tom and David,

If we have one 2 and nineteen 4's, the overall total is even: 78.

then Pip in step No. 2. would ask  for 1 die: a number 4. Then he would take 10 more dice next to the 4, and turn all of those 10 over to get one of the groups in the split with a total of 34 pips. This would work also if for instance 2 of those 4s would be swapped for a 3 and a 5, or for a 2 and a 6. And it would work for many other cases that ads up to 78.

Yes, Pip is not a magician but a mathematician,  and he has a formula in his head. And frankly, the assignment is not really fair, because there are cases when Pip would actually need to be given a choice of asking for more then two dices in step No. 2. (as many as 4, I think) for his formula to work. But these cases are so so rare that asking for two or less has never yet failed him. And requesting  dice combinations of two or less is much more impressive and simpler ( in fact he almost always just asks for one die in step 2.). So he takes the extremely small risk of failure and that's what he goes with.

Sorry for complicating... and not being fair by using a magician's dirty trick of misdirection. (My excuse is that I have seen my wife solve a variant of this problem in two minutes and she claimed that it is a well known problem. She is the problem solver in the family and I tend to trust her.)

[David Ash]

Yes, the key insight here seems to be that once Pip knows the overall total, he can flip any subset of dice (doesn't matter what subset) and the two subsets will then differ only by a known constant. I wasn't fully seeing that. Then Pip just needs to select the number of dice to flip, as well as the dice to request, to adjust said constant to zero.

If the total is a multiple of 7, like 21, Pip can always bypass step #2. If the total is 21, Pip is holding 19 '1's and a single '2'. He flips any three dice and is done, dividing the dice into that group and the other 17 dice. If the three dice flipped include the '2', the matching total is 17; otherwise it is 18.

Let's say the total is 78 as in my example that István followed up on. Pip requests dice totaling d and then flips k of the other dice totaling A, giving three groups totaling 7k-A, 78-d-A, and d. He can add the dice totaling d to the first group, and be done, if 7k+d=78-d or 7k+2d=78. István seems to be suggesting, in the other answer, that the preferred solution is to use k=10 and d=4. This will usually work but as István says there are rare cases where it might not. For example if we have 11 '3's and 9 '5's the total is 78 but there is no way to get a subtotal of four. The next best approach is to use k=8, d=11. Unless Pip is allowed to request three dice, he can't solve this one. However let's say he started with 6 '1's, 12 '5's, and 2 '6's. This also gives Pip an overall total of 78 and requests for one or two dice totaling 4 will fail again. However here he can request two dice totaling 11 and will succeed.

So yes I didn't fully see the key insight until the hint was posted. There might be a couple of interesting follow up problems. One would be to estimate the probability that Pip fails--we know it is low but nonzero. Another is whether there are any more tricky strategies that Pip could employ to salvage some of the more difficult cases. For example, if his first request of specific dice fails, are there any situations where he could turn some dice before making another request for specific dice and thereby gain some advantage?

[David Ash]

Here's an example of where Pip can salvage at least some of the 'rare' cases where the usual strategy doesn't work:

Let's say, as before, the total of the 20 dice was 78. Let's say also that requesting 4 as one die, requesting 4 as a total of two dice, and requesting 11 as a total of two dice all fail Pip. At this point Pip can do a lot of deduction to determine what the dice actually are and, in particular, he can do at least slightly better without resorting to requesting three or more dice.

At this point Pip knows he has no '4's, at most one '2', and either '1's or '3's but not both and either '5's or '6's but not both. It turns out some further cases can be eliminated by simple arithmetic and there are only two possibilities left:

11 '3's and 9 '5's

14 '3's and 6 '6's

He can then salvage these remaining cases some but perhaps not all of the time. First he picks a single die and flips it, and then requests, in turn, a single '1' or a single '2'. If either of these requests succeed Pip may be screwed. If both fail (the most likely scenario), however, Pip knows he flipped a '3' which is now a '4' and the overall total is now 79. He then requests two dice totaling 8. If this request succeeds, he can flip nine of the remaining dice and add the two dice totaling 8 to that group, and he is done.

If the request for two dice totaling 8 also fails, Pip knows he has at this point 13 3's, one '4', and 6 '6's. He can still salvage a bit more at least. He first flips the '4' back to a '3'--he should know which die the '4' is since it was the one he flipped earlier and the audience has had no reason to touch it. He then flips any of the remaining dice over in the hopes that he will be lucky and flip a '6'. He then requests a single '4'. If he gets it, he may be screwed, but if not, he now knows that he has just flipped a '6' and now has one '1', 14 '3's, and 5 '6's for a total of 73. He then flips the '3' that he flipped twice before once again back to a '4' and now has one '1', 13 '3's, one '4', and 5 '6's for a total of 74. He can then request two dice totaling 9--a request which at this point will succeed--and adds those two dice to a group of eight other dice which he flips, and he is done.

There may be other strategies that Pip can employ to reduce the already low (but perhaps nonzero) probability that Pip fails.

[David Ash]

Anyways now that I understand the problem statement for sure, I do think this is a good problem for the journal--although the original problem statement should be tightened up a bit. I was spending a lot of time looking for "tricks" and that could have been avoided--but there is still no guarantee I would have seen the key insight. The reasons why I think this is a good problem for the journal:

• There is one key insight (dividing the dice into two groups one of which we flip, and then using #2 to make any needed adjustments) which unfortunately I didn't see, but still is a good test.
• However Pip still perhaps cannot succeed perfectly all the time even with this insight, although maybe he gets there 99.9999+% of the time. This gives the problem an open-ended quality--if Pip can't quite guarantee success, how close can he get to a 100% guarantee?--which I think will be important for a journal. For the journal format, I think at least some problems need to be open-ended; problems relying solely on whether you see a single insight or not are great in an Olympiad format, but for a journal I think at least some problems need to provide people the opportunity to go beyond just one clever insight.

[t...@bellefleurbooks.com]

Dear David and Istvan:

You have indicated how to perform this trick if the dice total to a
multiple of seven. You flip the number of dice corresponding to the
multiple and separate them. In this case, only item 1 is needed.
Otherwise, after going through item 1, you must compute four times the
total modulo seven, and you must go through item 2 by asking for one or
more dice that sum to this quantity. As a consequence, the total minus
twice this quantity is now a multiple of seven, so you flip the number
of other dice corresponding to the multiple, separate them and then
combine them with the dice you asked for. If there are no such dice
that sum to this quantity, then you have to try a new quantity that is
greater by seven. This seems to work generally, as long as you allow
for asking for one, two or three dice, and as long as you have the
chance to name at least two quantities.

This process works in nearly every case. One exception is a sum of 100.
Here the quantity computed above is first one and second eight. If
every die is five, however, neither quantity works. Here you must ask
for first eight and second fifteen. There may be other cases that do
not quite work. I do not know.

Therefore, I would recommend changing item 2 to the following:

2. If, after hearing this total, Pip chooses to specify an integer, to
segregate for Pip one, two or three dice that sum to this integer from
the other dice, and, if no such dice have this sum, for Pip to specify
another integer and then to segregate for Pip one, two or three dice
that sum to this second integer from the other dice.

Sincerely,

Tom

On 2021-10-03 15:06, 'David Ash' via Competition Corner Participant

Discussion wrote:
> Anyways now that I understand the problem statement for sure, I do
> think this is a good problem for the journal--although the original
> problem statement should be tightened up a bit. I was spending a lot
> of time looking for "tricks" and that could have been avoided--but
> there is still no guarantee I would have seen the key insight. The
> reasons why I think this is a good problem for the journal:
>

> * There is one key insight (dividing the dice into two groups one of

> which we flip, and then using #2 to make any needed adjustments) which
> unfortunately I didn't see, but still is a good test.

> * However Pip still perhaps cannot succeed perfectly all the time

>> * In making request #2, Pip is allowed to restrict the request to a

>> subset of the original 20 dice, not necessarily all 20 dice

>> * In making request #2, Pip is allowed to specify an algorithm for

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/9da3e543-3fa1-4388-973e-8ea27537d16an%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/9da3e543-3fa1-4388-973e-8ea27537d16an%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

Hi Tom,

The case where Pip gets a sum of 100 is another case--like 78 and most if not all other cases which are not multiples of 7 and strictly between 21 and 119--where Pip probably can't do perfectly but can salvage at least some of the cases where the main strategy fails. In particular I think he can salvage the case where he has 20 5's without resorting to asking for three or more dice.

As you say, first he tries the main strategy of asking for a single '1' or two dice totaling '8'. If both these gambits fail, the remaining possibilities are quite few in number. Pip will know then he has no '1's, at most one '4', '2's or '6's but not both, and '3's or '5's but not both. If there are no '6's he must have 20 '5's to reach a total of 100. If he has '3's and '6's, he must have a '4' since 100 is not divisible by 3, and he has 6 '3's, 1 '4', and 13 '6's. If he has '5's and '6's, he must have a '4' to avoid exceeding 100, and has 1 '4', 18 '5's, and 1 '6'. So the only possibilities are:

6 '3's, 1 '4', and 13 '6's

1 '4', 18 '5's, and 1 '6'

20 '5's

I contend at this point Pip can solve the first case just over 50% of the time and the remaining cases 100% of the time without resorting to asking for three or more dice.

First, Pip does his best to handle the first case. He asks for two dice totaling '6'. This request will succeed iff he is dealing with the first case, and he will be given two '3's. At this point Pip has to do some guesswork and here is where he could fail. He picks two remaining dice in the hope that both will be '6's. This will succeed with probability (13/18)*(12/17)=26/51 or just over 50% of the time. He first flips one of the two possible '6's, giving (he hopes) a total of 95. He then sets aside one of the known '3's and the other possible '6', and adds to that group 11 other dice which he then flips. He will then be done if he guessed right (>50% probability) and, perhaps, screwed otherwise.

If the request for two dice totaling '6' fails he knows, with no guesswork, that he is dealing with one of the other two subcases. I contend at this point he can succeed 100% of the time without guesswork. What he then does is to try flipping one die at a time and asking for two dice totaling 5. This can only happen in the second subcase, and if it fails when he tries one die, he flips that die back and tries another die.

If this request succeeds, he knows he is dealing with the second subcase, the die he just flipped was a '6' (now a '1'), and the total is now 95. Moreover, all of the dice besides the two he was just handed must be '5's. He can flip six of them giving a total of 77, a multiple of seven. As he has a multiple of seven he can now solve the problem without further help.

Finally if the request for two dice totaling 5 fails after trying flipping every die in turn, Pip knows he is dealing with the third subcase and has 20 5's. He divides them into two groups of ten '5's, and he is done. 

[David Ash]

2. If, after hearing this total, Pip chooses to specify an integer, to
segregate for Pip one, two or three dice that sum to this integer from
the other dice, and, if no such dice have this sum, for Pip to specify
another integer and then to segregate for Pip one, two or three dice
that sum to this second integer from the other dice.

If we do this we will probably (I haven't worked out all the details) have a problem with a nice, crisp solution.

So if that is our goal that is a good way to meet it.

I would contend, however, that that should not be our goal. I believe the problem statement should be very crisp, but I also believe that at least some of the problems, especially at higher grade levels, should be open ended without necessarily having completely crisp solutions. We should also tell the students that not all of the problems may have complete solutions.

If we allow Pip the use of three dice, Pip can succeed perfectly (I think modulo my working out all the details). If we allow Pip the use of only two dice, we prevent Pip--and hence we prevent the student--from succeeding perfectly and that is a good thing. Real mathematics--even real pure mathematics--is messy and mathematicians get used to working on problems they may not be able to solve perfectly. In a journal format (unlike a brief Olympiad format) we have the opportunity to introduce such messier problems, and I believe we should do so. However we should do so honestly, and admit that some problems may not have complete solutions and in such cases we are looking for students to do their best.

Problems that are more open ended will also be less vulnerable to kids just looking up the proof on the Internet.

On Tuesday, October 5, 2021 at 9:42:10 PM UTC-7 t...@bellefleurbooks.com wrote:

[t...@bellefleurbooks.com]

Dear David and Istvan:

I tried to go through all the cases, and I found five similar
situations, as follows:

First, as you mention, for a total of 78, you are best off asking for
the quantity first four and second eleven, but if you happen to roll all
threes and sixes, i.e., 14 threes and 6 sixes, then you have to ask for
a third quantity of eighteen.

Second, similarly, for a total of 99, you are best off asking for the
quantity first four and second eleven, but if you happen to roll all
threes and sixes, i.e., 7 threes and 13 sixes, then you have to ask for
a third quantity of eighteen.

Third, for a total of 95, you are best off asking for the quantity first
nine and second sixteen, but if you happen to roll a two, a three and
the rest fives, i.e., 1 two, 1 three and 18 fives, then you have to ask
for a third quantity of two.

Fourth, similarly, for a total of 109, you are best off asking for the
quantity first nine and second sixteen, but if you happen to roll 2
ones, a five and the rest sixes, i.e., 2 ones, 1 five and 17 sixes, then
you have to ask for a third quantity of two.

Fifth, for a total of 114, you are best off asking for the quantity
first eight and second fifteen, but if you happen to roll a one, a five
and the rest sixes, i.e., 1 one, 1 five and 18 sixes, then you have to
ask for a third quantity of one.

As best as I can tell, asking for three quantities is enough in every
case--always the three smallest positive integers as quantities that are
all equal to each other modulo seven, and the above five cases are the
only ones where you need to ask a third time, so I need to change my
recommendation to the following (with or without the expression in
parentheses below):

2. If, after hearing this total, Pip chooses to specify an integer, to
segregate for Pip one, two or three dice that sum to this integer from

the other dice. If Pip specifies an integer but no such dice have this
sum, then Pip can specify another integer instead (specifying as many as
three integers in all, one at a time).

Sincerely,

Tom

On 2021-10-06 13:10, 'David Ash' via Competition Corner Participant

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/be46a81a-8d77-4f4f-9b24-be0fa5848301n%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/be46a81a-8d77-4f4f-9b24-be0fa5848301n%40googlegroups.com?utm_medium=email&utm_source=footer

[Istvan Lauko]

Thanks Tom!

That's great.

I would slightly change your wording:

2. After hearing this total, Pip may specify an integer and ask his helper to segregate for him from the other dice  one, two or three dice that sum to this integer. If no such dice combination can be found,  Pip could repeat his request with a different integer instead, at most twice -- one integer at a time.

[In practice, as a real magic trick, it may work well if we do not limit the number of dice to be summed up. In that case the grouping can be done by the helper, Pip never touching anything, and maybe finally he can select one or maybe two additional dice into the group that he turns over. Better misdirection... :)  ]