HMMT 二月 2005 · 冲刺赛 · 第 10 题

HMMT February 2005 — Guts Round — Problem 10

[7] You are given a set of cards labeled from 1 to 100. You wish to make piles of three cards such that in any pile, the number on one of the cards is the product of the numbers on the other two cards. However, no card can be in more than one pile. What is the maximum number of piles you can form at once?

解析

You are given a set of cards labeled from 1 to 100. You wish to make piles of three cards such that in any pile, the number on one of the cards is the product of the numbers on the other two cards. However, no card can be in more than one pile. What is the maximum number of piles you can form at once? Solution: 8 Certainly, the two factors in any pile cannot both be at least 10, since then the product would be at least 10 × 11 > 100. Also, the number 1 can not appear in any pile, since then the other two cards in the pile would have to be the same. So each pile must use 3 one of the numbers 2 , 3 , . . . , 9 as one of the factors, meaning we have at most 8 piles. Conversely, it is easy to construct a set of 8 such piles, for example: { 9 , 11 , 99 } { 8 , 12 , 96 } { 7 , 13 , 91 } { 6 , 14 , 84 } { 5 , 15 , 75 } { 4 , 16 , 64 } { 3 , 17 , 51 } { 2 , 18 , 36 }