Archive for bills

Froebenius coin problem

Posted in pictures, R, Statistics with tags , , , , , , , , , , on November 29, 2019 by xi'an

A challenge from The Riddler last weekend came out as the classical Frobenius coin problem, namely to find the largest amount that cannot be obtained using only n coins of specified coprime denominations (i.e., with gcd equal to one). There is always such a largest value. For the units a=19 and b=538, I ran a basic R code that returned 9665 as the largest impossible value, which happens to be 19×538-538-19, the Sylvester solution to the problem when n=2. A recent paper by Tripathi (2017) manages the case n=3, for “almost all triples”, which decomposes into a myriad of sub-cases. (As an aside, Tripathi (2017) thanks a PhD student, Prof. Thomas W. Cusick, for contributing to the proof, which constitutes a part of his dissertation, but does not explain why he did not join as co-author.) The specific case when a=19, b=101, and c=538 suggested by The Riddler happens to fall in one of the simplest categories since, as ⌊cb⁻¹⌋ and ⌊cb⁻¹⌋ (a) are equal and gcd(a,b)=1 (Lemma 2), the solution is then the same as for the pair (a,b), namely 1799. As this was quite a light puzzle, I went looking for a codegolf challenge that addressed this problem and lo and behold! found one. And proposed the condensed R function

function(a)max((1:(b<-prod(a)))[-apply(combn(outer(a,0:b,"*"),sum(!!a))),2,sum)])

that assumes no duplicate and ordering in the input a. (And learned about combn from Robin.) It is of course very inefficient—to the point of crashing R—to look at the upper bound

\prod_{i=1}^n a_i \ \ \ \ \ \ \ (1)

for the Frobenius number since

\min_{(i,j);\text{gcd}(a_i,a_j)=1} (a_i-1)(a_j-1)\ \ \ \ \ \ \ (2)

is already an upper bound, by Sylvester’s formula. But coding (2) would alas take much more space…

the incomprehensible challenge of poker

Posted in Statistics with tags , , , , , , , , on April 6, 2017 by xi'an

When reading in Nature about two deep learning algorithms winning at a version of poker within a few weeks of difference, I came back to my “usual” wonder about poker, as I cannot understand it as a game. (Although I can see the point, albeit dubious, in playing to win money.) And [definitely] correlatively do not understand the difficulty in building an AI that plays the game. [I know, I know nothing!]

Le Monde puzzle [#934]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on October 25, 2015 by xi'an

lemondapariAnother Le Monde mathematical puzzle with no R code:

Given a collection of 2€ coins and 5€ bills that sum up to 120€, find the number of 5€ bills such that the collection cannot be divided into 5 even parts.

Indeed, as soon as one starts formalising the problem, it falls apart: if there are a 5€ bills and b 2€ coins, we have 5a+2b=120, hence 2b=120-5a=5(24-a), meaning that b must be a multiple of 5, b=5b’ and a must be even, a=2a’, with b’=12-a’.  Hence, 10 possible values for both pairs (a’,b’) and (a,b), since a>0 and b>0. If these 120 Euros can be evenly divided between 5 persons, each gets 24€. Now, 24€ can be decomposed in 5€ bills and 2€ coins in three ways:

24=2×2+4×5=7×2+2×5=12×2+0x5.

Each of the five persons using any of the 3 above decompositions means there exist integers α, β, and γ such that

α(2×2+4×5)+β(12×2)+γ(7×2+2×5)=(2α+12β+7γ)x2+(4α+2γ)x5=bx2+ax5

with α+β+γ=5; therefore a=4α+2γ and b=2α+12β+7γ, which implies 2α+γ=a’ and 2α+12β+87γ=5×12-5a’=2α+5×12-12α-12γ+7γ, or 5a’=10α+5γ. That is, 2α+γ=a’ again… If a’=11, there is no solution with α+γ≤5, and this is the only such case. For any other value of a’, there is a way to divide the 120€ in 5 even parts. As often, I wonder at the point of the puzzle if this is the answer or at its phrasing if I have misunderstood the question.

Just to check the above by R means, I still wrote a short R code

for (a in 1:11){
# find integer solutions to 2x+y=a
  sum=0;z=-1
  while ((z<a)&(z<6)&(sum<2)){
    z=z+1;x=trunc((a-z)/2);y=5-x-z
    sum=(2*a==4*x+2*z)+(5*(11-a)==x+11*y+6*z)}
  print(c(2*a,5*(11-a),x,y,z))
  }

which returned

[1]  2 50  0  4  1
[1]  4 45  1  4  0
[1]  6 40  1  3  1
[1]  8 35  2  3  0
[1] 10 30  2  2  1
[1] 12 25  3  2  0
[1] 14 20  3  1  1
[1] 16 15  4  1  0
[1] 18 10  4  0  1
[1] 20  5  5  0  0
[1] 22  0  5 -1  1

meaning that a’=11 does not produce a viable solution.