Algorithm Theory

Algorithm Theory involves the design, analysis, and understanding of algorithms – step-by-step procedures for solving problems. Questions might ask to devise an algorithm for a task, analyze its efficiency (e.g., number of steps), or trace its execution.

• Question

  Can you divide `24` kilograms of nails into two parts of `15` and `9` kilograms using a balance scale without weights?

  Topics:

  Arithmetic Proof and Example -> Constructing an Example / Counterexample Algorithm Theory -> Weighing

• The Sophisticated Task

  Hannah has a basket with `13` apples. Hannah wants to know the total weight of all these apples. Rachel has a digital scale, and she is willing to help Hannah, but only under the following conditions: In each weighing, Hannah can weigh exactly `2` apples, and the number of weighings cannot exceed `8`.

  Explain how, under these conditions, Hannah can know the total weight of the apples.

  Topics:

  Combinatorics -> Double Counting Algebra -> Equations Algebra -> Word Problems Proof and Example -> Constructing an Example / Counterexample Algorithm Theory -> Weighing
  Sources:
  • problems.ru web site

• 9 Coins

  Given `9` coins that look identical. One of the coins is counterfeit, and its weight is less than the weight of a regular coin. How to find the counterfeit coin using two weighings on a balance scale without weights?

  Topics:

  Logic -> Reasoning / Logic Algorithm Theory -> Weighing Minimum and Maximum Problems / Optimization Problems

• 26 Coins

  Given `26` coins that look identical. One of the coins is counterfeit, and it weighs less than a regular coin. How can you find the counterfeit coin using three weighings on a balance scale without weights?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Induction (Mathematical Induction) Logic -> Reasoning / Logic Algorithm Theory -> Weighing Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems

• 80 Coins

  Given `80` coins that look identical. One of the coins is counterfeit and weighs less than a regular coin. How can you find the counterfeit coin using four weighings on a balance scale without weights?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Induction (Mathematical Induction) Logic -> Reasoning / Logic Algorithm Theory -> Weighing Minimum and Maximum Problems / Optimization Problems

• 9 Kilograms of Rice

  You have `9` kilograms of rice. How can you measure `2` kilograms of rice using three weighings on a balance scale and using two weights: one of `200` grams and one of `50` grams?

  Topics:

  Proof and Example -> Constructing an Example / Counterexample Algorithm Theory -> Weighing

• Weighing Coins

  Given are seven outwardly identical coins; four are genuine and three are counterfeit. The three counterfeit coins are of identical weight, as are the four genuine coins.
  It is known that a counterfeit coin is lighter than a genuine coin. In one weighing, you can select two groups of coins and determine which is lighter, or if they have the same weight.
  How many weighings are needed to locate at least one counterfeit coin?

  Topics:

  Logic -> Reasoning / Logic Algorithm Theory -> Weighing Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Gillis Mathematical Olympiad, 2019-2020 Question 1

• STEALING THE CASTLE TREASURE

  The ingenious manner in which a box of treasure, consisting principally of jewels and precious stones, was stolen from Gloomhurst Castle has been handed down as a tradition in the De Gourney family. The thieves consisted of a man, a youth, and a small boy, whose only mode of escape with the box of treasure was by means of a high window. Outside the window was fixed a pulley, over which ran a rope with a basket at each end. When one basket was on the ground the other was at the window. The rope was so disposed that the persons in the basket could neither help themselves by means of it nor receive help from others. In short, the only way the baskets could be used was by placing a heavier weight in one than in the other.

  Now, the man weighed `195` lbs., the youth `105` lbs., the boy `90` lbs., and the box of treasure `75` lbs. The weight in the descending basket could not exceed that in the other by more than `15` lbs. without causing a descent so rapid as to be most dangerous to a human being, though it would not injure the stolen property. Only two persons, or one person and the treasure, could be placed in the same basket at one time. How did they all manage to escape and take the box of treasure with them?

  The puzzle is to find the shortest way of performing the feat, which in itself is not difficult. Remember, a person cannot help himself by hanging on to the rope, the only way being to go down "with a bump," with the weight in the other basket as a counterpoise.

  Topics:

  Algebra -> Word Problems Algorithm Theory -> Weighing Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 377