Math Quiz Thread

[steve_bnk]

A sine wave is painted oN an NFL football field length wise, 100 yards by 53.3 yards.

A player runs the sine curve, how far does he run?

 

[lpetrich]

The length of a curve is

\(s = \int \sqrt{ \left( \frac{dx}{dt} \right)^2 + \left( \frac{dy}{dt} \right)^2 } dt \)

for {x,y} as functions of parameter t. A sine curve is y = a*sin(k*x), and using t = x, I find

\(s = \int \sqrt{ 1 + (ka)^2 \cos^2 kx } dx \)

This requires an elliptic integral of the second kind, though one could do it by numerical integration.

 

[steve_bnk]

The length of a curve is

\(s = \int \sqrt{ \left( \frac{dx}{dt} \right)^2 + \left( \frac{dy}{dt} \right)^2 } dt \)

for {x,y} as functions of parameter t. A sine curve is y = a*sin(k*x), and using t = x, I find

\(s = \int \sqrt{ 1 + (ka)^2 \cos^2 kx } dx \)

This requires an elliptic integral of the second kind, though one could do it by numerical integration.

The numerical answer is? There is a step or two before you can integrate....

 

[lpetrich]

That depends on the wavelength, the amplitude, and the starting phase. If it is one cycle for the length of the field, and an amplitude that makes the wave stretch over the end of the field, then k = (2π)/(100 yds) and a = (1/2) * (53.3 yds). The starting phase is irrelevant in this case.

Doing the integral gives 151.369 yds.

\( s = \frac{1}{k} \sqrt{1 + (ka)^2} E(kx, m) ,\ m = \frac{(ka)^2}{1 + (ka)^2} \)

 

[steve_bnk]

That depends on the wavelength, the amplitude, and the starting phase. If it is one cycle for the length of the field, and an amplitude that makes the wave stretch over the end of the field, then k = (2π)/(100 yds) and a = (1/2) * (53.3 yds). The starting phase is irrelevant in this case.

Doing the integral gives 151.369 yds.

\( s = \frac{1}{k} \sqrt{1 + (ka)^2} E(kx, m) ,\ m = \frac{(ka)^2}{1 + (ka)^2} \)

I came up with149.4.

I don't see where( 2πx)/(100) has a period of 100.

y(x) = 2*pi*x/100

 

[beero1000]

1. How many ways are there to make change of $1, using pennies, nickels, dimes, and quarters?
2. What is the optimal set of four coin denominations? (i.e. we are allowed 4 different denominations and want to minimize the average number of coins necessary to make change for any value from 1c to 99c, each equally likely)
3. If you repeatedly play a game where you can randomly win either $3 or $7, what is the largest dollar amount that it is not possible for you to cumulatively win? What about other $a and $b?

 

[steve_bnk]

#1
Reminds me of high school algebra word coin problems.
.01*P + .05*N + .10*D + .25*Q = 100

Q <= 4
D<= 10
N <= 20
P <= 100
From there it is permutation/combinations.

For all of one coin = 100, 4.

For any 1-3 quarters combinations of 5-10-20-25-75 pennies, nickles, and dimes that equal 0.25,0.50,0.75.

And so on...

I don't see a simple expression that eliminates redundant states, but I have rarely used combinatorics and permutations.

It could be brute forced by running all permutations and selecting results that equal 100.

#2
4 pennies
1 nickel
2 dimes
3 quarters

0 – 9, N 4P.
10, D
15, D N
20, D D
25, Q
30, Q N
35, Q D
40, Q D N
45, Q D D
50, Q Q
55, Q Q N
60, Q Q D
65, Q Q D N
70, Q Q D
75, Q Q Q
80 Q Q Q N
85 Q Q Q D
90 Q Q Q D N


#3

There is no loosing or betting, are there more details?

Taking random in its statistical meaning of uncorrelated events like a coin toss, for a 50/50 result over N events N being an even number you will have (N /2 * $3) +(N/2 * $7) accumulated.

 

[lpetrich]

#1:

How many ways are there to make change of $1, using pennies, nickels, dimes, and quarters?

I wrote a Mathematica function that does that calculation, and I got 242.

If you wish to do the comparable problem with British coinage, I've found these numbers:  List of British banknotes and coins,  Coins of the pound sterling


Decimal (Bank of England):
Coins: 1p, 2p, 5p, 10p, 20p, 50p, £1, £2
Bills: £5, £10, £20, £50
p = penny (British plural: pence), £ = pounds sterling
1 pound = 100 pence

I calculate 3953 splits of £1.


Before  Decimal Day, 15 February 1971, the UK had used a much more complicated mix. Here are those that survived to that day or not long before:
Farthing: (1/4)d (discontinued 1960), Halfpenny: (1/2)d, One penny: 1d, Threepence: 3d, Sixpence: 6d, Shilling: 1s = 12d, Florin: 2s = 24d, Half-crown: 2s 6d = 30d (disc. 1969), Crown: 5s = 60d (disc. 1965)
Note: £1 = 20s = 240d

With only 1d, 3d, 6d, 1s, and 2s, I calculate 38841 splits of £1.

 

[steve_bnk]

#1:

How many ways are there to make change of $1, using pennies, nickels, dimes, and quarters?

I wrote a Mathematica function that does that calculation, and I got 242.

If you wish to do the comparable problem with British coinage, I've found these numbers:  List of British banknotes and coins,  Coins of the pound sterling


Decimal (Bank of England):
Coins: 1p, 2p, 5p, 10p, 20p, 50p, £1, £2
Bills: £5, £10, £20, £50
p = penny (British plural: pence), £ = pounds sterling
1 pound = 100 pence

I calculate 3953 splits of £1.


Before  Decimal Day, 15 February 1971, the UK had used a much more complicated mix. Here are those that survived to that day or not long before:
Farthing: (1/4)d (discontinued 1960), Halfpenny: (1/2)d, One penny: 1d, Threepence: 3d, Sixpence: 6d, Shilling: 1s = 12d, Florin: 2s = 24d, Half-crown: 2s 6d = 30d (disc. 1969), Crown: 5s = 60d (disc. 1965)
Note: £1 = 20s = 240d

With only 1d, 3d, 6d, 1s, and 2s, I calculate 38841 splits of £1.

Can you post your code?

 

[lpetrich]

In the previous one, if one wants to do (1 dollar) - (1 cent) and (1 pound) - (1 penny), one gets:
US: 213
Brit decimal: 3794
Brit predecimal (1d,3d,6d,1s,2s): 37070

What is the optimal set of four coin denominations? (i.e. we are allowed 4 different denominations and want to minimize the average number of coins necessary to make change for any value from 1c to 99c, each equally likely)

For US money, that's 470/99 ~ 4.75

For an optimal sizing of coins, we need only find all but the smallest one, because the smallest one would necessarily be 1c.

For a total amount N and sizings {c,1}, the average number of coins is {N/(2c),c/2} averaged over c. Repeating for {c₁,c₂,...,c_n,1}, I find {N/(2c₁), c₁/(4c₂), ..., c_n-2/(2^n-1c_n-1), c_n-1/2^n-1} or more generally, {c_k-1/(2^k*c_k)} with c₀ = N and c_n = 1/2.

Minimizing, this gives us c_k-1/c_k² - 1/(2*c_k+1) or
c_k² = 2*c_k-1*c_k+1

Taking the logarithm gives a linear recurrence. Solving it gives us

c_k = 2^-k(k+1)/2 * w0 * w1^k

and plugging in the boundary conditions, the values for k = 0 and k = n, gives us
c_k = 2^{-k(k+1)/2 + ((n+1)/2-1/n)*k} * N^(n-k)/n

I obtain splitting {75, 28, 5, 1}, which gives an average of 4.95 coins. The assumption of average behavior is somewhat violated here.

 

[lpetrich]

I created a hill-climbing minimizer, one that looks at all the neighbors of a point then selects the best one.

For {25, 10, 5, 1} and 1-step neighbors, I found {29, 11, 3, 1} with 4.16 coins
For {25, 10, 5, 1} and 2-step neighbors, I found {29, 11, 3, 1} with 4.16 coins
For {75, 28, 5, 1} and 1-step neighbors, I found {74, 28, 5, 1} with 4.93 coins
For {75, 28, 5, 1} and 2-step neighbors, I found {60, 17, 4, 1} with 4.38 coins

Turning {29, 11, 3, 1} into nice-looking numbers, I get {30, 10, 3, 1} with 4.24 coins

 

[steve_bnk]

In the previous one, if one wants to do (1 dollar) - (1 cent) and (1 pound) - (1 penny), one gets:
US: 213
Brit decimal: 3794
Brit predecimal (1d,3d,6d,1s,2s): 37070

What is the optimal set of four coin denominations? (i.e. we are allowed 4 different denominations and want to minimize the average number of coins necessary to make change for any value from 1c to 99c, each equally likely)

For US money, that's 470/99 ~ 4.75

For an optimal sizing of coins, we need only find all but the smallest one, because the smallest one would necessarily be 1c.

For a total amount N and sizings {c,1}, the average number of coins is {N/(2c),c/2} averaged over c. Repeating for {c₁,c₂,...,c_n,1}, I find {N/(2c₁), c₁/(4c₂), ..., c_n-2/(2^n-1c_n-1), c_n-1/2^n-1} or more generally, {c_k-1/(2^k*c_k)} with c₀ = N and c_n = 1/2.

Minimizing, this gives us c_k-1/c_k² - 1/(2*c_k+1) or
c_k² = 2*c_k-1*c_k+1

Taking the logarithm gives a linear recurrence. Solving it gives us

c_k = 2^-k(k+1)/2 * w0 * w1^k

and plugging in the boundary conditions, the values for k = 0 and k = n, gives us
c_k = 2^{-k(k+1)/2 + ((n+1)/2-1/n)*k} * N^(n-k)/n

I obtain splitting {75, 28, 5, 1}, which gives an average of 4.95 coins. The assumption of average behavior is somewhat violated here.

What he asked was 'What is the optimal set of four coin denominations? ' to make change. I take the average comment to be extraneous.

 

[beero1000]

I created a hill-climbing minimizer, one that looks at all the neighbors of a point then selects the best one.

For {25, 10, 5, 1} and 1-step neighbors, I found {29, 11, 3, 1} with 4.16 coins
For {25, 10, 5, 1} and 2-step neighbors, I found {29, 11, 3, 1} with 4.16 coins
For {75, 28, 5, 1} and 1-step neighbors, I found {74, 28, 5, 1} with 4.93 coins
For {75, 28, 5, 1} and 2-step neighbors, I found {60, 17, 4, 1} with 4.38 coins

Turning {29, 11, 3, 1} into nice-looking numbers, I get {30, 10, 3, 1} with 4.24 coins

You can do better. IIRC, opt is around 3.9.

As a somewhat easier followup, what denomination should we add to {25,10,5,1} to give the best average?

#1:

How many ways are there to make change of $1, using pennies, nickels, dimes, and quarters?

I wrote a Mathematica function that does that calculation, and I got 242.

If you wish to do the comparable problem with British coinage, I've found these numbers:  List of British banknotes and coins,  Coins of the pound sterling


Decimal (Bank of England):
Coins: 1p, 2p, 5p, 10p, 20p, 50p, £1, £2
Bills: £5, £10, £20, £50
p = penny (British plural: pence), £ = pounds sterling
1 pound = 100 pence

I calculate 3953 splits of £1.


Before  Decimal Day, 15 February 1971, the UK had used a much more complicated mix. Here are those that survived to that day or not long before:
Farthing: (1/4)d (discontinued 1960), Halfpenny: (1/2)d, One penny: 1d, Threepence: 3d, Sixpence: 6d, Shilling: 1s = 12d, Florin: 2s = 24d, Half-crown: 2s 6d = 30d (disc. 1969), Crown: 5s = 60d (disc. 1965)
Note: £1 = 20s = 240d

With only 1d, 3d, 6d, 1s, and 2s, I calculate 38841 splits of £1.

242 is right.

An interesting fact is that the number of ways of making change of n cents using pennies, nickels, dimes, and quarters is

\(\frac{1}{24}\left((L+1)(50L^2+(85+30M)L+6M^2+24M+24\right) - \frac{1}{16}\left(2L +(1+(-1)^L)(1+(-1)^{M+1})+(1+(-1)^{L+1})\right)\) where \(L = \lfloor \frac{n}{25}\rfloor\) and \(M = \lfloor \frac{n}{5} \rfloor - 5\lfloor{\frac{n}{25}\rfloor\)

 

[lpetrich]

If you repeatedly play a game where you can randomly win either $3 or $7, what is the largest dollar amount that it is not possible for you to cumulatively win? What about other $a and $b?

Since 3 is smaller than 7, let us first consider 3.

The winning values can be divided into 3 types: 3n, 3n+1, and 3n+2. The first one is a multiple of 3, so it's always possible. The second and third ones are not possible unless they are greater than appropriate multiples of 7. The second one's possible values are 3n+7, while the third one's possible values are 3n+14. The first one's largest impossible value is 4, while the second one's is 11.

Thus, 11 is the largest number that cannot be the combination of winnings.

For a and b more generally, where a and b are both positive integers, there will be a maximum impossible value only if gcd(a,b) = 1. Otherwise, there will be an infinity of winning values not divisible by gcd(a,b), and thus impossible.

Let a be the smaller one and b the larger one. Then all the n*a values are possible, while for k = 1 to (a-1), the n*a+k values need not be. Find k for b, then for 2b, then for multiples of b up to (a-1)*b. They will be distinct values, from relative primeness, and thus will cover all the possible n*a+k sets. The largest of these values that starts a possible set of n*a+k is (a-1)*b, and thus the largest impossible value is (a-1)*b - a.

That value equals (a-1)*(b-1) - 1, which is symmetric in a and b.

 

[beero1000]

If you repeatedly play a game where you can randomly win either $3 or $7, what is the largest dollar amount that it is not possible for you to cumulatively win? What about other $a and $b?

Since 3 is smaller than 7, let us first consider 3.

The winning values can be divided into 3 types: 3n, 3n+1, and 3n+2. The first one is a multiple of 3, so it's always possible. The second and third ones are not possible unless they are greater than appropriate multiples of 7. The second one's possible values are 3n+7, while the third one's possible values are 3n+14. The first one's largest impossible value is 4, while the second one's is 11.

Thus, 11 is the largest number that cannot be the combination of winnings.

For a and b more generally, where a and b are both positive integers, there will be a maximum impossible value only if gcd(a,b) = 1. Otherwise, there will be an infinity of winning values not divisible by gcd(a,b), and thus impossible.

Let a be the smaller one and b the larger one. Then all the n*a values are possible, while for k = 1 to (a-1), the n*a+k values need not be. Find k for b, then for 2b, then for multiples of b up to (a-1)*b. They will be distinct values, from relative primeness, and thus will cover all the possible n*a+k sets. The largest of these values that starts a possible set of n*a+k is (a-1)*b, and thus the largest impossible value is (a-1)*b - a.

That value equals (a-1)*(b-1) - 1, which is symmetric in a and b.

Yup. Schur's theorem implies that for a collection of numbers there are a finite number of unobtainable values if and only if their gcd is 1, but actually finding the value for arbitrary collections is hard. In fact, the only known nontrivial closed form solution is for two numbers, and is the one you just derived. Three or more is still an open problem... It's known as the  Frobenius Problem and brings us fun things like the McNugget numbers.

 

[lpetrich]

What he asked was 'What is the optimal set of four coin denominations? ' to make change. I take the average comment to be extraneous.

The optimal set is the set that needs the smallest average number of coins to make change, and that was what I was trying to calculate.

 

[steve_bnk]

What he asked was 'What is the optimal set of four coin denominations? ' to make change. I take the average comment to be extraneous.

The optimal set is the set that needs the smallest average number of coins to make change, and that was what I was trying to calculate.

OK. Admittedly your theoretical math is well above mine and your math foundation is solid. I am not questioning that.

I looked at doing it algorithmically and then just made a table and worked it out.

It seemed obvious the solution would include 1, 2, or 3 quarters. Pennies would have to be minimized and required at least 4. At least one nickel was needed to count to 9. That left the mix of quarters and dimes.

 

[Bomb#20]

You can do better. IIRC, opt is around 3.9.

I make it 3.929. There are two equally good solutions.

Show

{25,18,5,1}
{29,18,5,1}

As a somewhat easier followup, what denomination should we add to {25,10,5,1} to give the best average?

32 cents.

 

[lpetrich]

You can do better. IIRC, opt is around 3.9.

I'd likely have to write a C++ version to go through all the possible values, since Mma has a lot of object-management overhead.

The best ones I've found are
{29, 8, 3, 1}, {29, 11, 3, 1} {32, 10, 3, 1} -- all have 4.16 coins

The third one I found by taking 1001 - k/n[/sub] for k from 1 to n.

As a somewhat easier followup, what denomination should we add to {25,10,5,1} to give the best average?

Max # coins needed:
Quarter: 3
Dime: 2
Nickel: 1
Penny: 4

So we consider a coin between the penny and the nickel.
2-cent coin: 0.1, 1.0, 1.1, 2.0 -- 1.5 coins
3-cent coin: 0.1, 0.2, 1.0, 1.1 -- 1.5 coins
4-cent coin: 0.1, 0.2, 0.3, 1.0 -- 1.75 coins
So it's a tossup between a 2-cent coin and a 3-cent one.

This reduces the total number of coins needed for splitting up 1 to 99 cents from 4.75 to 3.94

I've found some improved solutions:
{45, 18, 7, 3, 1}, {44, 20, 8, 3, 1} -- all have 3.49 coins

For 6 kinds of coins,
{44, 19, 8, 5, 2, 1} -- 3.18 coins

For 7 kinds of coins,
{56, 26, 15, 7, 3, 2, 1} -- 2.96 coins

For powers of 2,
{50, 25, 12, 6, 3, 1} -- 3.52 coins (rounded down)
{50, 25, 13, 7, 4, 2, 1} -- 3.15 coins (rounded up)

 

[beero1000]

I make it 3.929. There are two equally good solutions.

Show

{25,18,5,1}
{29,18,5,1}

As a somewhat easier followup, what denomination should we add to {25,10,5,1} to give the best average?

32 cents.

Nice! You can use these results to advocate for switching the dime to an 18c coin, but adding a 32c coin to circulation is probably more reasonable (even then, not very realistic ).

I suspect that the actual distribution of change amounts is not really uniform from 0 to 99, but more likely some kind of Benford-type distribution. I haven't done the calculations for that model, but no doubt someone has looked at it. I wonder how the denominations would change...