1

You have $10$ bags with marbles. Each bag has $2000$ marbles. Standard marbles weight $10$g. However, one bag has marbles that all weight $9$g and one bag has marbles that all weight $11$g.
If you can only use a scale once (one that displays the numerical weight), how can you determine which bag has the $9$g marbles and which bag has $11$g marbles?

I've been mulling this one over for a bit and discovered plenty of wrong ways to do this, but not the right way yet. Anyone have any ideas on how to tackle this problem?

VlS
  • 129

2 Answers2

3

Mark the bags $1$ to $10$. Pick $2^1$ balls from the first bag, $2^2$ balls from the second bag and in general pick $2^k$ balls from the bag marked $k$. If all bags had balls of equal weight, the sum would be $20460$g. If bag $i$ has $9$g balls and bag $j$ has $11$g balls, the sum of weight of all balls would be $$20460-2^i + 2^j = x$$ Any integer of the form $2^j-2^i$ can be expressed only in a unique way, which would identify the bags for us.

EDIT:

To be a bit more clear, if $x>20460$, we would then end up with $2^j-2^i = x-20460$, i.e., $2^i(2^{j-i}-1)$. Note that $2^{j-i}-1$ is odd. Hence, $i$ is the highest power of $2$ in $x-20460$. Now this also fixes $j$. Similarly, for $x<20460$, $i$ and $j$ interchange roles.

FURTHER EDIT:

We could also take a very higher power, i.e., $f(k) = k^m$, though $m=2$ will not work since we have $\color{red}{8^2-7^2=4^2-1^2}$.

Adhvaitha
  • 20,259
0

Line up the bags, and take a set number of marbles from each bag and weight those, using the difference from the weight of that many standard marbles to uniquely identify the two outlier bags.

To do this you need to find a set of ten numbers such that $x-y=\Delta w$ has only one solution for any $\Delta w$.

Can you find ten such numbers?

Graham Kemp
  • 129,094
  • -1: I do not understand how there is one up-vote to this answer, when the answer states the obvious thing. The question is to how to make this choice of $10$ numbers. – Adhvaitha Apr 30 '15 at 00:18
  • @user17762 yes, it's too general, but I like the approach. $n^2$ will do. – Alexey Burdin Apr 30 '15 at 00:20
  • @AlexeyBurdin $n^2$ won't do unfortunately, You will have $j^2-i^2 = l$ and there could be more than one $i$ and $j$ satisfying this. For instance, if we had sufficient number of bags, and say $j^2-i^2 = 15$ then we have multiple solutions $(j,i) = (8,7)$ and $(4,1)$. – Adhvaitha Apr 30 '15 at 00:26
  • @user17762: Anyway $(n+10)^2$ will do, just tested yet. :) – Alexey Burdin Apr 30 '15 at 01:08
  • @AlexeyBurdin Yes, that is true indeed, but the problem is if we have more than $10$ bags, $(n+10)^2$ won't work. We would need something like $(n+m)^2$. If we want a function, which is independent of the number of bags then any polynomial won't work. – Adhvaitha Apr 30 '15 at 01:10
  • @user17762: I may have to look for $f(m)$ (where $m$ if the number of bags), which is the overall minimum of the maximum element of the sequence. I would state $f(m)<<2^m$ that is all I wanted to say with $n^2$. – Alexey Burdin Apr 30 '15 at 01:15
  • @AlexeyBurdin True. $2^n$ is not optimal in that sense. – Adhvaitha Apr 30 '15 at 01:16