Wikipedia:Reference desk/Archives/Mathematics/2018 April 10

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 10

Worst hand in the addition game?

The following is the addition game (which I'm not sure whether it has been produced or not): Multiple players draw from a deck with X copies of the numbers 0-9 (X pretty big). Players may lay down cards out of their hand to form any addition of positive natural numbers and their sum. So for example, if your hand contains a 0,1,1,2,2,3,4,5,6 among its cards, then you could play 162+45+3=210. For example, a player could have a had with 12 7's and not be able to play, but if they have 13 7's they could play 7+7+7+7+7+7+7+7+7+7+7=77. What is the largest number of cards that a player can have and *not* be able to play?Naraht (talk) 08:57, 10 April 2018 (UTC)

As an upper limit, that number can not be larger than 10. If you have 11 cards, at least two of them must be equal, and you can at least play those two. ◄ Sebastian 09:25, 10 April 2018 (UTC)

My hunch is that the number is 6, with only the following threetwo unplayable hands: {0,5,6,7,8,9}, {0,4,6,7,8,9}, {0,4,5,6,7,8}. I think you can change any of the cards from one those hands, and it will either change into one of the other two hands, or become playable. ◄ Sebastian 10:05, 10 April 2018 (UTC)

I think (0,5,6,7,8,9) is playable: 58 + 9 = 67. Gandalf61 (talk) 08:20, 11 April 2018 (UTC)

Good catch. I'm striking it out. ◄ Sebastian 10:29, 12 April 2018 (UTC)

Assuming that you have to play all of your cards (otherwise the 12 7's example from the OP could be trivially solved)(as all of OP's example at the time of this message used all cards), then if you had $x-1$ 0's and 1 of any non-zero number $a$, then you can never have a solution as you'd just end up with $0=a*10^{n}$, which is obviously false, so there is no finite largest number of cards where you can't play. Iffy★Chat -- 09:51, 10 April 2018 (UTC)

I took the wording "cards out of their hand" to mean an explicit condition to the contrary. But you're right, the fact that there are solutions for 12 7s indicates otherwise. At least it's more interesting if we allow choosing cards. ◄ Sebastian 10:06, 10 April 2018 (UTC)

Correction: The hand of 12 7s is playable under either interpretation of the rules, since 777777=777777. ◄ Sebastian 10:46, 10 April 2018 (UTC)

OP here. The requirement is that the addition *must* have at least two addends in the total. Specifically 777777=777777 doesn't work since there must be at least one '+' so 777777+0=777777 would be a valid play. And just as {0,4,5} is an unplayable hand, so is {0,0,4,5} is unplayable. And with {7,7,7} is also unplayable. And the player is not required to use all cards in the hand at once, just those that would make a valid addition.Naraht (talk) 20:30, 10 April 2018 (UTC)

Even with the amended rules, {0,5,6,7,8,9} should be playable per Gandalf61's solution above. And btw., if H is a playable hand, then H ∪ {0} is playable, too, since one can always add an extra 0 to either side of the equation. ◄ Sebastian 10:29, 12 April 2018 (UTC)

What does it matter that {0,5,6,7,8,9} is playable? The OP asked for the largest unplayable hand. With the rules that the LHS contains at least two terms and the RHS contains exactly one, a hand of 12 7's is unplayable, so the answer is at least 12. The OP has also specified you don't have to use all cards, so any superset of a playable hand is playable. But that doesn't answer the question at all. We need to either find a larger unplayable hand, or prove that none exists. I don't know how to do that, though. -- Meni Rosenfeld (talk) 14:14, 13 April 2018 (UTC)

• There is no largest unplayable hand. Unless I am missing something, {0,0,...0,1} with any arbitrary number of zeros is unplayable.

Before you come up with an additional restriction to kill that obvious solution, here's something else. Notice that the modulo 9 residual of either side depends only on the digits that were grouped in that side and not on the way these were grouped into numbers or sums (see casting out nines). In particular, if we come up with a set of numbers that cannot be partitioned in two subsets with an equal sum modulo 9, that hand is unplayable. This can be done in a number of ways; for instance, if all cards but one are 0 modulo 9 (i.e. 0 or 9) (as in the example above), or if all cards but one are divisible by 3 (e.g. {1,3,3,...} or {2,6,6,...} are unplayable).

The game becomes much more interesting in a base B such that B-1 is a prime number, though, because it suffices to allow only non-zero cards to make the above solution insufficient (e.g. in base 8, allow only 1 through 7 and "casting out sevens" does not produce anything as decisive as above). Tigraan^{Click here to contact me} 14:40, 13 April 2018 (UTC)

I thought {0,0,...0,1} was unplayable too when I assumed that all cards had to be played above, but as you don't have to play all your cards, then 0+0=0 is a valid play. Your other solutions also fail as $x+x+x+x+x+x+x+x+x+x+x=xx$ is a valid play. Iffy★Chat -- 14:59, 13 April 2018 (UTC)

Sorry, you even mentioned that solution... I must really learn to read before answering. Yeah, that kills my other answer as well (though it still retains some interest if anyone wants to computer brute-force the problem).

Under those rules, there is a largest unplayable hand. The pigeonhole principle guarantees that out of 111 cards with 10 possible values, 12 of them will have the same value, thus providing a "11*x=xx" solution for any hand with at least 111 cards. That's probably not an optimal bound, but that's a finite bound. Tigraan^{Click here to contact me} 15:04, 13 April 2018 (UTC)

13 cards are necessary for the 11*x=xx solution (11 on the LHS, 2 on the RHS), but at the same time, only 3 0's are needed for the 0+0=0 solution, so the upper bound is actually 12*9+2+1 = 111, which is coincidentally the same as your wrong upper bound. Iffy★Chat -- 15:32, 13 April 2018 (UTC)

Adding any additional card to a playable hand results in a playable hand. Which means that for any unplayable hand, any "sub-hand" (i.e. a hand which is the unplayable hand with any card or cards removed) must be unplayable (if it was playable, the larger hand would also be playable). Which means that if Sebastian is correct above, and {0,4,6,7,8,9}, {0,4,5,6,7,8} are the only 6 card unplayable hands:

For {0,4,6,7,8,9}, 1+6=7, 2+6=8, 3+6=9, 5+4=9, and x+0=x for any x in the original hand except 0 (meaning that you can't add any non-0 card and get an unplayable hand), also 70+6+4=80 (so you can't add another 0 either), so there are no 7 digit unplayable hands for which this is a subhand.

For {0,4,5,6,7,8}, the same as above applies (except that for 5+4=9, the 9 is the new card added).

Therefore, assuming that those are the only 6 digit unplayable hands, they are also the largest unplayable hands (and if not, then it gives a simple way to search from the smallest unplayable hands up to the largest). MChesterMC (talk) 08:47, 16 April 2018 (UTC)

I can prove the assertion of those being the only 6 card hands without duplicated digits - a 6 card hand cannot contain a 1, as it must contain adjacent digits, cannot contain a 2, as it must contain digits separated by 2 ({0,1,4,5,8,9} is the only hand of length 6 that does not - but the hand cannot contain a 1), and cannot contain a 3 (as all hands which do not contain x+3=y also contain a 1 or 2). 4+5=9, so one of that triplet must be missing, and as noted above, (0,5,6,7,8,9) is playable: 58 + 9 = 67. Since we have now removed 4 of the 10 digits, those are all the hands containing a non-duplicated digit.

There may be larger hands containing duplicated digits, but they cannot contain a 0. Duplicated 0 is trivially playable (0+x=0), as is a single 0 in any hand with duplicated x (x+0=x). {1, 1, 1, 4, 4, 4} would seem to be unplayable, for example (though adding any other digit makes it playable - 4 is the least obvious, but 4+4+4+1+1=14). {1,1,1,1,5,5,5} may be a 7 digit unplayable hand. MChesterMC (talk) 09:07, 16 April 2018 (UTC)

In fact, you can definitely get higher than that - 12 2s and any odd number (other than 1) is a 13 digit unplayable hand (e.g. for 3, 11*2<32, and no combination of 2s will give a number ending in 3 on the RHS). Again, adding any other card to that hand results in a playable hand (another 2 gives 2*11=22, another 3 gives 3+2*10=23, for other even numbers, 2+2+2...=X, for other odd numbers, 3+2+2...=X or 1+2=3).

Importantly, we now know that the largest unplayable hand must contain duplicate digits, meaning that we can limit a search for unplayable hands to start from only those containing duplicate digits, and then add further digits (a lot of scribbling on paper gives me 77 three-card unplayable hands containing a duplicate, and not containing a 0). A search strategy starting from each of these hands, adding a card (1-9, since 0 will never work), and repeating (eliminating playable hands at each stage) would find the largest hand eventually. It might be possible to speed it up with the realization that, e.g., where adding the card "2" to the hand {1, 3, 3} does not result in a playable hand, the card "2" will not result in a playable hand for any hand which is generated from {1, 3, 3}. My programming knowledge isn't good enough to put together a program to iterate through this though (and I suspect that there are further simplifications which could be made). MChesterMC (talk) 10:25, 16 April 2018 (UTC)

Further thoughts - where you have 11 copies of a card, you can have at most 1 copy of any other (otherwise 10X+Y=XY is a valid solution). Which means that the upper bound is reduced to 10*9=90 (as we cannot have 0, and 11 of a single card would give a lower upper bound). Since we can only have 5 different cards (as otherwise there is a subset which is a playable hand, per the arguments for the largest hand without duplication, and removing the 0 - note that the only ones which relied on the 0 were the argument against duplication, and the argument for adding another 0), the upper bound is at most 10*5=50. And since the valid digits for that upper bound must include 4 and 8, we cannot have duplicate 4s (4+4=8), so the upper bound can be lowered to 10*4+1=41. Considering the valid hands of 4 unique cards would be necessary to bring that down further (and then 3 unique cards to reduce it below 30 by similar techniques - which I may try later on). MChesterMC (talk) 11:01, 16 April 2018 (UTC)

Can bring the limit a bit further down for the case of 5 unique cards (which may not be the lowest, as there may be a hand with 4 unique cards), by realizing that 8+X8=(X+1)6, which means that having two 8s and a 6 (and any two other consecutive cards) would result in a playable hand - limiting the number of 8s to one, and so bringing the upper bound in this case down to 32. Similar arguments can be applied to the fives (5*3=15, so at most 3 fives) and the nines (9+9=18, so at most one 9), sevens (7+7=14), and finally the sixes (6+6+6=18, so at most 2 sixes) which brings the upper bound with 5 unique cards down to 2+1+1+1+(3 or 1)=8 or 6, which is lower that an already found example, so the worst hand must have fewer than 5 unique cards.

Testing this, with the upper bound hand of {4, 5, 5, 5, 6, 6, 7, 8} - adding a 4 gives 4+4=8, adding a 5 gives 5+5+65=75, adding a 6 gives 6+6+46=58, adding a 7 gives 7+57=64, and adding an 8 gives 8+68=76. There may be other combinations (indeed, that hand might itself be playable), but that's enough to show you can't get to the previously found maximum example.

Now, there are 44 combinations of 4 unique cards which give unplayable hands, which would take significantly longer to work through, so I can't currently show that the lower bound is less than 40, but I suspect that this is the case (just from inspection, it must be less than 35 - as all hands either contain 2 digits X and Y such that X=n*Y for some integer n, or such that n*X=10+Y for some integer n and have adjacent digits.) MChesterMC (talk) 08:43, 17 April 2018 (UTC)

Name of a mathematician on whose shoulders Newton stood

What's the name of the mathematician mentioned here (at 2:44), which sounds something like "Hooda", who found a smart way of finding the center of the tangent circle. I found hoodamath.com, but I don't think Newton played with any of those games. ◄ Sebastian 09:10, 10 April 2018 (UTC)

Sounds like Johannes Hudde. -- ToE 14:19, 10 April 2018 (UTC)

Thank you. That must be him. ◄ Sebastian 10:32, 12 April 2018 (UTC)