Archive for bills
Alain Turing cash!
Posted in pictures, Travel with tags ACE computer, Alan Turing, Bank of England, bills, Bletchley Park, British history, code breaking, England, Enigma code machine, The British Bomb, Turing machine, WW II on April 8, 2021 by xi'an
Froebenius coin problem
Posted in pictures, R, Statistics with tags bills, codegolf, combn(), Ferdinand Frobenius, james Joseph Sylvester, Journal of Number Theory, mathematical puzzle, Norway, PhD thesis, Sylvester's formula, The Riddler 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
for the Frobenius number since
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 /Pages/SIMAccueil.aspx, artificial intelligence, bills, deep learning, Denmark, game theory, Nature, poker, statistics and sports on April 6, 2017 by xi'anWhen 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 arithmetics, bills, Le Monde, mathematical puzzle, R on October 25, 2015 by xi'an
Another 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
[sourcecode language=”r” gutter=”false”]
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))
}
[/sourcecode]
which returned
[sourcecode language=”r” gutter=”false”]
[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
[/sourcecode]
meaning that a’=11 does not produce a viable solution.
