Counterfeit coin with payments for weighting

Question

I came across this recreational mathematics problem :

You have $100$ coins , one of which is counterfeit. You need to find the false one. To do so , you can give a jeweller some of your coins and he will tell you whether your false coin is among them or not. If it is among them , you pay him $600$ units of money. If it is not among them , you pay $400$ units of money.
If you use the best possible strategy , what is the maximum payment you will make ?

The Correct Answer given [ without Explanation & without Proof ] is $3600$ units of money.
All my attempts led me to $4200$ units of money and I cannot make it less.
My Attempts include trying with Bisection : $50-50$ , $25-25$ & so on , which gives $4200$ units of money.

Answer 1

[[ Putting this here to generate thought & Alternate Answers on this , it is not yet resolved or finished. I suspect that there is no Exact Answer to get 3600 , though My Method might be tweaked to get a little closer to that target ]]

With fibonacci numbers , I am able to use wishy-washy thinking to get a better Cost : less than 4200 , though it is more than 3600 :

Start with 100 coins , split into 45+55 , & give 45 (the smaller set) to weigh , where we might expect that the larger set has higher Probability of having the fake coin.
In Case we are informed that 45 has no fake coin , hence 55 has the fake coin , then take the 55 , make 2 sets like shown below , splitting into fibonacci numbers :

100 = 45+55 ( this is not fibonacci , all the rest here are fibonacci )
         21+34 ( this & all the rest here are fibonacci )
            13+21
               8+13
                 5+8
                   3+5
                     2+3
                       1+2
                         1+1

Assumption is that the smaller set (left set) is given to weigh , while the larger set (right set) has higher Probability of having the fake coin. Hence Cost to move to next level is 400.
Other wise , Cost is 600 , but we are able to skip a level to go 2 levels down , overall we are saving 200.
The last level may cost 400 or 600. Hence total is $8 \times 400 + 600 = 3800$ or $9 \times 400 = 3600$

In Case , in the first level itself , we are informed that 45 has the fake coin , then we use the following splits :

45 = 22+23 ( this & the next are not fibonacci , all the rest here are fibonacci )
        10+13
           5+8 ( this & all the rest here are fibonacci )
             3+5
               2+3
                 1+2
                   1+1

Number of levels is less , Hence Overall Cost is less.

Starting with 100 coins , we can "expect" that it will Cost 3600 or 3800 or less.

There is no "guarantee" though.

When we want to OPTIMIZE this Method , we might make it such that $400+400+400=600+600$ , that is :
When we are informed that 2 Consecutive weightings have the fake coin , the number of Potential Coins left must be EQUAL to the Case when we are informed that 3 Consecutive weightings are not having the fake coins.
In other words , 3 Consecutive weightings without fake coins will go down 3 levels , while 2 Consecutive weightings with fake coins should also down 3 levels.
Over-all Cost might work out less than 3600 !

All wishy-washy thinking , still have to refine & finish it !

Answer 2

They're all counterfeit! They're made of plastic!

Not really, but a sequence involving the plastic constant as a limiting ratio comes into play.

Given a number of coins, we should seek to divide them in fractions of $p$ and $q$ such that $p+q=1$ and $p^2\approx q^3$. The exponents $2$ and $3$ are set by the cost ratio. The ratio of $q$ to $p$ in the limit of infinitely many coins is the plastic constant $\rho=1.32471..., \rho^3=\rho+1$.

Consider a sequence defined by $a_1=a_2=a_3=1$ and for $n>3, a_n=a_{n-2}+a_{n-3}$:

$1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,...$

The reader may verify that ratio of these terms approaches the plastic constant. Note that depending on the combination of jumps you take, you reach $1$ from $114$ in $16$ to $18$ downward steps.

Our rule is given any number of coins, find the first term equal or greater in the sequence, then go back three steps and give that many coins to the jeweler. For instance, with $100$ coins we find $114$ above, go back three steps to arrive at $49$, and give that many coins to the jeweler.

Suppose that the jeweler says no counterfeit coin each time, allowing you nine steps overall to stay within a $3600$ unit budget. Since you eliminated $49$ coins in the first division, you have to divide $51$ coins next, and you proceed. Blue numbers below represent the group containing the counterfeit coin:

$100=\color{blue}{51}+49$

$51=\color{blue}{30}+21$

$30=\color{blue}{18}+12$

$18=\color{blue}{9}+9$

$9=\color{blue}{5}+4$

$5=\color{blue}{3}+2$

$3=\color{blue}{2}+1$

$2=\color{blue}{1}+1$

This is actually only eight divisions and thus costs $3200$ units. We get a discount because we are working with $100$ coins instead of exactly $114$.

Let's look at the opposite extreme. If the jeweler says counterfeit each time, we have:

$100=51+\color{blue}{49}$

$49=28+\color{blue}{21}$

$21=12+\color{blue}{9}$

$9=5+\color{blue}{4}$

$4=2+\color{blue}{2}$

$2=1+\color{blue}{1}$

At 600 units per counterfeit answer this comes out to our budget of $3600$ units.

I will let the reader work out intermediate possibilities, which are too numerous to fit in the margins of this posting. The basic idea is that you need no more than $18$ sequence steps to get from $114$ coins (or any smaller number) to a $1$, and with each division you effectively pay $200$ units per step.