Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Martin Gardner gave a neat solution to the "Counterfeit Coin" problem.  The tough one -

"Given 11 coins of equal weight and one that appears identical but is either heavier or lighter than the others, use a balance pan scale to determine which coin is counterfeit and whether it is heavy or light.  And do it with three weighings." 

This summary is copied from alt.rec.puzzles newsgroup entry

 Assume that you are allowed W weighings. Write down the 3^W possible length W strings of the symbols '0', '1', and '2'. Eliminate the three such strings that consist of only one symbol repeated W times.

For each string, find the first symbol that is different from the symbol preceeding it. Consider that pair of symbols. If that pair is not 01, 12, or 20, cross out that string. In other words, we only allow strings of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).

You will have (3^W-3)/2 strings left. This is how many coins you can handle in W weighings.

Perform W weighings as follows:

For weighing I, take all the coins that have a 0 in string position I, and weigh them against all the coins that have a 2 in string position I.

If the side with the 0's in position I goes down, write down a 0. If the other side goes down, write down a 2. Otherwise, write down a 1.

After the W weighings, you have written down an W symbol string. If your string matches the string on one of the coins, then that is the odd coin, and it is heavy. If none of them match, than change every 2 to a 0 in your string, and every 0 to a 2. You will then have a string that matches one of the coins, and that coin is lighter than the others.

Note that if you only have to identify the odd coin, but don't have to determine if it is heavy or light, you can handle (3^W-3)/2+1 coins. Label the extra coin with a string of all 1's, and use the above method.

Note also that you can handle (3^W-3)/2+1 coins if you *do* have to determine whether it is heavy or light, provided you have a single reference coin available, which you know has the correct weight. You do this by labelling the extra coin with a string of all 2s. This results in it being placed on the same side of the scales each time, and in that side of the scales having one more coin than the other each time. So you put the reference coin on the other side of the scales to the "all 2s" coin on each weighing.

Proving that this works is straightforward, once you notice that the method of string construction makes sure that in each position, 1/3 of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a string occurs, then the string obtained by replacing each 0 with a 2 and each 2 with a 0 does not occur.

If you already know the odd coin is heavy (or light), you can handle 3^W coins. 

Given W weighings, there can only be 3^W possible combinations of balances, left pan heavy, and right pan heavy.

The algorithm in this case:

Divide the coins into three equal groups... A, B, and C. Weigh A against B. If a pan sinks, it contains the heavy coin, otherwise, the heavy coin is in group C. If your group size is 1, you've found the coin, otherwise recurse on the group containing the heavy coin.

 

These algorithms have been implemented here at DelphiForFun in the program described and downloadable from this Counterfeit Coins page.

 

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.