Academic challenge for advanced-users

[BrooksTech]

Heres an academic challenge. Unfortunately there's no prize other than Kudos and receiving credit for answering the challenge correctly:

1. CREATE A SPREADSHEET THAT WILL ANSWER THE FOLLOWING:

Youre trying to buy an item at a Vending Machine that costs 95 cents. The machine requires EXACT CHANGE ONLY. You do NOT have exact change and the change you have adds up to $1.15 (too much.)

Q. WHAT ARE THE NUMBER AND DENOMINATIONS OF COINS THAT YOU HAVE THAT RENDER $1.15 BUT YOU WILL NOT BE ABLE TO GET 95-CENTS FROM?<?xml:namespace prefix = o ns = "urn:schemas-microsoft-comfficeffice" /><o></o>

(This challenge was originally introduced by CarTalk on 12/24) Good Luck!

 

[BrooksTech]

CONTINUED CHALLENGE and PRACTICAL USES

Of course setting Kudos, etc. aside, what practical-purpose could such a spreadsheet possibly have? Well, just one that I can think of is for say the Vending Machine Industry. What if statistics showed that the average person or target-customer carried an average of specific-number and denominations of coins in their pockets at any given time. You would then set the price of your vended-items accordingly for maximum profit or sellability. A spreadsheet might help you best-identify the target-price for each item.

Such issues may also be that industries' best kept secret. After all, if you know that a customer is willing to pay 20-cents more than the asking price because of the coin-combinations generally unavailable in his/her pocket, then you set the price accordingly and require exact-change. That's absolutely diabolical!!! Heh, heh. But such strategies can make you rich!

Again, I look forward to seeing who can produce a spreadsheet on the initial challenge, and Happy New Years!

 

[Ron Coderre]

Re: CONTINUED CHALLENGE and PRACTICAL USES

This VBA approach found 2 solutions:

1) On sheet1:
A1:G1 contains these values:
1.00
0.50
0.25
0.10
0.05
0.03
0.01

2) This sub is in the VBA module:

Sub FindCombos()
Const Max_1Cent As Integer = 4
Const Max_3Cent As Integer = 6
Const Max_5Cent As Integer = 1
Const Max_10Cent As Integer = 6
Const Max_25Cent As Integer = 1
Const Max_50Cent As Integer = 1
Const Max_100Cent As Integer = 1
Const Max_Coins As Integer = 6
Const Target1 As Double = 0.95
Const Target2 As Double = 1.15
Dim Ctr100 As Integer
Dim Ctr50 As Integer
Dim Ctr25 As Integer
Dim Ctr10 As Integer
Dim Ctr5 As Integer
Dim Ctr3 As Integer
Dim Ctr1 As Integer
Dim CoinCtr As Integer
Dim TestTotal As Double
Dim MatchCount As Integer
For Ctr100 = 0 To Max_100Cent
    For Ctr50 = 0 To Max_50Cent
        For Ctr25 = 0 To Max_25Cent
            For Ctr10 = 0 To Max_10Cent
                For Ctr5 = 0 To Max_5Cent
                    For Ctr3 = 0 To Max_3Cent
                        For Ctr1 = 0 To Max_1Cent
 
                            CoinCtr = Ctr100 + Ctr50 + Ctr25 + Ctr10 + Ctr5 + Ctr3 + Ctr1
                            TestTotal = Ctr100 + Ctr50 * 0.5 + Ctr25 * 0.25 + Ctr10 * 0.1 + Ctr5 * 0.05 + Ctr3 * 0.03 + Ctr1 * 0.01
 
                            If (CoinCtr > Max_Coins) Or (TestTotal = Target1) Then
                                Exit For
                            ElseIf (CoinCtr = Max_Coins) And (TestTotal = Target2) Then
                                MatchCount = MatchCount + 1
                                With ActiveSheet
                                    .Cells(MatchCount + 1, 1) = Ctr100
                                    .Cells(MatchCount + 1, 2) = Ctr50
                                    .Cells(MatchCount + 1, 3) = Ctr25
                                    .Cells(MatchCount + 1, 4) = Ctr10
                                    .Cells(MatchCount + 1, 5) = Ctr5
                                    .Cells(MatchCount + 1, 6) = Ctr3
                                    .Cells(MatchCount + 1, 7) = Ctr1
                                End With
                                Exit For
                            ElseIf TestTotal > Target2 Then
                                Exit For
                            End If
                        Next Ctr1
                        If (TestTotal = Target1) Then
                            Exit For
                        End If
                    Next Ctr3
                    If (TestTotal = Target1) Then
                        Exit For
                    End If
                Next Ctr5
                If (TestTotal = Target1) Then
                    Exit For
                End If
            Next Ctr10
            If (TestTotal = Target1) Then
                Exit For
            End If
        Next Ctr25
        If (TestTotal = Target1) Then
            Exit For
        End If
    Next Ctr50
Next Ctr100
End Sub

Running that sub returns these 2 solutions:

1.00  0.50  0.25  0.10  0.05  0.03  0.01
   1     0     0     0     0     5     0
   1     0     0     0     1     3     1 <--INVALID

Edited to include this comment:
Only the first solution is valid....3x0.03 + .01 = 0.10...My code did not test to make sure we cannot make change for a dime.

 

[shg]

If the answer were 50, 25, 10, 10, 10, 10, then Tommy could buy Ray the candy bar (he said can't, not won't), so that can't be the answer.

The workbook at http://www.box.com/shared/ubd28tissi could be used to calculate the possibilities, though it doesn't account for the 'can't make change' conditions. Here's the first few lines:

       --B-- -C-- -D-- -E-- -F-- -G-- -H-- ---I---- ---J---
   2    Cum: 480  240  120   60   12    6                  
   3    Cnt:   2    2    2    5    2    6                  
   4   Coin: 1.00 0.50 0.25 0.10 0.05 0.01                 
   5            0    0    0    0    0    0                 
   6            1    1    1    1    1    1                 
   7                           2         2                 
   8                           3         3                 
   9                           4         4                 
  10                                     5                 
  11                                                       
  12     #   Qty1 Qty2 Qty3 Qty4 Qty5 Qty6 6 coins? =$1.15?
  13     1      0    0    0    0    0    0 FALSE    FALSE  
  14     2      0    0    0    0    0    1 FALSE    FALSE  
  15     3      0    0    0    0    0    2 FALSE    FALSE  
  16     4      0    0    0    0    0    3 FALSE    FALSE  
  17     5      0    0    0    0    0    4 FALSE    FALSE  
  18     6      0    0    0    0    0    5 FALSE    FALSE  
  19     7      0    0    0    0    1    0 FALSE    FALSE  
  20     8      0    0    0    0    1    1 FALSE    FALSE  
  21     9      0    0    0    0    1    2 FALSE    FALSE  
  22    10      0    0    0    0    1    3 FALSE    FALSE  
  23    11      0    0    0    0    1    4 FALSE    FALSE  
  24    12      0    0    0    0    1    5 TRUE     FALSE  
  25    13      0    0    0    1    0    0 FALSE    FALSE

Ben's answer is is arrangement #229.

I like Ron's answer.

 

[xenou]

Applying pgc01's Permut/Combin algorithm, I found only three combinations of six coins (with repetition) that add up to $1.15, given denominations of 100,50,25,10,5,1.

50 25 25 05 05 05
50 25 10 10 10 10
25 25 25 25 10 05

So the second is the only one where that I can get exact change of 95 cents.

Note: BTW, I had 463 combinations of coins made up of dollars, half-dollars, quarters, nickels, and pennies, assuming that order does not matter -then filtered down to those that added up to $1.15 - shown above.

 

[shg]

In both the first and last you can make change for a dollar or 50 cents.

 

[xenou]

Yes - just realized I made the same mistake as previous solvers (I solved for "can" buy the candy bar instead of "can't" buy the candy bar. So Ron's answer makes the most sense. It's not possible given currently minted denominations, and this is a machine from circa 1889 that takes three cent coins... (!)

Did anyone catch CarTalk today to get their solution?

 

[shg]

From the web site:

RAY: Here's the answer. Before anyone gets his tights in a bunch, I just want to say that these are all American coins, currently in circulation and there were no subway tokens involved.

You need to know that vending machines do not take 50 cent pieces**.

Tommy has a 50 cent piece, a quarter and four dimes. You can't make change for a quarter. You can't make change for a dollar. You can't make change for a nickel or a dime.

I will admit, I haven't checked every vending machine on the planet but I did check several, and none of them would take a 50 cent coin.

** Who knew??

 

[BenMiller]

Hurray for me being right

 

[xenou]

RAY: Here's the answer. Before anyone gets his tights in a bunch, I just want to say that these are all American coins, currently in circulation and there were no subway tokens involved.

You need to know that vending machines do not take 50 cent pieces**.

Tommy has a 50 cent piece, a quarter and four dimes. You can't make change for a quarter. You can't make change for a dollar. You can't make change for a nickel or a dime.

I will admit, I haven't checked every vending machine on the planet but I did check several, and none of them would take a 50 cent coin.

Hehe. Good puzzler.

 

[Ron Coderre]

So....the catch is that vending machines don't take 50-cent coins, eh?
I knew I stopped listening to those bozos for a reason. :\