Search Results

Problem . Fred brings home 100 kg of potatoes, made up of 99% water. He leaves them outside, allowing for some water to evaporate, thus reducing the water content to 98%. How much do the potatoes weigh now? Answer . The new weight is 50 kg. Fig 1 . Potatoes contain about 80% water on average. Solution . At first glance, the answer might seem illogical. The water content dropped by only 1%, so the weight shouldn't change much. However, the solid content doubled from 1% to 2%. The solids didn't evaporate, meaning their weight stayed the same. This is the factor we should focus on because the new proportions must account for this constant. If the proportion of solids in the new weight has doubled, then the amount of water, and thus its weight, must be halved. The Potato Paradox skillfully diverts attention from the key point, playing on a common confusion about percentages. Once this confusion is cleared, the solution is simple: 1 kg (constant) + 49 kg (halved) = 50 kg. Now, let's do it slowly, starting with defining percentages. Percentages represent the ratio of ingredients in a mix. The entire mix is considered to be 100%, meaning it is divided into 100 equal parts. The percentage of each ingredient indicates how many parts out of 100 it makes up. The initial figures, 1% and 99% , were calculated based on the weight of 100 kg. Dividing 100 kg into 100 parts, we estimate that each part weighs 1 kg: 1%  (solids)  + 99% (water) = 100%  (initial weight) 1 part (solids) + 99 parts (water) = 100 parts (initial weight), 1 kg + 99 kg = 100 kg The new figures, 2% and 98% , are based on the new weight, which we again take as 100%: 2%  (solids) + 98% (water) = 100%  (new weight) 2 parts  (solids)  + 98 parts (water) = 100 parts  (new weight)   The new weight differs because the weight of the water has changed, while the solids weigh the same, 1 kg. Now, this 1kg accounts for 2 parts of the new weight, meaning each part weighs 1/2 kg. 2 parts = 1kg , so 1 parts  = 1/2 kg 1/2 kg x 2 + 1/2 kg x 98 = 1 kg + 49 kg = 50 kg The new weight is indeed 50 kg.

The greatest common divisor (GCD) of two numbers, say 12  and 8 , is the greatest number (in this case, 4) that divides them without a remainder. It is denoted as gcd(12, 8) = 4 . Note that numbers 12  and 8  have other common divisors, 1 and 2, lower than 4. The Greatest Common Divisor is also called the Highest Common Factor (HCF). Fig. 1  Using the Euclidean algorithm, we can manually calculate the greatest common divisor.   We use the greatest common divisor (GCD) to determine a relationship between different quantities. Consider having 12  blue and 8  red cans of paint. We want to know what color we get by mixing them. The  gcd(12, 8)=4  simplifies a ratio 12:8 to 3:2. Now we can reference a color mixing guide and learn that the color will be purple ( Fig. 2 ). The GCD is also used to simplify fractions and related tasks. Fig. 2.   Three blue and two red parts make purple. Source: BBC Bitesize When dealing with small numbers, we can find the GCD by listing all divisors and choosing the largest. However, this will get increasingly problematic when numbers grow larger. For example, mixing 693  blue and 462  red cans will also make purple because the gcd(693, 462) = 231  simplifies 693:462 to 3:2. Finding all common divisors, such as 1, 3, 7, 11, 21, 33, 77, and 231, is a time consuming task, prone to mistakes. So, is there a way to find the greatest common divisor, bypassing all the lower ones? The Euclidean algorithm does just that.     Euclidean algorithm  (geometrical illustration)   Euclid introduced this algorithm in his treatise Elements around 300 BC, using a geometrical approach to illustrate it. In Fig. 3 , left, we consider two lengths, AB  and CD , which have no numeric values. We aim to find the greatest common unit that divides them exactly. This unit is  CF , though we don't know it yet. Once identified, CF can quantify the lengths as AB=10xCF  and CD=7xCF , with a ratio of 10:7. Here, 10 and 7 are integers, proving the GCD stipulation is satisfied. How do we find the unit CF ?   The Euclidean algorithm begins its search from the top of the ladder, unlike our previous approach, which started from the bottom. The algorithm selects the highest possible GCD for the two lengths, which is the shorter length, and checks if it fits into AB without a remainder. The GCD can't exceed the shorter length because dividing the smaller by the larger results in a fraction. If we had AE  and CF  ( Fig. 3 , right) as the starting pairs, this step would yield the answer immediately, gcd(AE, CF) =CF . Euclid chose a more interesting option. Fig. 3   Euclidean algorithm, geometrical illustration. We start with two lengths, AB  and CD  ( Fig. 3 , mid-left), where CD is the shortest. CD  fits into AB  once, with AE  left as a remainder. This step splits AB  into two segments, EB  and AE , which means we can replace gcd(AB, CD) with gcd(EB, AE, CD). Given that EB = CD , we have gcd(AB, CD) = gcd(CD, AE, CD). Discarding a duplicate CD, we arrive at:   gcd(AB, CD) = gcd(CD, AE) , where AE = AB - CD   Continuing with the new pair, CD  and AE , Fig. 3  mid-right, we again divide the longer CD by the shorter AE  and have a remainder CF . This splits CD  into three segments, AE ,  AE , and CF , so we can write gcd(CD, AE) = gcd(AE, AE, CF, AE) = gcd(AE, CF):    gcd(CD, AE) = gcd(AE, CF) , where CF = CD - 2x AE   Assuming CD=a , AE=b , 2 =q  (quotient), and CF=r  (remainder), we conclude:    gcd(a, b) = gcd(b, r) , where r = a - qxb   It is irrelevant how many times the shorter length fits into the longer. This will affect the ratio (10:7) but not the GCD. We focus exclusively on the remainder, r = CF , and the shorter length, AE , because they will make the next pair, AE and CF . So, we can replace subtraction with division, and find the remainder using this operation:   AE ÷   CF = 3 with a remainder of 0  ( r=0 ) This principle of substituting the longer length with the shorter one is fundamental to the Euclidean algorithm. The remainder ( r ) will be smaller than a  and b , so we will keep reducing the lengths until one divides perfectly into the other.. When this occurs, the GCD is determined ( Fig. 3 , right).   Applying the Euclidean algorithm to lengths   The Euclidean algorithm is a systematic process that efficiently finds the GCD. During each step, it selects a shorter length as the candidate for the GCD, discards it if proven wrong, and continues the process until the remainder is zero. This approach ensures no greater divisor is overlooked and no smaller divisor is tested. When r=0, no new pair can be formed, eliminating further division. Let's now see how the algorithm works in practice. First, we divide the longer AB by the shorter CD : Step 1 AB÷CD = 1 with a remainder of  AE   We have a remainder r = AE  and will continue with a new pair, CD  and AE .   Step 2 CD÷AE = 2 with a remainder of CF   We still have a remainder, r=CF , and continue with a new pair, AE  and CF :   Step 3 AE÷CF = 3 exactly ( r=0 )   There is no remainder. The gcd(AB, CD) = CF .     Euclidean algorithm  (numerical illustration)   We can also prove the algorithm using a numerical approach. In Fig. 4 , two groups of dots represent numbers 30  and 12 . The gcd(30, 12)=6  is the largest unit, comprising 6  dots, that divides them both evenly. Now, we can express the size of each group as 30=5 x 6  and 12=2 x 6 , simplifying their ratio from 30:12 to 5:2. Fig. 4   Euclidean algorithm illustrated with dots. We know that the GCD of two numbers will be the smaller number, provided it divides the larger number without a remainder. This would be the case if we had numbers 30 and 5, for instance. In our case, 30÷12= 2  with a remainder of 6 . The division breaks 30  into three numbers, 12 , 12 , and 6 , Fig. 4 . Fig. 5   Proof of the Euclidean algorithm, numerical method So,rather than calculating gcd(30, 12), we need to determine gcd(12, 12, 6, 12). Discarding the duplicate 12s, we get gcd(30, 12) =   gcd(12, 6) . In other words, the same principle applies, with a slightly different approach to visualizing the algorithm for clearer understanding. Applying the Euclidean algorithm to numbers   The approach remains unchanged. So, we'll use this demonstration to explore how the algorithm identifies shortcuts to the solution. Without the Euclidean algorithm, we would have to go through all divisors, starting with the lowest and finishing with the highest. The divisors of 30  are 1, 2, 3, 5, 6, 10, 15, 30, while those of 12  are 1, 2, 3, 4, 6, 12. The common divisors are 1, 2, 3, and 6, with the greatest being 6 . Even with the numbers as small as 30  and 12 , this method is tedious and prone to errors. Let's see how the Euclidean algorithm eliminates several divisors at each step.   Step 1 30 ÷ 12 = 2 remainder  6   Two divisors are eliminated: 18 for being higher than 12, and 12 for leaving a remainder. The new pair is 12  and 6 .   Step 2 12 ÷ 6 = 2  exactly.     Five divisors are eliminated when  gcd(18, 12)=6  is identified: 9 for being higher than 6 , and 1, 2, 3, 4 for being lower than 6 .     Additional examples   Example 1 .  This represents the classic Euclidean scenario, depicted in Fig. 2 , where we allocate numerical values as AB=130  and CD=91  (ratio 10:7).   Given pair 130  and 91 130 ÷ 91 = 1 remainder 39 New pair  91  and 39 91÷39=2 remainder 13                       New pair  39  and 13 39÷ 13 =3 ( r=0 ). gcd(130, 91) = 13                          Example 2 . Using the Euclidean algorithm is crucial when dealing with larger numbers such as 3623  and 1017 . These numbers share only one common divisor, which is 1 . This is the smallest common divisor possible since every number is divisible by 1.   Given pair 3623  and 1017 3623 ÷ 1017 = 3 remainder 572     New pair  1017  and 572 1017 ÷ 572 = 1 remainder  445                       New pair  572  and 445 572 ÷ 445 = 1 remainder 127 New pair  445  and 127 445 ÷ 127 = 3 remainder 64 New pair  127  and 64 127 ÷ 64 = 1 remainder 63  New pair  64  and 63 64 ÷ 63= 1 remainder 1  (64 = 1x63 +1) New pair  63  and 1 63 ÷ 1 = 63 ( r=0 ). gcd(3623, 1017) = 1     The GCD of three or more numbers   Finding the GCD of three or more numbers may seem daunting, but it is easier than you think. The key factor is that the GCD of multiple numbers can't exceed the GCD of any two because it must divide each number without a remainder. We choose the two lowest numbers, a  and b . If gcd(a, b)=1 , then the GCD of all numbers is 1 , gcd(a, b, c...)=1 . If gcd(a, b)=2 , and all remaining numbers are even, then gcd(a, b, c...)=2 .  However, if gcd(a, b)=2 , and there are odd numbers among the others, then gcd(a, b, c...)=1 . This is because if the GCD of all numbers can't be 2 or greater, then the only possibility left is 1 . It is uncommon for a random set of numbers to have a high GCD, so the more numbers involved, the greater the likelihood of the GCD being low. In general, the formula is:   gcd(a, b, c) = gcd[c, gcd(a, b)]      Applying this formula, you can calculate the GCD of as many numbers as you need.