Magic Square Part – 2

আগের পর্ব ঃ part – 1

জোড় সংখ্যক গ্রিডের ম্যাজিক স্কয়ার সমাধান ( Solving Even-Numbered Magic Square )

প্রথমে আমরা সহজভাবে দেখি। আমরা এখন যেটি দেখবো সেটি হল ডাবল-জোড় সংখ্যক গ্রিড এর জন্য। ডাবল-জোড় কি? ( Doubly Even ) ডাবল-জোড় হল, যে জোড় গ্রিড ভাঙলে আবার জোড় গ্রিড পাওয়া যায়। যেমন ঃ ৪, ৮, ১৬… আবার, ৬, ১২, ১৪… এসব হবে সিঙ্গেল-জোড় গ্রিড এর মেথড এ। আমরা পরে আলোচনা করবো এটি নিয়ে। আপাতত ডাবল-জোড় দেখি।

প্রথমেই আমরা ম্যাজিক কন্সটেন্ট বের করি। ধরি গ্রিড 4×4,
সুতরাং, [  4 * ( 42 + 1 ) ] / 2 = [ 4 * 17 ] / 2 = 34

প্রথম ধাপ ঃ গ্রিড এর ৪ টি কোনাতে আমরা N/4 সাইজের ঘর মার্ক করে রাখবো।
4×4 এর জন্য মার্ক করা ঘরের সাইজ ঃ 1×1
8×8 এর জন্য মার্ক করা ঘরের সাইজ ঃ 2×2
12×12 এর জন্য মার্ক করা ঘরের সাইজ ঃ 3×3
1.JPGদ্বিতীয় ধাপঃ এবার আমরা মাঝাখানের ঘরগুলি, যেগুলি চার কোনার সাথে কানেক্টেড আছে, তাদের মার্ক করবো এভাবে ঃ 1.JPG
তৃতীয় ধাপঃ এবার আমরা মার্ক করা ঘরগুলিতে সংখ্যা বসাতে থাকবো। যে যেই ঘরে বসবে ( ১ থেকে শুরু করে ) তাকে সেই ঘরে বসিয়ে দিবো এভাবে ঃ
1চতুর্থ ধাপঃ এবার আমরা যেসব ঘর মার্ক করা নেই, সেগুলোতে বাকি সংখ্যাগুলি বসিয়ে দিবো রিভার্স অর্ডার এঃ
1.JPG
আমরা হিসাব করে দেখবো যে, সকল সারি, কলাম, কর্ণ বরাবর যোগফল ৩৪ হচ্ছে ( ম্যাজিক কন্সটেন্ট )।
একটি ৮x৮ এর জন্য দেখা যাক –>
1.JPG এখানে ম্যাজিক কন্সটেন্ট ঃ ২৬০

এবার আমরা দেখবো সিঙ্গেল-জোড় সংখ্যার জন্য। ( Single-Even ) সিঙ্গেল-জোড় হল এমন সংখ্যার গ্রিড যা ২ দিয়ে বিভাজ্য কিন্তু ৪ দিয়ে নয়। প্রথম সিংগেল-জোড় হল ৬x৬, কারন ২x২ ম্যাজিক স্কয়ার সম্ভব নয়।আমরা এখন এরকম গ্রিড এর জন্য দেখবো কিভাবে মানগুলি বসাতে হবে।
ম্যাজিক কন্সটেন্ট, c = [  6*( 6*6+1 ) ] / 2 = 222/2 = 111
1
প্রথমে আমরা ৬x৬ গ্রিড টিকে এভাবে চারভাগে চাগ করবো। এবার আমরা এই চার ব্লকে আমাদের নাম্বারগুলি বসাবো এভাবেঃ A ব্লকের রেঞ্জ হবে ১-৯, B ব্লকের রেঞ্জ হবে ১৯-২৭, C হবে ২৮-৩৬ এবং D হবে ১০-১৮। এরপরে আমরা ৩x৩ যেভাবে সল্ভ করেছি, সেইভাবে মানগুলি বসাবো।
1.JPG
এবার আমরা প্রতি ব্লকের জন্য মানগুলি বসাবো। প্রতি ব্লকের ১, ১০, ১৯, ২৭ এগুলোকে ১ ধরে আমরা আমাদের ৩x৩ ম্যাজিক স্কয়ার কমপ্লিট করবো। মান বসানোর সময় আমরা শুধুমাত্র ৩x৩ গ্রিডই বিবেচনা করবো।
1.JPG
আমাদের কাজ এখনও শেষ হয়নি। সিঙ্গেল-জোড় এর ক্ষেত্রে এই পার্টটি গুরুত্বপুর্ণ। আমরা কয়েকটি ঘর মার্ক করবো এবং কিছু ঘরের সাথে এক্সচেঞ্জ করবো এভাবেঃ
1.JPG
মার্ক করা ঘরগুলি আমরা এক্সচেঞ্জ করবো, তাহলেই আমাদের কাজ শেষ।
1.JPGএভাবে সবসময়, A এবং C ব্লকের মাঝে এক্সচেঞ্জ করতে হবে।
৬ এর থেকে বড় গ্রিড এর জন্য আমাদের A,C ছাড়াও B,D এর মাঝেও এক্সট্রা এক্সচেঞ্জ করতে হবে সেইম ১-১ মেথড এ, নিচের ছবিটি দেখলে আশা করি বুঝা যাবে ঃ
1.JPG
১৪x১৪ ঃ এক্সচেঞ্জ এর আগে।

2.JPG
১৪x১৪ ঃ এক্সচেঞ্জ এর পরে।

এবার একটি মজার ট্রিক ঃ magic square trick

Magic Square Part – 1

ম্যাজিক স্কয়ার কি? ( What is Magic Square? )

একটি  N x N ২ডি গ্রিড এ 1 থেকে N পর্যন্ত সংখাগুলোকে প্রতিটি কেবলমাত্র একবার ব্যবহার করে এমনভাবে সাজাতে হবে, যাতে ঐ গ্রিড এর প্রতিটি সারি, কলাম এবং কর্ণ গুলির যোগফল সমান হয়। এখন এরকম অনেকরকম সাজানো যেতে পারে, আমাদের এমন একটি স্টেট বের করতে হবে, যেটায় এই যোগফল সবচেয়ে কম হয়।

ম্যাজিক কন্সটেন্ট ( Magic Constant )

ম্যাজিক কন্সটেন্ট হল সেই সর্বনিম্ন সংখ্যা যেটা আমাদের গ্রিড এর জন্য বের করতে হবে। এখন গ্রিড N x N হলে,
ম্যাজিক কন্সটেন্ট, c = N * [ ( N2 + 1 ) / 2 ]
সুতরাং, N = 3 হলে, c = 3 * [  ( 9 + 1 ) / 2 ] = 3 * [ 10 / 2 ] = 3 * 5 = 15
কাজেই সব সারি, কলাম, কর্ণ এর যোগফল অবশ্যই ১৫ হতে হবে।

বেজোড় সংখ্যক গ্রিডের ম্যাজিক স্কয়ার সমাধান ( Solving Odd-Numbered Magic Square )

 প্রথম ধাপ ঃ গ্রিড এর প্রথম সারির একদম মাঝের কলামে ১ বসাই।

1
আমরা একটি 3 x 3 গ্রিড এর জন্য করবো। 7 x 7 এর জন্য 4th কলামে আমরা 1 বসাবো, এরকমভাবে।
বেজোড় সারি-কলামের ক্ষেত্রে আমরা সবসময় এভাবে শুরু করবো।
দ্বিতীয় ধাপঃ আমরা সবসময় sequencially ১ থেকে n পর্যন্ত বসাবো। এখন, ১ বসানোর পরে আমরা একবার কলাম, একবার সারি, এভাবে ধাপে ধাপে সিরিয়ালি বসাবো। নিচের উদাহরন দেখলে বিষয়টা বুঝা যাবেঃ
2
২ আমরা এভাবে বসাবো। ১ এর ঠিক পরের কলাম এবং সবার শেষের সারিতে ২ বসবে। এরপরে আমরা বাকি সংখ্যাগুলি ২ এর পরের কলাম, এবং আগের সারিতে, এভাবে বসাবো। অর্থাৎ আমরা নিচ থেকে উপরে উঠবো। এখন কথা হচ্ছে, ২ এর পরে আর কলাম নেই, এটা একটি ব্যাতিক্রম। এরকম ৩ ধরনের ক্ষেত্র আছে, যেগুলি একটু খেয়াল করলে আমরা সহজে হ্যান্ডেল করতে পারবো।
প্রথম ব্যাতিক্রমঃ আমরা এখন হিসাব অনুযায়ী ৩ নং কলাম এবং ২ নং সারিতে যাবো। কিন্তু আমাদের এটি গ্রিড এর বাইরে, কাজেই আমাদের ঐ সারিতে থাকবো ঠিকই, কিন্তু ডান দিকে না গিয়ে আমরা একদম সবচেয়ে বামদিকের ঘরে বসাবো।
3

ছবি দেখে আমরা বুঝতে পারবো ব্যাপারটা। ৩ এর জন্য ঘর গ্রিড এ নাই, কাজেই আমরা ২ নং সারিতে থাকবো ঠিকই, কিন্তু, একদম বামে চলে যাবো, আসলে ব্যাপারটা ঠিক বামে না, আমাদের যে দিকে যাবার কথা, তার বিপরীত দিকে যাবো। কাজেই কলাম ১ এ চলে আসলাম।
দ্বিতীয় ব্যাতিক্রমঃ
এখন আমাদের ৪ বসানোর জন্য আবার ঝামেলায় পরে গেলাম। আমাদের উপরের সারিতে এবং পরের কলামে যাওয়ার কথা, কিন্তু সেখানে আগে থেকেই ১ আমরা লিখে রেখেছি। এরকম অবস্থা হলে সেটি হল দ্বিতীয় ব্যাতিক্রম। এজন্য আমরা যেখানে বর্তমানে আছি, তার ঠিক নিচের সারিতে পরের মান বসাবো, এক্ষেত্রে কলাম একই থাকবে। অর্থাৎ ৪ কে আমরা ৩ এর নিচে বসাবো এভাবে ঃ
4.JPG
এখন আমরা দেখতে পাচ্ছি আমাদের মূল যেভাবে বসানোর কথা ছিল, আমরা সেরকম পথ পেয়ে গেছি 😀 । কাজেই আমরা ৪ থেকে উপরের সারি, পরের কলাম, এভাবে বাকি সংখ্যাগুলি বসাতে থাকবো যতক্ষন কোন ব্যাতিক্রম না পাই। অর্থাৎ ঃ
5এখন আমরা ৭ বসানোর জন্য দেখি যে একটি ব্যাতিক্রম হয়ে গেছে। হিসাব অনুযায়ী গ্রিডের বাইরে চলে যায়, এখন আমাদের এটা ১ নং ব্যাতিক্রমের মধ্যে পরে, কিন্তু যেহেতু, ৬ এর নিচে খালি একটি ঘর আছে, কাজেই, এটি আসলে ২ নং ব্যাতিক্রম। তাই আমরা ৬ এর ঠিক নিচে ৭ কে বসাবো এভাবে ঃ
6.JPG

এখন আমরা খেয়াল করলে দেখবো এখানে আসলে ১ নং ব্যাতিক্রমটি হয়েছে, কারন ৭ এর নিচে ঘর ফাঁকা নেই, আবার গ্রিড এর বাইরেও চলে যাচ্ছে। তাই আমরা উপরের সারির সবচেয়ে বামদিকে পরের সংখ্যাকে বসাবো এভাবে ঃ
7.JPG

তৃতীয় ব্যাতিক্রমঃ এখন আমরা আসি ৩ নং ব্যাতিক্রম এ। এটি আসলে এমনিতেই বুঝা যায়, আমাদের হিসাবে এখন যাওয়ার কথা উপরে, কিন্তু গ্রিড এর বাইরে হওয়াতে আমরা দেখবো ৮ এর নিচে ফাঁকা ঘর আছে কিনা, ফাঁকা নেই, কাজেই হিসাব মত আমাদের সবচেয়ে বামের ঘরে ব্যাতিক্রম ১ অনুযায়ী মান বসানোর কথা, কিন্তু এটিও গ্রিড এর বাইরে  -_- । এটিই আমাদের ৩নং ব্যাতিক্রম। এক্ষেত্রে আমাদের ঠিক পরের কলামের নিচ থেকে যে ঘর ফাঁকা পাবো, সেখানে মান বসায়ে দিবো।
Capture.JPG

সারি, কলাম, কর্ণ সকল ক্ষেত্রে যোগফল ১৫ এসেছে, কাজেই আমাদের উদ্দেশ্য সফল। এভাবে আমরা যেকোন বেজোর সংখ্যক গ্রিড এর জন্য ম্যাজিক স্কয়ার বানাতে পারবো।
 ** ৭ এর জন্য আমরা একটি ম্যাজিক স্কয়ার দেখি ঃ
এক্ষেত্রে ম্যাজিক কন্সটেন্ট, c = 175
9.JPG
আমরা ঠিক 3×3 এর মত করে 7×7 গ্রিডটি সাজালাম। এখন সারি, কলাম, কর্ণ সব যোগ করে আমরা ১৭৫ পাবো 🙂
ইটারেশন গুলিতে বুঝতে সমস্যা হলে, হাতে কলমে এভাবে একটি করলেই আশা করি সবাই বুঝে যাবে।

এখন আমাদের লাগবে জোড় সংখ্যক গ্রিডের জন্য সমাধান। আমাদের প্রথমে ১ টি জিনিস দেখা লাগবে আগে, আমরা প্রথমে দেখবো যে গ্রিডটি কে ভাঙলে যে গ্রিড পাওয়া যায়, সেগুলি জোড় নাকি বেজোড়। ২ টির ভিন্নতার কারনে ভিন্ন ভিন্ন মান আসবে। আমরা ২ টির জন্যই দেখবো এখানে ঃ part – 2

40 Mathematics Quotes

গনিতবিদ, দার্শনিকরা গনিত এর বিভিন্ন বিষয় নিজেরা যেভাবে চিন্তা করতেন, সেভাবে তারা গনিত নিয়ে কিছু কথা বলে
গেছেন।এখানে এরকম ৪০ টি উক্তি দেয়া হল, যা টাইম অফ ইউক্লিড ( Time of Euclid ) ্থেকে সংগ্রীহিত।

1. Mathematics is the door and key to the sciences. — Roger Bacon

2. Mathematics – the unshaken Foundation of Sciences, and the plentiful Fountain of Advantage to human affairs.  — Isaac Barrow

3. Mathematics is the art of giving the same name to different things.– Henri Poincaré

4. Mathematics is like checkers in being suitable for the young, not too difficult, amusing, and without peril to the state. — Plato

5. Mathematics is not a careful march down a well-cleared highway, but a journey into a strange wilderness, where the explorers often get lost. Rigour should be a signal to the historian that the maps have been made, and the real explorers have gone elsewhere. –– W. S. A

6. Mathematics is not only real, but it is the only reality. — Martin Gardner

7. Mathematics Is an Edifice, Not a Toolbox

8. Mathematics serves as a handmaiden for the explanation of the quantitative situations in other subjects, such as economics. – H. F. Fehr

9. Mathematics is a hard thing to love. It has the unfortunate habit, like a rude dog, of turning its most unfavourable side towards you when you first make contact with it. — David Whiteland

10. Mathematics makes a nice distinction between the usually synonymous terms “elementary” and “simple”, with “elementary” taken to mean that not very much mathematical knowledge is needed to read the work and “simple” to mean that not very much mathematical ability is needed to understand it. – Julian Havel

11. Mathematics is concerned with “all possible worlds. — D.M. Armstrong

12. But mathematics is the sister, as well as the servant, of the arts and is touched by the same madness and genius. — Marston Morse

13. Mathematics, however, is, as it were, its own explanation; this, although it may seem hard to accept, is nevertheless true, for the recognition that a fact is so is the cause upon which we base the proof. — Girolamo Cardano

14.   . . mathematics is not just another language . . . it is a language plus logic. Mathematics is a tool for reasoning. — Richard Feynman

15. Mathematics is pure language – the language of science. It is unique among languages in its ability to provide precise expression for every thought or concept that can be formulated in its terms. — A Adler.

16. Mathematics compares the most diverse phenomena and discovers the secret analogies that unite them. — Joseph Fourier

17. Mathematics is an independent world created out of pure intelligence.  — William Woods Worth

18. Mathematics is the science which uses easy words for hard ideas. — Edward Kasner and James R. Newman

19. Mathematics is a body of knowledge, but it contains no truths.  — Morris Kline

20. Mathematics is the science which draws necessary conclusions. — Benjamin Pierce

21. Mathematics is the queen of science. — Carl Friedrich Gauss

22. Mathematics is no more computation than typing is literature.– John Allen Paulos

23. Mathematics, as much as music or any other art, is one of the means by which we rise to a complete self-consciousness. The significance of mathematics resides precisely in the fact that it is an art; by informing us of the nature of our own minds it informs us of much that depends on our minds.– John William Navin Sullivan

24. Mathematics is the science of what is clear by itself. — Carl Jacobi

25. Mathematics is a game played according to certain rules with meaningless marks on paper. — David Hilbert

26. Mathematics is as much an aspect of culture as it is a collection of algorithms. —  Carl Boyer

27. Mathematics is the supreme judge; from its decisions there is no appeal.–Tobias Dantzig

28. Mathematics is the language with which God wrote the universe. — Galileo

29. Mathematics is a great motivator for all humans.. Because its career starts with zero and it never end (infinity).

30. Mathematics is often erroneously referred to as the science of common sense. — Newman & Kasner

31. Mathematics is the cheapest science. Unlike physics or chemistry, it does not require any expensive equipment. All one needs for mathematics is a pencil and paper.

32. Mathematics is, as it were, a sensuous logic, and relates to philosophy as do the arts, music, and plastic art to poetry. —  K. Shegel

33. Mathematics is a more powerful instrument of knowledge than any other that has been bequeathed to us by human agency.  — Descartes

34. Mathematics is an art of human understanding. — William Thurston

35. Mathematics is not a contemplative but a creative subject; no one can draw much consolation from it when he has lost the power or the desire to create; and that is apt to happen to a mathematician rather soon. It is a pity, but in that case he does not matter a great deal anyhow, and it would be silly to bother about him. — G.H. Hardy

36. Mathematics is on the artistic side a creation of new rhythms, orders, designs, harmonies, and on the knowledge side, is a systematic study of various rhythms, orders.– William L. Schaaf 

37. Mathematics is the science of definiteness, the necessary vocabulary of those who know. — W. J. White

38. Mathematics is not a book confined within a cover and bound between brazen clasps, whose contents it needs only patience to ransack; it is not a mine, whose treasures may take long to reduce into possession, but which fill only a limited number of veins and lodes; it is not a soil, whose fertility can be exhausted by the yield of successive harvests; it is not a continent or an ocean, whose area can be mapped out and its contour defined: it is limitless as that space which it finds too narrow for its aspirations; its possibilities are as infinite as the worlds which are forever crowding in and multiplying upon the astronomer’s gaze. — J. Sylvester

39. Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. — Bertrand Russell

40. Mathematics is concerned only with the enumeration and comparison of relations. — Carl Friedrich Gauss

Sources: Brainy Quote, Oklahom State U Website, Peter Cameron’s Blog, David Pleacher’s Website, Quote Garden

 

UVA 11254 : Consecutive Integers

Prob link : UVA 11254: Consecutive Integers

Problem টায় বলা হয়েছে আমাকে একটা integer দেয়া হবে, আমাকে ঐ integer টি আরো কতোগুলি consecutive integer এর summation এর মাধ্যমে বানানো যায় তা print করতে হবে।
Suppose 15 কে আমরা লিখতে পারি এভাবে ——>
15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
15 = 15

দেখা যাচ্ছে যে এর মধ্যে প্রথম টির integer সংখ্যা বেশি, তাই আমাকে প্রথম টি ই print করা লাগবে।print করার জন্যে question এ যে format এর কথা বলা হয়েছে, সে অনুযায়ী print করলে আমাদের output হবে এরকম  :::
15 = 1 + … + 5  ( অর্থাৎ আমাকে consecutive integers এর  first এবং last integer টা print করতে হবে )
যদি এমন integer হয়, যাকে কোন consecutive integer এর summation এ ফেলা যায় না, তখন কেবল ঐ integer টাই print হবে।
Ex : For N = 8  ans   ===   8 = 8 + … + 8

Solve Technique :

আমরা sum of arithmetic progression সম্পর্কে নিশ্চই জানি।
যদি n তম integer পর্যন্ত summation বের করতে হয়, তাহলে সূত্র ঃ sum, Sn ( n terms ) = n / 2 + [ 2 * a + ( n – 1 ) * d ]
যেখানে , a = first term , n = last term , d = interval between numbers .
আমরা এই সূত্র ব্যবহার করে আমাদের উত্তর বের করবো।
যেহেতু আমাদের বলা আছে , consecutive integers, so আমাদের d এর মান হবে  one  ( 1 ) .
এখন আমাদের n জানা আছে, আমরা চাইলে brute force করে করতে পারি,  কিন্তু আমাদের range টাকে ( 10 ^ 9 ) মাথায় রাখতে হবে।
এতবড় জিনিস বারবার loop চালায়ে করলে TLE  ( Time Limit Exceeded ) খাওয়ার সম্ভাবনা অনেক বেশি, তাই আমরা আমাদের সূত্র ব্যবহার করে একটা ফরমুলা বানানোর চেষ্টা করবো যাতে আমাদের brute force এর time complexity কম হয়।
সূত্র টাকে আরেকভাবে লিখা যাক,  a = ( 2 * Sn + n – n * n ) / ( 2 * n )

হিসাবের সুবিধার জন্য আমরা এভাবে লিখলাম, এখন খেয়াল করে দেখো আমাদের জানা মান হল Sn , যা qs এ দেয়া থাকবে, আমাদের বের করতে হবে a এবং n । আমরা ২ টা কাজ করতে পারি, প্রতি a  এর জন্য লুপ চালায়ে n বের করতে পারি, অথবা উলটা কাজটাও করতে পারি।

এখন কথা হল লুপ চালাবো কতক্ষন ?

equation খেয়াল করলে দেখা যায় আমাদের R.H.S এ আছে 2 * Sn , আমরা square root of 2 * Sn থেকে 1 পর্যন্ত integer এর উপর লুপ চালায়ে n  এর মান বের করতে পারি এবং n  এর মান আমরা equation এ বসায়ে  a এর মান এর validity check করতে পারি।যখন ই আমরা valid একটা মান পাবো তখন আমাদের result এর a হবে equation থেকে প্রাপ্ত মান এবং n হবে   a + ( যেই মান এর জন্য আমরা valid a পেলাম সেই মান) – 1 ।

Qs 1 : Why sqrt ( 2 * Sn )  ?

Ans :
equation থেকে এটা easily observe করা যায়, n * n এই value টার আগে minus sign আছে, কাজেই, আমার  n এর মান sqrt ( 2 * Sn ) এর বেশি হলে negative integer আসবে , যা আসলে ভুল result দিবে।

Qs 2 : a এর validity check করবো কিভাবে ?

Ans : আমরা a = ( 2 * Sn + n – n * n ) / ( 2 * n )  এই সূত্র টা কাজে লাগাবো, sqrt ( 2 * Sn ) থেকে 1 পর্যন্ত লুপ চালায়ে আমরা প্রতি n এর জন্য  a এর মান এর validity দেখবো। a valid হবে তখনই যখন আমার equation এ n এবং Sn বসালে তা সত্য হবে।

a = ( 2 * Sn + n – n * n )  এটা থেকে আমরা একটা মান পাবো, এখন কখন এই মানটা সত্য? যখন a কে  ( 2 * n ) দিয়ে মড করলে মান শুন্য আসবে, কেবলমাত্র তখনই আমরা a এর একটা integer value পাবো এবং value টা হবে ( 2 * Sn + n – n * n ) / ( 2 * n ).

আশা করি এখন code লিখতে কোন সমস্যা হবার কথা না। code embed করে দিলাম, কিন্তু, suggestion রইল যাতে আগে সবাই নিজে চেষ্টা করে দেখবে। ধন্যবাদ।

Solution