Snel ordenen

Nog een vraag van de wisfaq:

Ik ben me aan het voorbereiden voor toelatingsexamen aan de Koninklijke Militaire School en kwam volgende vraag tegen:
Sorteer a, b en c volgens stijgende waarden: a=√23; b=1199/250; c=959/200
Nu vroeg ik me af hoe ik dit efficiënt kan doen en zonder rekenmachine weliswaar!

Hoe doe je zoiets snel? Als ik veel haast heb bereken ik misschien 1199×200 en 959×250. Er geldt namelijk dat b>c precies als 1199×200>959×250 (via kruislings vermenigvuldigen) en daarnaast zou ik snel de kwadraten van b en c bepalen en met 23 vergelijken.

Die vermenigvuldigingen kosten wel wat tijd want de getallen zijn een beetje groot. Daarom kan het handig zijn iets beter naar de getallen te kijken. Dan blijkt dat die twee breuken hetzelfde gehele deel hebben, namelijk 4, en dat wat overblijft snel te vergelijken is:
1199/250=4+199/250=4+796/1000 en 959=4+159/200=4+795/1000 en nu zijn b en c in ieder geval heel eenvoudig te vergelijken: b>c.
En hoe zit het met √23? Het kwadrateren van b en  c kan iets sneller als je het indirect doet: schijf b=5-204/1000 en c=5-205/1000, en gebruik de bekende formule (x-y)2=x2-2xy+y2. Dan blijkt dat

  • b2=23-4/100+(204/1000)2, en
  • c2=23-5/100+(205/1000)2.

Nu is (204/1000)2 net iets meer dan (2/10)2=4/100, dus b2 is net iets groter dan 23.
Ook (205/1000)2 is iets meer dan 4/100 maar niet te veel: het is kleiner dan het makkelijkere kwadraat (21/100)2=4,41/100 en dat is weer kleiner dan 5/100, dus c2 is kleiner dan 23.

Conclusie: 959/200<√23<1199/250.

Ik vind dit een aardige opgave omdat met weinig niet al te moeilijke vermenigvuldigingen en delingen drie getallen die heel dicht bij elkaar liggen toch mooi onderscheiden kunnen worden.

Be Sociable, Share!

1 comment

Leave a Reply

Your email address will not be published. Required fields are marked *

© 2011 TU Delft