Question and Answers Forum

All Questions      Topic List

Algebra Questions

Previous in All Question      Next in All Question      

Previous in Algebra      Next in Algebra      

Question Number 22082 by Tinkutara last updated on 10/Oct/17

If A is a fifty-element subset of the set {1, 2, 3, ...., 100} such that no two numbers from A add up to 100 show that A contains a square.

$$\mathrm{If}\:{A}\:\mathrm{is}\:\mathrm{a}\:\mathrm{fifty}-\mathrm{element}\:\mathrm{subset}\:\mathrm{of}\:\mathrm{the}\:\mathrm{set} \\ $$$$\left\{\mathrm{1},\:\mathrm{2},\:\mathrm{3},\:....,\:\mathrm{100}\right\}\:\mathrm{such}\:\mathrm{that}\:\mathrm{no}\:\mathrm{two} \\ $$$$\mathrm{numbers}\:\mathrm{from}\:{A}\:\mathrm{add}\:\mathrm{up}\:\mathrm{to}\:\mathrm{100}\:\mathrm{show} \\ $$$$\mathrm{that}\:{A}\:\mathrm{contains}\:\mathrm{a}\:\mathrm{square}. \\ $$

Answered by Rasheed.Sindhi last updated on 14/Oct/17

The subset of {1,2,...,100}, (i)which doesn′t contain perfect square and (ii)whose no two elements add up to 100 has at most 49 elements and are as follows. All the possible sets having at most elements are given here.(Note thatby notation a∣b here is meant ′one of a or b′): {99^(1) ,2∣98^(2) ,3∣97^(3) ,96^(4) ,5∣95^(5) ,6∣94^(6) ,7∣93^(7) , 8∣92^(8) ,91^(9) ,10∣90^(10) ,11∣89^(11) ,12∣88^(12) ,13∣87^(13) 14∣8^(14) ,15∣85^(15) ,84^(16) ,17∣83^(17) ,18∣82^(18) ,19^(19) , 20∣80^(20) ,21∣79^(21) ,22∣78^(22) ,23∣77^(23) ,24∣76^(24) , 75^(25) ,26∣74^(26) ,27∣73^(27) ,28∣72^(28) ,29∣71^(29) , 30∣70^(30) ,31∣69^(31) ,32∣68^(32) ,33∣67^(33) ,34∣66^(34) , 35∣65^(35) ,37∣63^(36) ,38∣62^(37) ,39∣61^(38) ,40∣60^(39) , 41∣59^(40) ,42∣58^(41) ,43∣57^(42) ,44∣56^(43) ,45∣55^(44) , 46∣54^(45) ,47∣53^(46) ,48∣52^(47) ,51^(48) ,50^(49) } ∴ 50th number must be perfect square.

$$\mathrm{The}\:\mathrm{subset}\:\mathrm{of}\:\left\{\mathrm{1},\mathrm{2},...,\mathrm{100}\right\}, \\ $$$$\left(\mathrm{i}\right)\mathrm{which}\:\mathrm{doesn}'\mathrm{t}\:\mathrm{contain}\:\mathrm{perfect} \\ $$$$\:\:\:\:\:\mathrm{square} \\ $$$$\mathrm{and} \\ $$$$\left(\mathrm{ii}\right)\mathrm{whose}\:\mathrm{no}\:\mathrm{two}\:\mathrm{elements}\:\mathrm{add} \\ $$$$\:\:\:\:\:\:\:\:\mathrm{up}\:\mathrm{to}\:\mathrm{100} \\ $$$$\mathrm{has}\:\mathrm{at}\:\mathrm{most}\:\mathrm{49}\:\mathrm{elements}\:\mathrm{and}\:\mathrm{are} \\ $$$$\mathrm{as}\:\mathrm{follows}.\:\mathrm{All}\:\mathrm{the}\:\mathrm{possible}\: \\ $$$$\mathrm{sets}\:\mathrm{having}\:\mathrm{at}\:\mathrm{most}\:\mathrm{elements} \\ $$$$\mathrm{are}\:\mathrm{given}\:\mathrm{here}.\left(\mathrm{Note}\:\mathrm{thatby}\:\right. \\ $$$$\mathrm{notation}\:\mathrm{a}\mid\mathrm{b}\:\mathrm{here}\:\mathrm{is}\:\mathrm{meant}\: \\ $$$$\left.'\mathrm{one}\:\mathrm{of}\:\mathrm{a}\:\mathrm{or}\:\mathrm{b}'\right): \\ $$$$\left\{\overset{\mathrm{1}} {\mathrm{99}}\overset{\mathrm{2}} {,\mathrm{2}\mid\mathrm{98}}\overset{\mathrm{3}} {,\mathrm{3}\mid\mathrm{97}},\overset{\mathrm{4}} {\mathrm{96}}\overset{\mathrm{5}} {,\mathrm{5}\mid\mathrm{95}}\overset{\mathrm{6}} {,\mathrm{6}\mid\mathrm{94}}\overset{\mathrm{7}} {,\mathrm{7}\mid\mathrm{93}},\right. \\ $$$$\:\overset{\mathrm{8}} {\:\mathrm{8}\mid\mathrm{92}},\overset{\mathrm{9}} {\mathrm{91}},\overset{\mathrm{10}} {\mathrm{10}\mid\mathrm{90}},\overset{\mathrm{11}} {\mathrm{11}\mid\mathrm{89}},\overset{\mathrm{12}} {\mathrm{12}\mid\mathrm{88}},\overset{\mathrm{13}} {\mathrm{13}\mid\mathrm{87}} \\ $$$$\:\:\overset{\mathrm{14}} {\mathrm{14}\mid\mathrm{8}},\overset{\mathrm{15}} {\mathrm{15}\mid\mathrm{85}},\overset{\mathrm{16}} {\mathrm{84}},\overset{\mathrm{17}} {\mathrm{17}\mid\mathrm{83}},\overset{\mathrm{18}} {\mathrm{18}\mid\mathrm{82}},\overset{\mathrm{19}} {\mathrm{19}}, \\ $$$$\:\:\overset{\mathrm{20}} {\mathrm{20}\mid\mathrm{80}},\overset{\mathrm{21}} {\mathrm{21}\mid\mathrm{79}},\overset{\mathrm{22}} {\mathrm{22}\mid\mathrm{78}},\overset{\mathrm{23}} {\mathrm{23}\mid\mathrm{77}},\overset{\mathrm{24}} {\mathrm{24}\mid\mathrm{76}}, \\ $$$$\:\:\overset{\mathrm{25}} {\mathrm{75}},\overset{\mathrm{26}} {\mathrm{26}\mid\mathrm{74}},\overset{\mathrm{27}} {\mathrm{27}\mid\mathrm{73}},\overset{\mathrm{28}} {\mathrm{28}\mid\mathrm{72}},\overset{\mathrm{29}} {\mathrm{29}\mid\mathrm{71}}, \\ $$$$\:\:\overset{\mathrm{30}} {\mathrm{30}\mid\mathrm{70}},\overset{\mathrm{31}} {\mathrm{31}\mid\mathrm{69}},\overset{\mathrm{32}} {\mathrm{32}\mid\mathrm{68}},\overset{\mathrm{33}} {\mathrm{33}\mid\mathrm{67}},\overset{\mathrm{34}} {\mathrm{34}\mid\mathrm{66}}, \\ $$$$\:\:\overset{\mathrm{35}} {\mathrm{35}\mid\mathrm{65}},\overset{\mathrm{36}} {\mathrm{37}\mid\mathrm{63}},\overset{\mathrm{37}} {\mathrm{38}\mid\mathrm{62}},\overset{\mathrm{38}} {\mathrm{39}\mid\mathrm{61}},\overset{\mathrm{39}} {\mathrm{40}\mid\mathrm{60}}, \\ $$$$\:\:\overset{\mathrm{40}} {\mathrm{41}\mid\mathrm{59}},\overset{\mathrm{41}} {\mathrm{42}\mid\mathrm{58}},\overset{\mathrm{42}} {\mathrm{43}\mid\mathrm{57}},\overset{\mathrm{43}} {\mathrm{44}\mid\mathrm{56}},\overset{\mathrm{44}} {\mathrm{45}\mid\mathrm{55}}, \\ $$$$\left.\:\:\overset{\mathrm{45}} {\mathrm{46}\mid\mathrm{54}},\overset{\mathrm{46}} {\mathrm{47}\mid\mathrm{53}},\overset{\mathrm{47}} {\mathrm{48}\mid\mathrm{52}},\overset{\mathrm{48}} {\mathrm{51}},\overset{\mathrm{49}} {\mathrm{50}}\right\} \\ $$$$\therefore\:\mathrm{50th}\:\mathrm{number}\:\mathrm{must}\:\mathrm{be}\:\mathrm{perfect} \\ $$$$\mathrm{square}. \\ $$

Commented by Tinkutara last updated on 14/Oct/17

Thank you very much Sir!

$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{very}\:\mathrm{much}\:\mathrm{Sir}! \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com