Coin Weighing with a Single Device

You can not do it in 2 weightings. Let's prove it step by step. Initially you have 8 possible combinations: 1st ball is heavier, 1st ball is lighter, 2nd ball is heavier, .., 4th ball is lighter. So you must be able to set correspondence between outcomes or 2 weightings and 8 combinations. Ea...

2

Q: $N_{max}$ balls in 3 weightings

This is a small generalization of well known 12 balls puzzle: You are given two-sided scale and some number of balls. All balls have the same weight but one. It is of a different weight, although you don't know whether it's lighter or heavier. You are allowed to do only 3 weighings to determi...

scale

going by those old questions... maybe the solution will be something like... there is a certain way to do weighings with some pattern of 6 at a time

mdc32

except these are two sided scales which makes it harder

i think

d'alar'cop

I would've thought it'd be easier :p

well we know that the solution for 12... with a balancing scale.. is 8 weighings

mdc32

5:01 AM

how is that accomplished

d'alar'cop

i.e. when we're trying to determine the weights of all the coin

mdc32

never mind i found it

d'alar'cop

not just finding one which is odd

mdc32

ah... so we do have to incorporate all 12 coins in one process

d'alar'cop

possibly

why do you think that?

mdc32

5:05 AM

sort of unrelated, but i think we need to because the author wouldn't have posted it as 12 if we only needed to do a solution for 4 coins 3 separate times

unless he wanted it to be like the 12 balls problem

d'alar'cop

could just be a red herring..

like 6 in 4

twice might be acceptible

mdc32

yeah which would really suck

d'alar'cop

I don't think we can tell

mdc32

has he told you the minimum amount of moves?

d'alar'cop

you reckon we can do 12 in 7 or something?

mdc32

5:07 AM

no probably not

cutting out 5 moves seems like a stretch

d'alar'cop

then 4 in 6... and thus 12 in 8 should be fine?

I mean... 6 in 4

mdc32

hopefully

one thing i have figured out is how I managed to get rid of one move in the 4 in 3 solution

d'alar'cop

oeis.org/A160511

n =12 -> 8

well I mapped it out a little bit

01 = 1 ambiguous
10 = 1 ambiguous
0 1 = 1 ambiguous (but c_2 = c_3)
1 0 = 1 ambiguous (but c_2 = c_3)
000 = 0 unique
001 = 1 unique
110 = 2 unique
111 = 3 unique

mdc32

yeah

the last move we know that c_2 and c_3 are the same, so we have a group of c2 and c3, then a group of c4

it turns into a binary sort of grouping

if we could extend it, maybe we could have a group of c1, then c2 and c3, then c4, c5, c6, and c7

d'alar'cop

yep, but doing it for 6 isolate first might be less soul killing

mdc32

5:12 AM

yeah definitely

just curious what time zone are you in?

d'alar'cop

+10 GMT

4pm here

mdc32

oh its 11pm where I am

d'alar'cop

USA?

mdc32

yeah

you in australia?

d'alar'cop

yep :)

what do you think about weighing some arrangement of 3 coins... for the 4 weighings and deducing something from that?

this just reminds me heavily of that "schedule" method from the balance scales method

000 = 0 unique
001 = 1 unique
110 = 2 unique
111 = 3 unique

that is the interesting part about your solution

mdc32

5:16 AM

yeah

if we could get this along with 3 other coins found in just 3 moves, then our last move could give us 6 in 4

mdc32

5:40 AM

alright, i have to go to bed

11:40 here... i can work on this more tomorrow

d'alar'cop

ok mate

@mdc32 till next time!

mdc32

3:49 PM

Whoa. That last answer... I think I understand what you're saying, but it went a bit over my head

d'alar'cop

4:02 PM

hi mdc :)

@mdc32 are you around?

I'd be happy to walk through it

but it will probably be useless with actually solving it :p

d'alar'cop

4:25 PM

type @d'alar'cop when you want me to see it, see you later mate :)

mdc32

5:21 PM

@d'alar'cop

I'm on now, i have like an hour or so

d'alar'cop

hi mdc

mdc32

hi

d'alar'cop

ok

what's on your mind..

mdc32

so i'm still confused about your answer

i don't really know most of the symbols you're using... I'm only in 9th grade

d'alar'cop

oh ok, well you're doing fantastically then

you solved the problem :)

so which symbols?

mdc32

5:23 PM

well, not really symbols

i understand hamming weight and base 13, but i don't see what this helps with for the problem

like i don't understand the connection

d'alar'cop

right

well you get encoding the weights as 0 or 1

mdc32

yeah

d'alar'cop

so 12 coins means..

a binary number that's 12 symbols long

they are all unique and they each describe one of the arrangement that we are trying to crack

mdc32

i got that

d'alar'cop

ok

so now the largest subset you can get from them is all of them..

and the greatest weight it can have is 12

so to express the possible weights for that subset..

you need from 0-12. i.e. base-13

mdc32

5:26 PM

ah

d'alar'cop

so, now we have 4 (for the case of 6)

mdc32

so it helps give each possible hamming weight a unique symbol, so we need base 13

d'alar'cop

yes

now we can weigh 3 times.. and all we get is a weight... nothing else

so with 4 weighings... we have 4 hamming distances for those subsets we picked

let's say we weight them all... and they are all 20 grams..

mdc32

yes

d'alar'cop

6666

useless... but that's how it works.. same idea for 12

mdc32

5:28 PM

ok

d'alar'cop

so.. what I'm saying is that that encoding needs to give us something that we can use to deduce what all the weights are

and we do that by mapping these results to the possible binary numbers

mdc32

so its more of a good way to test possible answers

d'alar'cop

it's just a formal description to the problem.. and possibly would help with coding it up

it's a problem specification really

mdc32

i could probably whip up some program, but i don't even know what i would test

d'alar'cop

yes, I wouldn't worry about a program..

in fact, the useful thing about that whole thing... is really that we are looking for a sequence of weighings that would give unique reesults..

test it with your own 3 for 4 example

in the last one... the last hamming weight can be 0 1 2 or 3

and that's the disambiguator that makes the whole thing clear and map to a specific combination

mdc32

5:31 PM

yes

because there are distinct outcomes if the weight is 0 1 2 or

3*

d'alar'cop

yep, although the previous ones may not be unique (they are not)

e.g. 11X ...

could still be anything

mdc32

so to get 6 in 4, we either need two places where the hamming weight produces 4 outcomes, or 1 case where it produces 6

d'alar'cop

in the first weighing... we weighed the subset.. coin 1 and 2

it probably will never need to be 6

like we only get up to 3 in yours

mdc32

yeah

d'alar'cop

yet we have 4 coins.. it's clear that every coin needs to go on at least once

we probably end up throwing the last 3 or 4 on in the case of 6

mdc32

5:34 PM

yes

d'alar'cop

it'll be the disambiguator

mdc32

but we can't have two unknown coins in the last weighing

d'alar'cop

maybe we should do all the easy cases first... like where we weigh 2 and they're all equal

exactly :)

mdc32

which means the first 3 weighings contain 5 or 6 of the coins

d'alar'cop

5 of them

and the last will use the 6th..

(*probably)

mdc32

5:36 PM

that's actually pretty useful

d'alar'cop

now it would be easier to code actually... we've (you've really) found quite a lot of optimisations

mdc32

code as in program,?

d'alar'cop

yes

but I think we can get it now..

mdc32

that should be easy, but i can't think of a way to test it efficiently

d'alar'cop

well you'd need to try all the possible weights of 6 coins

mdc32

5:38 PM

oh thats only 64

d'alar'cop

from 0 to 2^6

mdc32

that's not too bad

d'alar'cop

yeah

but you need to test all the possible subsets...

mdc32

subsets of what?

d'alar'cop

which is powerset of 6... 2^6 (only 64 again)

because when you put some coins on the scale.. we are taking a subset

mdc32

5:39 PM

yeah... that would be quite a bit harder

d'alar'cop

so in the first weighing... we can try 2^6 weighing... then we need to do 3 more... so it's actually (2^6)^4

not so easy actually

mdc32

thats a lo

lot*

d'alar'cop

* we can try 2^6 possible subsets to weigh...

yes

mdc32

ill see if I can figure something out... i have to leave soon for about a half hour

d'alar'cop

ok

well we can eliminate certain possible subsets of the coins to weigh

all 6... 0... 1...

that's only 8 in total :p

mdc32

5:42 PM

are reversed subsets necessary>

like 000111 and 111000

d'alar'cop

yes

mdc32

crap

so now we're still at how many subsets

d'alar'cop

because that's coin 1, 2 and 3 all weigh 10 and 4,5,6 weigh 20.... and the other is 1,2,3 weigh 20... and 4,5,6 weigh 10

2^6 - 8

mdc32

so 56

wait what are the 8 we removed?

d'alar'cop

well we won't weigh just 1 coin

mdc32

5:44 PM

oh

d'alar'cop

that's 6 ways to do that... we won't weigh 1 or all 6...

*0 or all 6... =2

Actually yeah, sorry, 000111 and 111000 are not the subsets.. they are the possible combinations of weights

mdc32

so 56^4 now

well actually not 56^4... its 56P4

d'alar'cop

almost 10 million :p

mdc32

yeah

i don't have a good enough computer for that

d'alar'cop

hmmm... yeah 10,000,000 is not that bad..

however... we need to do that for every single one of the 64 possible combinations of the coin weights...

640,000,000 :O forget it

mdc32

5:47 PM

yup

well its more like 620,000,000 because all 0s or all 1s don't matter

d'alar'cop

so the strategy would be: for every single combination of weights... go through all the possible subsets for each of the 4 weighings and when the pattern gives a unique way to identify the coin weighs... we keep it... then do the next combination of weights and keep the weighing patterns which we identified earlier...

no wait... scratch all that

the outer-most loop is the possible subsets...

then we can abandon if we find a set of subsets which handle all the possible coin-weight combinations

mdc32

outer loop is possible subsets of what? coin weights or coins to weigh?

like 2^6 or 2^6-8

d'alar'cop

coins to weigh

yes, but it'll be 4 loops on the outside... each one has (2^6)-8

for each of the possible subsets of the coins to try in on the scale

the outer-most one of the 4 will represent the first use of the scale... and so forth

then inside the 4.... we need to try all the 64 possible weight-patterns of the coins