MSF Challenge 2006
( A Joint Initiative with NIIT )
Mathematics with Computation
    
     
Home   ||  Rules    ||   Problem (Group A)   ||   Problem (Group B)   ||   Downloads   ||   FAQ   ||   Deadline  ||  Comments   
 
 
Prestigious competition with attractive prizes.
Important Dates
This contest is open to schools in Delhi and NCR.. They may enter teams in two age groups
Group B (Senior Level): for students of classes XI and XII

(Download Problems for Group B)
Submission of Form by School
July 5, 2006
Submission of Solution/Paper
July 5, 2006
Instructions
  • The problem you choose should be considered interesting to your team.
  • Mathematicians and Scientists often do the following activities to gain “intuition” about a problem situation. You may find them helpful too.
 
  • Try small cases or simpler versions of a problem first
  • Doing numerical computations
  • Drawing pictures
  • Writing programs or using computer software to list special cases or to test your hypothesis
  • Think a bit about whether your solution and method can generalize or can be used in modified situations. Mention these generalizations in your paper.
  • Even partial solutions may be acceptable. What is important is how you approach things, and whether your team got a few insights. Communicating those insights in the paper is important.
  • Think independently. Creative ideas and approaches will get more credit from our distinguished jury.

Problems
Group B (For Classes XI & XII).
Problem B1:
Coin Changing Problem
Calculate the following sequence of fractions:

How many ways are there to make change for Rs. 100, if you have notes for Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 20, Rs. 50 and Rs. 100.

Some hints and comments.

  • One Rs. 100/- note is also considered to be change.
  • 100 Rs 1 notes is one example of change. So are 5 Rs. 20 notes. List a few before thinking about the problem.
  • The number of ways of making change for Rs. 50 is 293. Use this to check whether your approach works or not.
  • It is usually helpful to gain intuition about how to solve the problem by doing simpler cases. For example, how many ways are there to make change for Rs. N, where N is 1, 2, 3, 4, ...
  • In your solution, you should consider how you can solve related problems. For example, if you have to find change for Rs. 100, but the notes available are just for Rs. 1, 2, and 5. How would you modify your solution to do this problem? What are the answers you get?
Problem B2:
Decipher My Message
In this problem, we consider some ways to hide messages, and also the ways in which they can be rediscovered! The basic way is to jumble up the letters, replacing each by another. Punctuation is not changed. For instance, we replace A by B, B by D, C by X, and so on. The list of replacements is called the key, and can be represented by a table:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
B
D
X
A
W
S
Y
G
R
T
C
L
M
E
U
F
K
N
V
O
P
Z
H
I
J
Q
As an example, if we code the message “Use the key” using this key, we get “Pvw ogw cwj.” This kind of code is called a Substitution cipher.
The simplest kind of key is one in which each letter is shifted to the left by the same number of spaces. For example, if we shift thrice we get the key:

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Such a code is called a Caesar cipher.
Question A: Describe how a Caesar cipher can be decoded methodically. Can your process be implemented on the computer? Decode the following Caesar cipher:

Nlpdlc ntaspcd lcp pldj ez opntaspc

Question B: Suppose you knew a message had been coded using a Substitution cipher. If it took you one second to try out each key, how many days would it take for you to try all possible keys on this message?

Question C: Decode the substitution cipher typed on the next page. You may find it useful to consider questions like the following:

  • Which is the most often used letter in the English alphabet?
  • Which is the most often used two-letter word in the English language?

(Note: The long length of the coded text makes the problem easier! We have also converted all capitals to lower case while doing the coding.)

The text file containing the coded text on the below page can be downloaded from here.
 
Text Coded by a Substitution Cipher:
 
"rke fvn br oksi?" fi vhgin mlsf v niit fvuhf yklqi von v hsukoapr bvugin aiubvo vqqios. "l skpn rke sfvs l mkepn qvpp." fi pkkgin wukb koi sk sfi ksfiu kw eh, vh lw eoqiusvlo mflqf sk vnnuihh.
"tuvr svgi v hivs," hvln fkpbih. "sflh lh br wulion von qkppivaei, nu. mvshko, mfk lh kqqvhlkovppr akkn iokeaf sk fipt bi lo br qvhih. mfkb fvyi l sfi fkokeu sk vnnuihh?"

"rke bvr vnnuihh bi vh sfi qkeos yko guvbb, v ckfiblvo okcpibvo. l eoniuhsvon sfvs sflh aiospibvo, rkeu wulion, lh v bvo kw fkokeu von nlhquislko, mfkb l bvr suehs mlsf v bvssiu kw sfi bkhs ijsuibi lbtkusvoqi. lw oks, l hfkepn beqf tuiwiu sk qkbbeolqvsi
mlsf rke vpkoi."

l ukhi sk ak, ces fkpbih qveafs bi cr sfi mulhs von tehfin bi cvqg losk br qfvlu. "ls lh cksf, ku okoi," hvln fi. "rke bvr hvr ciwkui sflh aiospibvo vorsfloa mflqf rke bvr hvr sk bi."

sfi qkeos hfueaain flh cukvn hfkepniuh. "sfio l behs cialo," hvln fi, "cr clonloa rke cksf sk vchkpesi hiquiqr wku smk rivuh; vs sfi ion kw sfvs slbi sfi bvssiu mlpp ci kw ok lbtkusvoqi. vs tuihios ls lh oks skk beqf sk hvr sfvs ls lh kw heqf milafs ls bvr fvyi vo lowpeioqi etko ieuktivo flhskur."

"l tukblhi," hvln fkpbih.

"von l."

"rke mlpp ijqehi sflh bvhg," qkosloein keu hsuvoai ylhlsku. "sfi veaehs tiuhko mfk ibtpkrh bi mlhfih flh vaios sk ci eogokmo sk rke, von l bvr qkowihh vs koqi sfvs sfi slspi cr mflqf l fvyi dehs qvppin brhipw lh oks ijvqspr br kmo."

"l mvh vmvui kw ls," hvln fkpbih nurpr.

"sfi qluqebhsvoqih vui kw auivs niplqvqr, von iyiur tuiqveslko fvh sk ci svgio sk xeioqf mfvs blafs aukm sk ci vo lbbiohi hqvonvp von hiulkehpr qkbtukblhi koi kw sfi uilaoloa wvblplih kw ieukti. sk htivg tpvlopr, sfi bvssiu lbtplqvsih sfi auivs fkehi kw kubhsilo, fiuinlsvur gloah kw ckfiblv."

"l mvh vphk vmvui kw sfvs," beubeuin fkpbih, hissploa flbhipw nkmo lo flh vubqfvlu von qpkhloa flh irih.

keu ylhlsku apvoqin mlsf hkbi vttvuios heutulhi vs sfi pvoaeln, pkeoaloa wlaeui kw sfi bvo mfk fvn ciio ok nkecs nitlqsin sk flb vh sfi bkhs loqlhlyi uivhkoiu von bkhs ioiuaislq vaios lo ieukti. fkpbih hpkmpr uiktioin flh irih von pkkgin lbtvsliospr vs flh alavoslq qplios.

"lw rkeu bvdihsr mkepn qkonihqion sk hsvsi rkeu qvhi," fi uibvugin, "l hfkepn ci cissiu vcpi sk vnylhi rke."

sfi bvo htuvoa wukb flh qfvlu von tvqin et von nkmo sfi ukkb lo eoqkosukppvcpi valsvslko. sfio, mlsf v aihseui kw nihtiuvslko, fi skui sfi bvhg wukb flh wvqi von feupin ls etko sfi aukeon. "rke
vui ulafs," fi qulin; "l vb sfi gloa. mfr hfkepn l vssibts sk qkoqivp ls?"

 
Phone No: (91-11) 29230401, 65182616 Fax No: (91-11) 29230401
Website :http:// www.mathscifound.org