Difference between pages "1.3" and "2.51"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(Created page with " a ----------- c ----------- b \ / \--------- d ---------- / If the distance from ''a'' to ''b'' going through ''d'' is less than the dista...")
 
(Created page with "<pre> 1) Find an empty bag (labeled "E") 2) Place 1 coin from bag 1 into E 3) Place 2 coins from bag 2 into E ... 10) Place 9 coins from bag 9 into E 11) Place 10 coins from b...")
 
Line 1: Line 1:
−
  a ----------- c ----------- b
+
<pre>
−
    \                        /
+
1) Find an empty bag (labeled "E")
−
    \--------- d ---------- /
+
2) Place 1 coin from bag 1 into E
 +
3) Place 2 coins from bag 2 into E
 +
...
 +
10) Place 9 coins from bag 9 into E
 +
11) Place 10 coins from bag 10 into E
 +
12) Weigh bag E on your digital scale
 +
</pre>
  
−
If the distance from ''a'' to ''b'' going through ''d'' is less than the distance from ''a'' to ''b'' going through ''c'' but there is a busy traffic intersection at ''d'' with a stop sign that is always backed up, then the route from ''a'' to ''b'' through ''c'' is faster, but the route through ''d'' is shorter.
+
If all coins were 10 grams, the bag would weigh 550 grams.  Thus, <math>550 - weight</math> will tell you how many coins are too light.  Since this number of coins correlates to the bag from which the coins came, you now know which bag contains the light coins.
  
  
−
For example,
+
Back to [[Chapter 2]]
−
 
 
−
<math>dist(a, c) = 10</math> miles
 
−
 
 
−
<math>dist(c, b) = 5</math> miles
 
−
 
 
−
So the distance from ''a'' to ''b'' through ''c'' is 15 miles. Assuming you drive 30 miles per hour, the time to travel this would be 30 minutes
 
−
 
 
−
 
 
−
<math>dist(a, d) = 5</math> miles
 
−
 
 
−
<math>dist(c, b) = 5</math> miles
 
−
 
 
−
So the distance from ''a'' to ''b'' through ''d'' is 10 miles. Assuming you drive 30 miles per hour, the time to travel this would be 20 minutes, but due to the busy intersection at ''d'', you are delayed 15 minutes, the total time would be 35 minutes.
 
−
 
 
−
---
 
−
 
 
−
Another possible solution: You have a longer route with a higher speed and a shorter route with a lower speed. By choosing the numbers appropriately, you can make the longer route be the winner. The speed may be due to law, or due to traffic jam, or because of pot holes on the road :-)
 
−
 
 
−
Suppose road of length l1 has speed limit s1 and another road of length l2 has speed limit l2. The shorter route is determined by comparing l1 with l2. The faster route is determined by comparing l1/s1 with l2/s2. With positive numbers, if l1 > l2 but l1 < l2 * s1 / s2, then the faster route differs from the shorter route.
 
−
 
 
−
 
 
−
Back to [[Chapter 1]]
 

Latest revision as of 19:43, 10 September 2020

1) Find an empty bag (labeled "E")
2) Place 1 coin from bag 1 into E
3) Place 2 coins from bag 2 into E
...
10) Place 9 coins from bag 9 into E
11) Place 10 coins from bag 10 into E
12) Weigh bag E on your digital scale

If all coins were 10 grams, the bag would weigh 550 grams. Thus, [math]\displaystyle{ 550 - weight }[/math] will tell you how many coins are too light. Since this number of coins correlates to the bag from which the coins came, you now know which bag contains the light coins.


Back to Chapter 2

Retrieved from "https://algorist.com//algowiki/index.php?title=1.3&oldid=140"