2002 AMC 10A Problem 11
Jamal wants to save 30 files onto disks, each with 1.44 MB space. 3 of the files take up 0.8 MB, 12 of the files take up 0.7 MB, and the rest take up 0.4 MB. It is not possible to split a file onto 2 different disks. What is the smallest number of disks needed to store all 30 files?
Show solution without answering
Key insight
Give each big file (0.8 or 0.7) 3 points and each small file 2 points. No disk can hold more than 6 points, but the files total 75 points.
Solution
This is a "smallest number" question, so it has two halves: show that disks are enough, then show that are not.
Setting up. There are files of , files of , and files of . Call the and files big ( of them) and the files small ( of them).
1. What fits on one disk ( MB)?
- Two big files: only fits ( is too much), and then there is no room for anything else.
- One big file: it fits with one small file (), but not two ().
- No big files: at most three small files (), since four would be .
Part 1: thirteen disks are enough.
- Put each file with one file: disks. Pair the twelve files: disks. The small files left go three to a disk: disks. That is disks.
Part 2: twelve disks are not enough.
3. Give every big file points and every small file points. Using the list in step 1, the most points a disk can carry is:
- two big files: ,
- one big and one small: ,
- three small: .
So every disk holds at most points.
- The files are worth points in total. Twelve disks carry at most points, which is less than . So disks (or fewer) cannot hold everything.
Thirteen disks work and twelve do not, so the smallest number is .
The answer is .
Why this works
Adding up megabytes gives a lower bound that is too weak, because files cannot be split and space is wasted. Giving each kind of file a score, chosen so that a full disk is worth at most a fixed amount, measures the waste correctly. For any "smallest number needed" question, always do both halves: an arrangement that works, and a reason nothing smaller can.
Alternative approach
Handle the files first. Each one needs its own disk, and the only thing that fits beside it is one file, so use disks for . Left over are twelve files and twelve files, totalling MB. Nine disks hold only MB, so at least more disks are needed, and six disks of plus four disks of three files do it. Total: .
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
There are files of , of , and of . Call the and files "large" ( in all). Check what fits in : two large files fit only if both are (), and then nothing else fits; one large file leaves room for at most one ( is too much); a disk with no large file holds at most three files ().
Suppose disks were enough. Let be the numbers of disks holding two, one, or zero large files. Then and , so and . Those disks can hold at most small files, and forces , so at most small files fit. Contradiction: disks fail.
Thirteen disks work: three disks each with , six disks each with , and four disks each with three files. That stores files.
The answer is .
Review in the AoPS books
- Intermediate Counting & Probability, Chapter 2: Sets and Logic (§2.2, §2.3)
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Prealgebra, Chapter 7: Ratios, Conversions, and Rates (§7.4)
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site. Also appeared as 2002 12A #9.