ࡱ> :<9M bjbj== ]`WWP0]l$ 000P214f1 >.2D2"f2f2f2 $ x E if2f2Niii v f2f2i ii9V 9f2"2   0Ãx990>9;.9i   Paper Reference(s) 6689 Edexcel GCE Decision Mathematics D1 Advanced/Advanced Subsidiary Tuesday 10 June 2003 ( Afternoon Time: 1 hour 30 minutes Materials required for examination Items included with question papers Nil D1 Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates must NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP48G. Instructions to Candidates In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature. Information for Candidates Full marks may be obtained for answers to ALL questions. This paper has seven questions. Advice to Candidates You must ensure that your answers to parts of questions are clearly labelled. You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit. This publication may only be reproduced in accordance with Edexcel copyright policy. Edexcel Foundation is a registered charity. 2003 Edexcel Write your answers in the Dl answer booklet for this paper.  1. Six workers A, B, C, D, E and F are to be matched to six tasks 1, 2, 3, 4, 5 and 6. The table below shows the tasks that each worker is able to do. WorkerTasksA2, 3, 5B1, 3, 4, 5C2D3, 6E2, 4, 5F1 A bipartite graph showing this information is drawn in the answer booklet. Initially, A, B, D and E are allocated to tasks 2, 1, 3 and 5 respectively. Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly. (5)  2. (a) Explain why it is impossible to draw a network with exactly three odd vertices. (2) Figure 1 x + 1 D B x 5  EMBED Equation.3  x A E x 4 C 2x 14 x 1 x 3 F x G The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100. (b) Determine the value of x, showing your working clearly. (4) 3. (a) Describe the differences between Prims algorithm and Kruskals algorithm for finding a minimum connector of a network. (3 marks) Figure 2 C 25 F  15 35 14 A 17 B 24 21 E 18 16 20 D 32 G (b) Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using (i) Prims algorithm, (ii) Kruskals algorithm. (4)  4. The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper (R), Palmer (P), Boase (B), Young (Y), Thomas (T), Kenney (K), Morris (M), Halliwell(H), Wicker (W), Garesalingam (G). (a) Use the quick sort algorithm to sort the names above into alphabetical order. (5) (b) Use the binary search algorithm to locate the name Kenney. (4)  5. Figure 3 C(23) F(10) K(19) A(12) J(6) H(18) L(13) D(14) G(15) I(20) B(17) M(27) E(32) The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. (a) Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet. (4) (b) Hence determine the critical activities. (2) (c) Calculate the total float time for D. (2) Each activity requires only one person. (d) Find a lower bound for the number of workers needed to complete the process in the minimum time. (2) Given that there are only three workers available, and that workers may not share an activity, (e) schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time. (5)  6. A company produces two types of self-assembly wooden bedroom suites, the Oxford and the York. After the pieces of wood have been cut and finished, all the materials have to be packaged. The table below shows the time, in hours, needed to complete each stage of the process and the profit made, in pounds, on each type of suite. OxfordYorkCutting46Finishing3.54Packaging24Profit ()300500 The times available each week for cutting, finishing and packaging are 66, 56 and 40 hours respectively. The company wishes to maximise its profit. Let x be the number of Oxford, and y be the number of York suites made each week. (a) Write down the objective function. (1) (b) In addition to 2x + 3y ( 33, x ( 0, y ( 0, find two further inequalities to model the companys situation. (2) (c) On the grid in the answer booklet, illustrate all the inequalities, indicating clearly the feasible region. (4) (d) Explain how you would locate the optimal point. (2) (e) Determine the number of Oxford and York suites that should be made each week and the maximum profit gained. (3) It is noticed that when the optimal solution is adopted, the time needed for one of the three stages of the process is less than that available. (f) Identify this stage and state by how many hours the time may be reduced. (3)  7. Figure 4  F 8 (5) C 9 (9) 15 (15) 4(4) T1 E 24 (20) H 15 (10) 10 (5) 28 (x) 8 (6) A 20 (18) D S1 T2 45 (38) 25 (18) 12 (12) 8 (y) 25 (25) S2 35 (30) B 20 (18) G C1 C2 Figure 4 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network. (a) Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 2 in the answer booklet. (2) (b) Find the values of x and y, explaining your method briefly. (2) (c) Find the value of cuts C1 and C2. (3) Starting with the given feasible flow of 68, (d) use the labelling procedure on Diagram 3 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. (6) (e) Show your maximal flow on Diagram 4 and state its value. (3) (f) Prove that your flow is maximal. (2)  END PAGE  N9978 PAGE 6 N13901A N13901A (]rstu\UYZu_`u;<=   # $ & ' ) * , - / 0 5 6 ŽŶ 6mH sH j5CJUmHnHu56CJDmH sH mH sH  5mH sH j5UmHnHu CJmH sH 5CJmH sH 5>*CJmH sH  CJmH sH  j-5CJ$mH sH 5CJ$mH sH 5CJ<mH sH 5CJ*mH sH  CJ mH sH 2(@]Z[\UVWX  7^ d1$7$8$H$ ( dh1$7$8$H$ dh1$7$8$H$ 1$7$8$H$ 771$7$8$H$^7PXYu>^_u<=>?@AB 7 z)71$7$8$H$^7``$ d1$7$8$H$^a$^$ dh1$7$8$H$^a$ 11$7$8$H$^BCD   l m $$Ifa$$a$$`a$^$a$$`a$ 7 z)71$7$8$H$^7` ,8 , $$Ifa$i$$Ifl0p$ $ 04 la K L N O Q R W X # & ' ( , 4 = > B C D    & 2 7 ; B J  jCJUmHnHujEHUmH sH joϒB CJUVmHnHujUmH sH j6UmHnHuj5UmHnHu 5mH sH  6mH sH mH sH A ? @ # ' > ? ~q $ h`a$$^a$$a$i$$Ifl0p$ $ 04 la $$Ifa$ & 7 @ A B J $^a$ $^`a$$^a$ $^`a$ $^`a$$a$$^a$$ 7@a$ $ a$$a$J K ^  $^a$ $^`a$$a$$ ^`a$$ ^`a$$a$$ ha$$a$    18:=>LPnoz{8<=>{j6UmHnHu5jCJUmHnHu6jUmHnHu 5mH sH 5\mH sH  6mH sH mH sH K:;<fg8$`a$ $ `a$ `$ `a$$ a$$ \^`\a$$p^pa$$a$8<{() $^`a$ $^`a$$^a$ $^`a$$a$ $P^P`a$$`a$$ ha$ $ ha$ $ ^a$ $ dha$  "#*18~|>BCDWX\]^_dfgklmn(,-.`d jmH sH  jmH sH 5jCJUmHnHu 5mH sH  6mH sH mH sH 6Q)*678~$ n^`na$$ ndh^`na$$ n^`na$$a$$`a$ $p^p`a$ $^`a$| $$Ifa$$a$$`a$ $^`a$$`a$$ n^`na$$ n^`na$w4n $$Ifa$~$$Ifl_F20    4 la $$Ifa$ Dwnn $$Ifa$ $$Ifa$~$$Ifl`F20    4 la  <wnn $$Ifa$ $$Ifa$~$$Ifl_F20    4 la$(,-.Pwnniiiiiii$a$ $$Ifa$ $$Ifa$~$$Ifl`F20    4 la >BUVdkrs(,`d$ J^`Ja$$ Jdh^`Ja$$ J^`Ja$$a$$dha$$a$ $ dha$$ a$deflm!"#'9Jmn| /MOPUVcdeg23   @A H*mH sH H*6j5UmHnHu5jCJUmHnHu 5mH sH  6mH sH mH sH Pjk #'9R $^`a$$^a$ $^`a$$@ ^@ a$ $^`a$ $@ ^@ `a$$`a$$a$$a$$ J^`Ja$$ a$Rp|OPfg01$ J^`Ja$ $^`a$$`a$ $^`a$$^a$$a$$^a$ $P^P`a$ $@ ^@ `a$ >?DHIKOP 9r $ 9r 0^`0a$$ 9r 0^`0a$$a$$ J^`Ja$$ J^`Ja$$ Jdh^`Ja$ !DHIJKOPQWXY^`abhijklsu|~0JmHnHuCJ CJ0J j0JU5jCJUmHnHu 6mH sH mH sH  5mH sH PY`altu~  z)1$7$8$H$&`#$ 9r 1 0 00&P P. A! "#$%(&P 1h. A!"#$% DdThB  S A? 2x¸a 6s.CTD `!L¸a 6s.C @XJ|xcdd``~$d@9`,&FF(`T̐ & $d3H1icYP{ 憪aM,,He`H`b e-¤f Y.rح,L ! ~ Ay ߖ_H_^e5lWXgE%<05<&0n{XFH0߰ s.p耭EOF&&\ iOAhLxN  !"#$%&'()*+,-./02345678;>?@BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry  F=Data 1WordDocument ]`ObjectPool _1116917615F@@Ole CompObjfObjInfo  FMicrosoft Equation 3.0 DS Equation Equation.39q   12 xOh+'0 , H T ` lxEquation Native <1TableASummaryInformation( DocumentSummaryInformation8 ,Paper Reference(s)ape Benjaminereenjenj Normal.doteAdministratore(3miMicrosoft Word 9.0@V@@0@L1@hy՜.+,0 hp|   .  Paper Reference(s) Title  FMicrosoft Word Document MSWordDocWord.Document.89q i8@8 NormalCJ_HaJmH sH tH 8@8 Heading 1$@& 56\]@@@ Heading 2$$@&a$5mH sH uF@F Heading 3$$@&a$6\]mH sH u<A@< Default Paragraph Font,@, Header  9r , @, Footer  9r &)@& Page NumberhC@"h Body Text Indent$$ 771$7$8$H$^7a$5CJmH sH u:B@2: Body Text$a$\mH sH uNS@BN Body Text Indent 3 ^\mH sH u  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\0;<=>?@ABCD E F G H IJKLMNOPQRSTUVWXYZ[[+!,"-#.$/%0&1'2(3)4*5+6,7-8.9/:123456789 : ; < = >?@ABCDEFGHIJKLMNOP Q!R"S#T$U%V&W'X(Y)Z* \  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\_      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[`3`(@]Z[\UVWXYu>^_u<=>?@ABCDlm?@#'>? &7@ABJK^     : ; < f g 8 < {  ( ) * 6 7 8 ~|  $(,-.>BUVdkrs(,`djk #'9Rp|OPfg01 >?DHIKOPaltu~<<<<<<<<<`<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<0<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<0@@0@@@@ %%///////2  d'+XB J 8) RP !"#$%&()*,-./:2!!@B p0e0e     A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@LdAK(   = fBM#CDEFM#@S" > TB\#CDEF\#@3"VB ? C D"VB @ C D"VB A C D" B fBk#CDEFk#@S" v TBY#CDEFY#@3"  y TBy#CDEFy#@3"   ZB}#CDEFԔ}#@3"  fBM#CDEFM#@S"VB  C D"  b r N'!D4  3"fB  s *DN')B B ZD?r ).B B HD?HZ'.B B HD?6.H.B  HD?r .6.~B  BD?)6.   0e0e    BC]DEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||]@.N=4B  ZD?>4!D4~B  BD?N.!>4Z b 6 < "  3"~B  BD?H < zB  ZD?< !<    0e0e    BCYDEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||Y@B ~B  BD?< Z   0e0e    BDCDEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||D@Z~B  BD?Z< !~B  BD?B  ZD?6 zB  TD?"~B  BD?!< "~B  BD?Z".b }(  3" @ L }(  }(~B  BD? Z ~B B BD?Z < rB  6D?N ~B  BD? 3xB  <D? xB  <D?  /rB  6D?, 0rB  6D?0    0e0e    BCDEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@0    0e0e    B CZDEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| Z@ }(r rB   6D?p \( xB   <D?$p \(xB   <D? rB   6D?*     0e0e    B$CDEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||$@  xB  <D?j4xB  <D?TxxB  <D?xB  <D?lxB  <D?  xB  <D? $ * xB  <D?2bxB  <D?! Z!& xB  <D?p  xB  <D?  xB  <D?xB  <D?:FxB  <D?&"Z t"` b C ' A 3" HL C ' /C ' L  ' - 'L  ' , '~B  BD?.8%.~B  BD?rB   6D?.&%xB ! <D?.~B " BD? $=xB # <D?:$R rB $ 6D?R 8%.xB % <D?^ P &xB & <D?LZ!rB ' 6D?l 'P xB (B <D?l xB )B <D?p .rB * 6D?z :$ +  0e0e    B C#DEF 5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| #@ .  0e0e    BpCWDE\F 5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| W k Ir vi ZE /  j 2 w s #  T F9 ,} ,WN|ugY$;=#7;h SS z PM L  &r .d >] HP T@ `0 i q q z t \ "4 L 4 e x  Z | @zf[V='r-]]eB &7BIXvXX!P6bQN |O EX = # #     * ~  &7GXihN(5Ssb d L87N!Yppgh@                                                  CW"xB 0 <D? 8 xB 1 <D?n 2  0e0e    B]C?DEF A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||?]@d  XxB 3 <D?NrxB 4 <D?lxB 5 <D?x..xB 6 <D?.6 .xB 7 <D?  xB 8 <D? P xB 9 <D?F#L #| xB : <D?< & xB ; <D?f  xB < <D?|RxB = <D?4xB > <D?#B$ xB ? <D?b"N"xB @ <D?.F.B S  ?Y_' I?<<t@4G4tA:c:tM# t=0#t  tBM#t$t t>s#tvA#t0"tR#tyz#tAl![t4l#9t' - < E ~ ;FMVKTPs~CD  12:;  _ f   0 2 Ndekltx!CFP33333333333333333333333333333 OPakcummingga\\hera\comatec\Sums\Graham's e-mail emporium\04 GCE C2000\19 June 2003 papers\38 D1 June 2003.doccummingga\\hera\comatec\Sums\Graham's e-mail emporium\04 GCE C2000\19 June 2003 papers\38 D1 June 2003.doccummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asdcummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asdcummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asdcummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asdcummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asdcummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asdcummingg7C:\autorecover\AutoRecovery save of 38 D1 June 2003.asd Administrator9W:\maths\A level\Edexel papers&info\jun03\decision\D1.doc  $(,-P@ (U P@UnknownGz Times New Roman5Symbol3& z Arial"qh"lvKtcv .20d2Paper Reference(s)Benjamin AdministratorCompObjj