Counterfeit Coins and Balanced Ternary

[@blacklotus42]

This is a really refreshing and novel solution to these balance puzzles, I definitely agree that the standard logical approach can feel pretty unsatisfying with generalization in mind. Not to mention that this solution is, in my opinion, much more elegant. Thank you for sharing!

[@MathVisualProofs]

Thanks for watching!

[@LittlePaimon]

非常好的视频！

[@KinuTheDragon]

How do you select the numbers to negate? Is there some procedure other than brute force?

[@MathVisualProofs]

This is a good question. It doesn't take too long when playing around with them, but I don't know a systematic way to do it for larger values of n of the top of my head. I will say the choice isn't unique. The linked article about the magic trick negates 1,7,8,11,12 instead for the classic three coin puzzle.

[@Brollyy349]

The sum of the numbers to negate must be equal to the sum of the numbers that won't be negated. More concretly, they should sum to (3^n-3)*(3^n-1)/16. This is always possible by selecting coins with largest numbers until you get close to the target sum, and then adding a smaller number to complete it. n = 2: 3 coins, target sum = 3, choose 3 n = 3: 12 coins, target sum = 39, choose 12, 11, 10, 6 n = 4: 39 coins, target sum = 390, choose 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 16

[@MathVisualProofs]

@@Brollyy349 thanks! Very cool :)

[@MathVisualProofs]

@@Brollyy349 but you also need to negate 13 coins for the last one. I think you did 12

[@Brollyy349]

Went through it by hand and you're right - there's an imbalance in my last example. The target sum is a necessary condition, but not a sufficient one - basically I got 14 1s and 12 (-1)s for 27s place, which just so happened to balance out with 10 1s and 16( -1)s in 9s place. I'm not sure if choosing exactly a third of all the numbers is sufficient or even necessary. I'll try to look into this more deeply when I have the time.

[@benjaminpedersen9548]

Very nice solution! I managed to find an easy algorithm for selecting numbers to negate and posted it under the question comment.

[@MathVisualProofs]

Nice work!

[@MrSilversMathSheets]

I thought this one might get a mention. This is by far the best math video site I have discovered in the past year. I think it is just a matter of time before the site gets the visibility it deserves.

[@MathVisualProofs]

Thanks! I appreciate the comment :)

[@MathVisualProofs]

Oh and I see maybe you meant in the 3b1b video. I didn’t even make the top 100. Oh well, we keep on.

[@AllThingsPhysicsYouTube]

Wow! This is so cool! Of course, I immediately wanted to know how to figure out which numbers to negate, but I see this question in the comments so I'll look there for the answer. Nicely done!

[@MathVisualProofs]

It is not obvious to me how to choose numbers to negate in general. But it wasn't too hard to find 13 that work for the 39 coin case.

[@captaindapper5020]

I think I found a very satisfying answer to this question. It's in the top comment :)

[@MathVisualProofs]

@@captaindapper5020 I missed that one somehow. Thanks for that. It looks nice. I’ll read it more carefully and think about it (soon I hope) but it seems like a good idea!

[@captaindapper5020]

@@MathVisualProofs I just posted it, so no worries :)

[@alikaperdue]

I searched for a solution like this in the past. I used a constant set of ball choices for each weighing and then used a lookup table for the answer. After, I searched for a solution like you have done where the weighing are the bits of the answer. ie: no lookup table. I didn't find it. If you found this solution yourself, I am impressed and congradulations.

[@jonathanlevy9635]

without any generalization to any number of coins this still feels like a black magic. is there an algorithm for any number of coins that is derived from this technique? from what it seems, the number of weighings you need to have is not even linear to the number of coins, am I right? great video btw! the topic and mainly the connection between the seemingly unrelated problem to the solution felt very mathologer to me

[@MathVisualProofs]

Thanks for this comment! So the thing you need is you want essentially half the powers of 3. This works out because you want the all the numbers with n-digits (after padding with 0s if necessary) in balanced ternary. The only one you don't include is (1,1,1,1...,1) because that won't allow you to split them into nice even piles for each weighing. The number of weighings is essentially logarithmic (basically because we have the negative numbers implicitly hiding, we are using all the numbers from -((3^n-1)/2 -1) to (3^n-1)/2 -1 , which is the 3^n-3 numbers (removing zero). Does that make sense?

[@divijdude]

It is quite similar to finding linearly independent vectors where each element in the vector belongs to {-1, 0, 1}

[@minimath5882]

Gotta love balanced ternary on weighing problem

[@MathVisualProofs]

😀👍

[@noambagon1]

I want to write an assembly code that calculates the lists of numbers to put on the scales for each weighing with 39 coins. how would I do that??

[@me0101001000]

I learned how to do this when I was a kid. Anyone remember the show Cyberchase?

[@MathVisualProofs]

never saw it. Should I check it out?

[@me0101001000]

@@MathVisualProofs absolutely! It's a great kid's show that teaches kids about math and science

[@tylerduncan5908]

@MathVisualProofs That's a good representation of it. I thought up the idea in my head, but im not great with manim/coding. I pictured it just by looking at the formula. σ = root( 1/n Σ (x₁ - x*)² )

[@zeke-a-hedron]

Once I heard you were able to label the coins I saw where you were going

[@MathVisualProofs]

:)

[@angeldude101]

Would you still need to strategically negate some numbers if instead of counting up from 1, you instead count symmetrically away from 0? So like {-4, -3, -2, -1, 0, 1, 2, 3, 4} rather than {1, 2, 3, 4, 5, 6, 7, 8, 9}. (Actually no since this wouldn't be able to tell if the coin is lighter or heavier.)

[@MathVisualProofs]

Is definitely a good thought! But right, we need the labels between 1 and 12 and then the opposites to tell us heavier or lighter. I haven't thought if there is a way around it...

[@stevenmcculloch5727]

​@@MathVisualProofscan't you tell which side is heavier by simply looking at the scale when the counterfeit coin is part of the batch? If the side with the coin goes up, then it is lighter. If it goes down it is heavier. Great video :) I have a critique too. It might have been good to use some color on the algebra in the first half since it looks like a wall of text and is hard to see at a glance what is a base vs. exponent vs. operator.

[@MathVisualProofs]

@@stevenmcculloch5727 Yes. Once you've identified the coin, you can look back at the weighings and just see the weight of the counterfeit coin. But I like that you can tell numerically as well. Appreciate the comment and the critique. I always waffle on when and how to use color because of accessibility issues when I do use color. I agree that it would have made some sense where you say :) Thanks!

[@MrSilversMathSheets]

This is a very nice video.

[@MathVisualProofs]

Thank you! I really appreciate that.

[@tanchienhao]

Wow such an elegant take on this problem!

[@MathVisualProofs]

Thanks! Appreciate the comment!

[@temporary9508]

Very Very interesting

[@MathVisualProofs]

Thanks! Appreciate the comment and you checking out the video 👍😀

[@trevise684]

great vid, but id suggest extending the pauses between sentences, as there is no room to breath

[@MathVisualProofs]

Thanks! I often worry about blank space, but you are right that some probably come too quickly. Appreciate it!

[@meanderer9808]

Where is the explanation for why 1,4,7,10 are in the ones position? 3 also has a one in it.

[@MathVisualProofs]

3 has 1 three and 0 ones

[@skyscraperfan]

I still do not see how you can tell if a coin is heavier or lighter by looking at which representatives you strategically negated. You decided that 23 is not negated in the list of representatives, but at that point you did not know the coins at all. So how can the fact that 23 is not negated mean that coin 23 is heavier?

[@alikaperdue]

Base 1 is the unary number system. It also takes each 1 and multiplies it by 1 to the power of its position and then all of these ones are added up. I'm suggesting that the numbers in a base system do not need to 2 or greater. Also, there is the e and golden ration numbers. The golden ration is less than 2. Although I wonder if anyone ever used them for any real math.

[@MathVisualProofs]

Unary is a bit different because in a base b positional system the digits are 0 to b-1. So this doesn’t work for b=1. But the unary system does work.

[@skpcboy]

genius

[@MathVisualProofs]

👍😀 thanks!

[@vitowidjojo7038]

Now, use the coins to buy a new scale or weighing.

[@MathVisualProofs]

Smart! :)

[@tylerduncan5908]

Asking you to do a visual representation of the standard deviation

[@tylerduncan5908]

>Take average >square the distance from the average to individual data points >add the squares >divide by number of points >re-squareify >side length is σ

[@onradioactivewaves]

​@@tylerduncan5908if only it were that simple. Case in point, there's a different formula to use for standard deviation for small vs large sample size.

[@gblargg]

I don't understand the trend to more and more distracting animation in math videos, e.g. text drawing the individual strokes for every letter.

[@hansdumbf7608]

You're talking to fast! Give people a few seconds to catch up. Just lower your speed about 20 - 25% and make a short pause between ideas, just a few seconds so people can grasp what they just heard.

[@netfri25]

imo his speed is fine, and don't forget that it is a video, you can slow it down or pause it as much as you'd like

[@theexplorer9012]

New to KZbin? There is something called playback speed mf. Oh i forgot , there is dumb in your name itself