لغز العدد الضائع!

بدأه Khaled.Alshaya في 18 أغسطس 2010 · 26 رد · 7,131 مشاهدة · في الرياضيات والخوارزميات

#118 أغسطس 2010 في 21:26 صاحب الموضوع

السلام عليكم و رحمة الله و بركاته....

تصور أن لدينا متتابعة على الشكل التالي:

n, n+1, n+2, ..., n+i

و قام أحد الأشخاص بنزع عدد من تلك المتتابعة, ثم قام ببعثرة الأرقام فأصبح ترتيبها عشوائياً عند إدخالها لبرنامجك. هل تستطيع معرفة العدد الذي تم نزعه من المتتابعة المدخلة للبرنامج؟

ملاحظات لتسهيل كتابة الخوارزمية:

أولاً, افترض أن الأعداد المدخلة لا تقل عن عددين. فليس هناك داع للتحقق من وجود عددين فأكثر.

ثانياً, افترض أن أطراف المتتابعة لم يتم المساس بها, بالتالي فإن العنصرين n و n+i دائماً حاضران ضمن مدخلات الخوارزمية.

ثالثاً, و هذه الملاحظة تتبع من الملاحظة الثانية, أن العدد الضائع أو لنقل العدد الذي تم نزعه هو عدد من منتصف المتتابعة. بالتالي لو سميناه n+k فإن k لابد أن تحقق الشرط التالي:

0 < k < i

رابعاً, ليس مطلوباً منك التحقق من كون المدخل لبرنامج صحيح أم لا, و افترض أنك تحصل دائماً على مدخلات صالحة للخوارزمية بقصد تبسط كتابة البرنامج لا أكثر. و هذا يعني أن الأعداد المدخلة عبارة عن أعداد موجبة دائماً.

ما يلي عبارة عن أمثلة على مدخلات البرنامج و مخرجاته(العدد الضائع)...

Example 1:

Input:  1 3
Ouput:  2


Example 2:

Input:  3 1
Ouput:  2


Example 3:

Input:  9 6 7 5 2 3 1 8
Ouput:  4


Example 4:

Input:  99 96 91 95 93 98 89 97 92 94 100
Ouput:  90

ما هي أفضل خوارزمية تستطيع الوصول إليها لحل هذا السؤال؟ بمجرد كتابتك للبرنامج ضعه في الموضوع, و بعد أن نصل إلى عدد جيد من الإجابات سنقوم بمناقشتها و طرح أفضل خوارزمية لحل السؤال.

تحياتي :)

تم تعديل هذه المشاركة بواسطة Khaled.Alshaya في 18 أغسطس 2010 في 21:28

Follow me on bitbucket

#218 أغسطس 2010 في 23:01

وعليك السلام ورحمة الله وبركاته

لست متأكداً أنها الخوارزمية الأفضل ... لكنها جيدة بما فيه الكفاية ... كما أنها تعمل ! :D

كود جافا:

public class LostNum {

    public static void main(String[] args) {
        int input[] = {3, 5, 4, 8, 9, 2, 1, 6, 0};
        System.out.println("The Lost number is: " + findLostNum(input));
    }

    static int findLostNum(int input[]) {
        // Sorting
        for (int i = 0; i < input.length; i++) {
            for (int j = i + 1; j < input.length; j++) {
                if (input > input[j]) {
                    int tmp = input[j];
                    input[j] = input;
                    input = tmp;
                }
            }
        }

        // Finding The Lost Number
        int lastNum = input[0];
        for (int i = 1; i < input.length; i++) {
            if (lastNum + 1 != input) {
                return (lastNum + 1);
            }
            lastNum = input;
        }
        return -1; // Not found !
    }
}

تم تعديل هذه المشاركة بواسطة Speed_Of_Light في 18 أغسطس 2010 في 23:03

مدونتي: سرعة الضوء

#318 أغسطس 2010 في 23:07

السلام عليكم ...

حل لابأس به أخي و معذور بسبب الصيام لذلك لن نطالب بتشغيل المخ بأقصى طاقته :P , و لكن لا تنسى أن تستفيد من نقطة حصر الأعداد المدخلة بالأعداد الموجبة فقط. عموماً, هناك حلول أفضل, و لا تحتاج إلى ترتيب الأعداد لكشف العدد الضائع.

تحياتي...

Follow me on bitbucket

#418 أغسطس 2010 في 23:53

صدق لم أستطع أن أتمالك نفسي عندما رأيت السؤال قلت أسجل دخول سريع وأحله وأهرب من المنتدى , بعض المشيغلات هذه الأيام :ph34r:

#include "stdafx.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{


	int x[] = {16,12,13,11,15,17,18,19,20};
	int ELEMETNS_NUM = 9;
	int sum=0,min=x[5],max=x[0];
	for (int q=0;q<ELEMETNS_NUM;q++)
	{
		if(x[q]<min) min= x[q];
		sum+=x[q];
		if(x[q]>max) max= x[q];
	}

	cout << "Missing num is :" << (max*(max+1)/2 - min*(min-1)/2) - sum << endl;


	return 0;
}

مايفعله الكود هو الإستفادة من مجموع الأعداد المتتالية بالعلاقة

$2$

ويوجد المجموع الحقيقي لهذه الأعداد وناتج الطرح هو الرقم المفقود :P

قد توجد طرق أسهل لكن لازال ليلي طويل ولاأريد أن أحرق بقية السعرات الحرارية الموجودة :lol:

تم تعديل هذه المشاركة بواسطة HGB في 19 أغسطس 2010 في 05:46 — السبب: تم تعديل المعادلة بإضافة القوس المفقود - تن&a

NOTHING IS IMPOSSIBLE

#519 أغسطس 2010 في 00:00

لا أدري كيف يمكن تحسين الخوارزمية بحصر الأعداد بالموجبة فقط ... أنا بالأساس لا أفحص كون العدد موجباً أم لا !

هل تقصد بهذا استخدام متحولات unsigned مثلاً ؟!

على كل حال هذه خوارزمية لا تحتاج إلى ترتيب العناصر، أفضل من الأولى ... لكن ليس كثيراً :D

public class LostNum {

    public static void main(String[] args) {
        int input[] = {3, 5, 4, 8, 9, 2, 1, 6, 0};
        System.out.println("The Lost number is: " + findLostNum2(input));
    }

    static int findLostNum2(int input[]) {
        int max = 0;
        for (int i = 0; i < input.length; i++) {
            if (input > max) {
                max = input;
            }
            boolean b = false;
            for (int j = 0; j < input.length; j++) {
                if (input[j] == input + 1) {
                    b = true;
                    break;
                }
            }
            if(!b && input != max){
                return input + 1;
            }
        }
        return -1; // Not found !
    }
}

مدونتي: سرعة الضوء

#619 أغسطس 2010 في 00:09

يا شباب هيثم ممنوع من الاشتراك في الألغاز القادمة :lol:

الله ينور عليك يا هيثم, أتيت بالحل المثالي. بالمناسبة لا أعتقد أنه يوجد خوارزمية أفضل :)

تحياتي...

Follow me on bitbucket

#719 أغسطس 2010 في 00:21

هيثم ؟

اتفقنا أنك في اجازة ..

كانت لي محاولة ، بالرغم من أني لا أفهم ماذا تعني المتوالية الحسابية بالظبط :( ..

#include<iostream>
using namespace std;

void minAndMax(int *arr,int len,int  &minInt ,int &maxInt,int &totalWithLost)
{
	for(int i=0;i<len ; i++){
		if(minInt>arr)
			minInt = arr;
		if(maxInt<arr)
			maxInt = arr;
		totalWithLost += arr;
	}
}
int main(){
	int arr[] ={99, 96, 91, 95, 93, 98, 89, 97, 92, 94, 100};
	const int ARRAY_SIZE = 11;
	int totalWithoutLost = 0,totalWithLost = 0;
	int minInt = 100000;
	int maxInt = -100000;

	minAndMax(arr,ARRAY_SIZE, minInt , maxInt,totalWithLost);

	// I think , there is an equeation to do this without for loop .
	for(int i=minInt;i<=maxInt;i++){
		totalWithoutLost +=i;
	}



	cout << totalWithoutLost - totalWithLost ;

	getchar();
	return 0;
}

طبقتها على بعض امثلة خالد وهي تعمل : ) .

الفكرة التي خطرت ببالي ،

- جمع الأرقام مع العدد الضائع ( بمعرفة أصغر عدد و أكبر عدد ثم جمع ما بينهم مع الحدين ) .

- جمع المدخلات التي في المصفوفة .

- الفارق بينهم هو العدد الصائع :D .

إضافة :

اسم المتغيرين totalWithoutLost و totalWithLost مبهمين ؟ يبدو أنهما العكس ، لكني أخطأت .. المهم النتيجة .

تطبيق طمأنينة ، نسخة بيتا على أندرويد

عبدالله الشمّري - Al-Shammari

CodingAlone.com

twitter @abshammeri

abshammeri AT gmail.com

github : abshammeri

#819 أغسطس 2010 في 01:12

اقتباس
يا شباب هيثم ممنوع من الاشتراك في الألغاز القادمة

my bad :lol:

اقتباس
هيثم ؟
اتقفنا أنك في اجازة

نعم لازلت وباقي إسبوع :wub:

الشمري بالضبط ماقلته لجمع القيمة الحقيقة توجد علاقة رياضية مشهورة وهي $2$ هذه ستقوم بإيجاد مجموع الأعداد فورا إذا كانت مبتدئة من الصفر .. يعني 0,1,2,3,4,5...n

أم لو إبتدأت برقم متقدم مثلا .. 13,14,15,16...n , فما هو المجموع ؟ سيكون المجموع بالتأكيد مجموع الأعداد من 1 حتى n مطروح منها مجموع الأعداد من 1 حتى 13 :)

هل تصدق أيضا أن هذه العلاقة $2$ أوجدها أحد علماء الرياضيات أظنه "أويلر" هم كثر بالمناسبة هؤلاء الأويلرات , أظنهم أقارب أو شيء كهذا , لدرجة أنه في الجامعة أحد الطلاب علق أن يبدو أنه سيظهر صابون أويلر قريبا في الأسواق من شدة ماتدخلو في كل شيء في الرياضات :lol:

المهم المصيبة أن أويلر , أو أيا كان العالم ألف النظرية في إحدى المراحل الإبتدائية من المدرسة :S , فكان الأستاذ كما عرفت القصة يريد أن يلهي الطالب ويرتاح من وجع رأسهم فقال لهم أوجدو مجموع الأعداد من 1 إلى 100 , وتركهم :lol: , فقام هذا الكابتن بحلها في دقائق ..

الفكرة كالتالي .. تخيل الأعداد :

1,2,3,4,5,5,6,7,8,9,10

لاحظ مجموع 10+1 = 11 , و 9+2 = 11 أيضا و 8+3 = 11 أيضا , 7+4 = 11 أيضا , 6+5 =11 , إذن كم المجموع ؟

سيكون 11*5 = 55 ..

طيب كم مجموع الأعداد من 1 إلى 100 ؟ ستكون 100+1 مضروبة في 50 صح ؟ لأن كل رقمين سيعطو 101 , بالتالي 50 مرة 101 = 5050 , ومن هنا جائت العلاقة ..

n/2 مضروبة في n+1

50 مضروبة في 101

تم تعديل هذه المشاركة بواسطة HGB في 19 أغسطس 2010 في 05:47 — السبب: تم تعديل المعادلة بإضافة القوس المفقود - تن&a

NOTHING IS IMPOSSIBLE

#919 أغسطس 2010 في 01:42

أعتقد أنه Gauss يا هيثم, و القصة صحيحة بالفعل, اكتشف النظرية عندما كان في الابتدائية :wacko:

بالمناسبة Euler أجن و أجن من Gauss و Euler's Identity تسمى أجمل Identity في الرياضيات كلها حسب رأي الكثيرين, لأنها تجمع جميع الأعداد المميزة!

$9e9a547076c6820b95e439dd1a5d6a32.png$

الصفر و الواحد و i و pi و e ... ماذا بقي :lol:, السؤال هو كيف وصل لهذه المتطابقة أصلاً!

تم تعديل هذه المشاركة بواسطة Khaled.Alshaya في 19 أغسطس 2010 في 01:43

Follow me on bitbucket

#1019 أغسطس 2010 في 01:43

إضافة أخييرة وسأذهب :D

أيضا لمجموع الأعداد المربعة ..

$mimetex.cgi?1^2,2^2,3^2,4^2,5^2... n^2$

نستخدم العلاقة :

$6$

في الجامعة في أول عام أذكر الدكتور أعطانا "مخمنة" :blink: قال لنا خمنو مجموع :

$mimetex.cgi?1^3,2^3,3^3,4^3,.... n^3$

فذهبت للمنزل ورفعت ضغطي وطبعا كانت مجرد تخمين وليس إثبات رياضي أبدا , وأنما شيء أقرب للتجربة والخطأ ووجدت أن العلاقة كانت :

$2^2$

نفس علاقة المتتابعة العادية لكن كلها تربيع للبسط والمقام .. أظن أنها أثبتت في منهج المادة التي كنا ندرسها Arithmetic .. لكن لم أكن مهتما :happy:

فياريت شباب الرياضيات يثبتو لنا العلاقتين لو أمكن ونكون من الممنوننين : )

NOTHING IS IMPOSSIBLE

#1119 أغسطس 2010 في 03:51

HGB كتب:
مايفعله الكود هو الإستفادة من مجموع الأعداد المتتالية بالعلاقة
$2$

هذا القانون خطأ :) ، الصحيح هو

$2$

وطبعا فرق كبير بين الإثنين وعلى فكرة انت استخدمت القانون الصحيح داخل الكود ، ولكنك كتبته خطأ خارجه :)

Khaled.Alshaya كتب:
الله ينور عليك يا هيثم, أتيت بالحل المثالي. بالمناسبة لا أعتقد أنه يوجد خوارزمية أفضل :)

ليس مثاليا بالقدر الكافى :lol: ، لكن الفكرة عامة مضبوطه ، لكن يمكن تحسين الأداء قليلا.

حل أخونا الشمرى ايضا جميل وهو يدور فى نفس فكرة الأخ هيثم.

عامة السؤال معتمد على حالة خاصة جدا من المتسلسلات الحسابية ، وهى المتسلسلات الحسابية الموجبة والتى يزيد كل حد فيها بمقدار واحد. ولكن ماذا نفعل لو كانت المتسلسلات بها حدود سالبة؟ او كان الفرق بين كل حد والذى يليه هو عدد مختلف عن الواحد.

مثال: المتسلسلة الحسابية

1, 4, 7, 10, 13, 16, 19, 22

وتم نزع احد الحدود من وسط المتسلسلة ، فكيف يمكنك التعرف عليه؟

بالله التوفيق ،،،

أشهد أن لا إله إلا الله وأشهد أن محمدا رسول الله

مـــوقـــعـــى

#1219 أغسطس 2010 في 04:28

السلام عليكم ورحمة الله

حتى يكون الكلام عمليا اكثر منه نظريا. فإن الفكرة (المطروحة حاليا) تتمثل فى ايجاد مجموع الأعداد المعطاه ، ثم إيجاد مجموع المتسلسلة الحسابية الأصليه اعتمادا على قانون المتسلسلات وكذلك حساب اصغر واكبر عناصرها. وبما أن المتسلسلة الحسابية الحالية -حسب المعطيات- فيها كل حد يزيد عن الحد الذى يسبقه بمقدار الواحد. إذا لا توجد ضرورة لحساب قيمة أكبر عدد فى الأعداد المعطاه ، يكفى حساب أصغر عدد فقط ، وذلك لأن القانون العام لجمع المتسلسلات الحسابية هو $2$

حيث n عدد الحدود و a اصغر حد بالمتسلسلة و d مقدار الزياده فى كل حد عن الحد الذى يسبقه.

وفى مسألتنا هذه

n هو عدد الحدود المعطاه +1 (لان هناك حد محذوف ونريد حسابه)

d=1

فيبقى لنا حساب اصغر عدد فقط a

وهكذا تكون توفرت لدينا جميع المعلومات المطلوبه.

ويبقى السؤال هو:

ماذا نفعل لو كانت المتسلسلات بها حدود سالبة؟ او كان الفرق بين كل حد والذى يليه هو عدد مختلف عن الواحد؟

المفروض الأن الإجابة تكون سهلة :)

بالله التوفيق ،،،

أشهد أن لا إله إلا الله وأشهد أن محمدا رسول الله

مـــوقـــعـــى

#1319 أغسطس 2010 في 04:58

اقتباس
ماذا نفعل لو كانت المتسلسلات بها حدود سالبة؟ او كان الفرق بين كل حد والذى يليه هو عدد مختلف عن الواحد؟

تجمع كل الأعداد في المتتالية بالنظير الجمعي لأكبر عنصر سالب

ثم تطبق قانون المتتاليات العام؟؟

#1419 أغسطس 2010 في 05:35

خذ الكود لكل الحالات .. سالبة , و/أو الأعداد بزيادة q ..

ولن يحدث أي شيء حتى لو كانت هناك قيم سالبة في الكود .. :) , كل مافعلته أنني حسنت الكود في جزئية المعادلة فقط لتكون عامة , ولم أضع السالب في الحسبان والنتائج دقيقة , والسبب ببساطة أن القيم السالبة التي تخشى منها ستنقص بالتوزاي أيضا في قيمة sum العادية , وستنقص أيضا بالمثل في المجموع بالمعادلة , بالتالي وكأننا لم نفعل شيئا ولا نزال نبحث عن الرقم السالب أو الموجب الذي سيكمل المجموع لاأكثر .

#include "stdafx.h"
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{

	int x[] = {-7,1,5,9,13,17,21,25,29,33};

	int ELEMETNS_NUM = 10;
	int sum=0,min=x[0],max=x[0];
	for (int q=0;q<ELEMETNS_NUM;q++)
	{
		if(x[q]<min) min= x[q];
		sum+=x[q];
		if(x[q]>max) max= x[q];
	}

	int inc = (max - min)/ELEMETNS_NUM;
	cout << "Missing num is :" << (ELEMETNS_NUM+1)*(max+min)/2 - sum << endl;

	return 0;
}

أيضا لانحتاج لقانون متتاليات عام يكفي أن تجمع أكبر رقم + أصغر رقم وتضرب المجموع في نصف عدد ال items لديك وإنتهينا :)

NOTHING IS IMPOSSIBLE

#1519 أغسطس 2010 في 07:10

HGB كتب:
خذ الكود لكل الحالات .. سالبة , و/أو الأعداد بزيادة q ..
ولن يحدث أي شيء حتى لو كانت هناك قيم سالبة في الكود .. :) , كل مافعلته أنني حسنت الكود في جزئية المعادلة فقط لتكون عامة , ولم أضع السالب في الحسبان والنتائج دقيقة , والسبب ببساطة أن القيم السالبة التي تخشى منها ستنقص بالتوزاي أيضا في قيمة sum العادية , وستنقص أيضا بالمثل في المجموع بالمعادلة , بالتالي وكأننا لم نفعل شيئا ولا نزال نبحث عن الرقم السالب أو الموجب الذي سيكمل المجموع لاأكثر .

اعلم ياباشا امكانياتك كويس :) بالضبط أخى هيثم. يمكن فقط عمل تعديل بسيط فى الكود لتوفير بعض الحسابات التى لا داعى لها

	int sum=x[0],min=x[0],max=x[0];
	for (int q=1;q<ELEMETNS_NUM;q++)

ما فائدة هذا السطر؟

        int inc = (max - min)/ELEMETNS_NUM;

HGB كتب:
أيضا لانحتاج لقانون متتاليات عام يكفي أن تجمع أكبر رقم + أصغر رقم وتضرب المجموع في نصف عدد ال items لديك وإنتهينا :)

لو كنت درست متسلسلات ، كنت عرفت ان ماكتبته حضرتك هو القانون العام لجمع المتسلسلات :) وهو

LaTeX

$mimetex.cgi?\sum_{i=1}^n a_i=\frac{n}{2}$

حيث $mimetex.cgi?a_1$ الحد الأول (الأصغر) و $mimetex.cgi?a_n$ هو الحد الأخير (الأكبر)

وبما أن الحد الأخير يتم حسابه بالشكل التالى

LaTeX

$mimetex.cgi?a_n=a_1+(n-1)d$

حيث d هو مقدار الزيادة فى كل حد عن الحد الذى يسبقه. وبالتالى يمكن إعادة كتابة قانون الجمع ليكون

LaTeX

$mimetex.cgi?\sum_{i=1}^n a_i=\frac{n}{2}$

وبالتالى القانونين هم اصلا واحد ، ولكن تختار المناسب منهم حسب المتوفر لديك من معلومات عن المتسلسلة.

فلو كان المتوفر عدد الحدود والحد الاول والحد الأخير ، كان القانون التالى أنسب

LaTeX

$mimetex.cgi?\sum_{i=1}^n a_i=\frac{n}{2}$

ولو كان متوفر عدد الحدود والحد الأول ومقدار الزيادة فى الحدود ، كان القانون التالى انسب

LaTeX

$mimetex.cgi?\sum_{i=1}^n a_i=\frac{n}{2}$

وتحديدا فى مسألتنا هنا ، لو كان التعامل مع الحالة الخاصة من المتسلسلات الحسابية التى تزيد بمقدار واحد ، فالأنسب هو استخدام

LaTeX

$mimetex.cgi?\sum_{i=1}^n a_i=\frac{n}{2}$

وبكده يمكن توفير كمية الحسابات التى تستخدم لحساب الحد الأخير. أما فى الحالة العامة للمتسلسلات الحسابية ، سيكون الأسهل هو قانون الحد الأول والحد الأخير

هذا والله اعلى واعلم ،،،

تم تعديل هذه المشاركة بواسطة عماد حمدي احمد في 19 أغسطس 2010 في 07:13

أشهد أن لا إله إلا الله وأشهد أن محمدا رسول الله

مـــوقـــعـــى

#1619 أغسطس 2010 في 16:46

أستاذ عماد جزاكم الله خيرا على التوضيح ... :)

هذا السطر

 int inc = (max - min)/ELEMETNS_NUM;

وجد سهوا , ونسيت حذفه من نظرية قبل هذه ..

لكن قانون المتسلسلات العام يبدو أنني نسيته وعدنا إليه بطريق آخر .. :lol:

NOTHING IS IMPOSSIBLE

#1719 أغسطس 2010 في 17:43

HGB كتب:
أستاذ عماد جزاكم الله خيرا على التوضيح ... :)

بارك الله فيك أخى هيثم وبارك لك :)

بعض التركيز منك فى الرياضيات ، ولن استبعد ان نسمع عن انجازات مذهلة باسمك :)

أشهد أن لا إله إلا الله وأشهد أن محمدا رسول الله

مـــوقـــعـــى

#1819 أغسطس 2010 في 21:00

فاتتني فرصة المشاركة هذه المرة :)

HGB كتب:
إضافة أخييرة وسأذهب :D
أيضا لمجموع الأعداد المربعة ..
$mimetex.cgi?1^2,2^2,3^2,4^2,5^2... n^2$
نستخدم العلاقة :
$6$
...
فياريت شباب الرياضيات يثبتو لنا العلاقتين لو أمكن ونكون من الممنوننين : )

يمكن البرهنة عليها بالترجع (الإستقراء): نتحقق أولا من أنها صحيحة من أجل 1، ونفترض بعدها أنها صحيحة من أجل n، ونبين أنها صحيحة من أجل n+1. إلا أن السؤال سيبقى: كيف وجدنا تلك العلاقة أصلا؟

لنر أولا البرهان بالترجع، ثم لنحاول إيجاد العلاقة بشكل مختلف.

البرهان بالترجع:

لنبين أن $mimetex.cgi?1^2 + 2^2 + ... + n^2 = \fra$ لكل n من $mimetex.cgi?\mathbb{N}^*$

التحقق:

من أجل n=1 لدينا:

$mimetex.cgi?\frac{1 \times (1+1) \times$

المتساوية صحيحة من أجل n=1

يمكن أيضا التحقق من أجل n=2، لكن ليس ضروريا.

الإفتراض:

نفترض أن العلاقة $mimetex.cgi?1^2 + 2^2 + ... + n^2 = \fra$ صحيحة من أجل n.

هذا يعني أنها صحيحة من أجل جميع الأعداد الأصغر من n أيضا.

لنبين أن المتساوية صحيحة من أجل n+1:

أي أن $mimetex.cgi?1^2 + 2^2 + ... + n^2 + (n+1$

لدينا $mimetex.cgi?1^2 + 2^2 + ... + n^2 = \fra$

نضيف ²(n+1) إلى طرفي المتساوية:

$mimetex.cgi?1^2 + 2^2 + ... + n^2 + (n+1$

ونبسط:

$mimetex.cgi?1^2 + 2^2 + ... + (n+1)^2= ($

المتساوية صحيحة أيضا من أجل n+1.

وبالتالي: لكل n من $mimetex.cgi?\mathbb{N}^*$ لدينا

$mimetex.cgi?1^2 + 2^2 + ... + n^2 = \fra$

طريقة أخرى:

نفترض أننا لا نعرف صيغة المجموع $mimetex.cgi?1^2 + 2^2 + ... + n^2$

(البرهان من السنة أولى ثانوي)

لنبحث عن حدودية P من الدرجة الثالثة تحقق:

$mimetex.cgi?P(1)-P(2)=1^2$

$mimetex.cgi?P(2)-P(3)=2^2$

$mimetex.cgi?P(3)-P(4)=3^2$

$mimetex.cgi?\dots$

$mimetex.cgi?P(n)-P(n+1)=n^2$

والسبب؟

عند جمع المتساويات طرفا طرفا، سنحصل على:

$mimetex.cgi?1^2 + 2^2 + ... + n^2=P(1)-P$

أي أن صيغة المجموع تساوي فرق صورتي 1 و n+1 بالحدودية P.

الحدودية P من الدرجة 3، إذن توجد أعداد حقيقية a و b و c و d بحيث:

$mimetex.cgi?P(x)=ax^3 + bx^2 + cx + d$

لنحسب صورة x+1

$mimetex.cgi?P(x+1)=a(x+1)^3 + b(x+1)^2 +$

بعد النشر والتبسيط، نجد أن:

$mimetex.cgi?P(x+1)=ax^3 + (3a+b)x^2 + (3$

ولدينا $mimetex.cgi?P(x)-P(x+1)=x^2$

نبسط الطرف الأيسر، فنجد:

$mimetex.cgi?-3ax^2-(3a+2b)x-(a+b+c)=x^2$

تكون حدوديتان متساويتان إذا وفقط إذا كانت معاملات حدودهما التي من نفس الدرجة متساوية مثنى مثنى:

$mimetex.cgi?-3a=1 \hspace{20} 3a+2b=0 \h$

أي أن:

$mimetex.cgi?a=\frac{-1}{3} \hspace{20} b$

لا توجد شروط على d، للتبسيط سنأخذ d=0

إذن:

$mimetex.cgi?\red \fbox{P(x)=\frac{-1}{3}$

نحسب صورتي 1 و n+1

$mimetex.cgi?P(1)=\frac{-1}{3} + \frac{1}$

$mimetex.cgi?-P(n+1)=\frac{-1}{3} (n+1)^3$

$mimetex.cgi?=(n+1)\frac{2(n+1)^2-3(n+1)+$

$mimetex.cgi?=\frac{(n+1)(2n^2+n)}{6}$

$mimetex.cgi?=\frac{n(n+1)(2n+1)}{6}$

لدينا

$mimetex.cgi?1^2 + 2^2 + ... + n^2=P(1)-P$

ومنه

$mimetex.cgi?1^2 + 2^2 + ... + n^2=\frac{$

وهي الصيغة المطلوبة.

يمكن البرهنة على الصيغ الأخرى بنفس الطريقتين.

هذا إن لم أخطئ.

أعتذر أخي خالد على خروجي عن الموضوع :)

خالص التقدير،،

MPSI/MP* - CPR Tanger

#1919 أغسطس 2010 في 22:15

بارك الله فيك أخى راغب ، ابداعاتك ليست بجديدة علينا :)

عامة طريقتك الأخيرة التى اوجدت بها صيغة مجموع المتسلسلة ، تسمى -فى مصر- بــ "طريقة الفروق لحساب مجموع المتسلسلات".

بارك الله فيك وبارك لك ،،،

أشهد أن لا إله إلا الله وأشهد أن محمدا رسول الله

مـــوقـــعـــى

#2020 أغسطس 2010 في 00:20

@ عماد : شكرا على رفع المعنويات :D

@ راغب : جزاكم الله خيرا .. إثبات جميل وواضح ..

لكن لماذا إثبات التكعيب مختفي وقليل جدا ؟ يبدو أنه معقد قليلا ...

NOTHING IS IMPOSSIBLE

#2120 أغسطس 2010 في 04:25

اقتباس
لنبحث عن حدودية P من الدرجة الثالثة تحقق:<BR>

حل رائع , لكن هل من الممكن أن تشرح لي لماذا من الدرجة 3 ؟ <BR>فيوجد طريقة في حالة كان يوجد فقط An=A(n+1) نبحث عن P من الدرجة الثانية مثلا ً<BR><BR>و شكرا ً لك

تم تعديل هذه المشاركة بواسطة aohammed في 20 أغسطس 2010 في 04:27

#2220 أغسطس 2010 في 16:41

ماذا فاتني هنـا..؟ :)

يبدو أن كل الأساتذة قد اجتمعوا لأمرٍ جلل.. :P

بالنسبة للمتساوية $mimetex.cgi?\sum\limits_{k = 1}^n {{k^3}$ فيمكن إثباتها بدورها بالاستنتاج الرياضياتي كما ذكر راغب. و قد أثبتها Knuth بهذه الطريقة في كتابه The Art of Computer Programming, Vol. 1.

المدهش في الأمر أن هذه المتساوية أثارت شغف الرياضياتيين منذ الحضارات القديمة و حتى الآن؛ وجدت عند المصريين القدماء و الهنود و الصينيين و الفرس و الإغريق و العرب، و مازالت تقدم لها براهين جديدة حتى اليوم. ذُكرت المتساوية في آثار نيكوماكوس الروماني المولود بجرش في الأردن، و أريابهاتا و سوماراجي الهنديين و أبي بكر الكرخي الفارسي، و أبي الصقر القبيسي العربي. يقول ستروكر Roel Stroeker عن هذه المتساوية: (إن أي دارس لنظرية الأعداد ليعجب أشد العجب من هذه الحقيقة المذهلة)..

و إذا سألنا عن اثبات مباشر Direct proof لهذه المتساوية بعيداً عن الاستنتاج الرياضياتي لنجيب عن سؤال راغب: (كيف وجدنا هذه العلاقة أصلاً؟).. نجد أننا بحاجة للعودة للرياضيات القديمة، و للخيال الثري الناتج عن ربط الأعداد بالأشكال الهندسية..

هناك مبرهنة قديمة لنيكوماكوس الرماني تسمى باسمه Nicomachus's theorem، و هي مذكورة في القليل جداً من مؤلفات نظرية الأعداد، و تعتمد في صياغتها على ما يسمى بالأعداد الشكلية Figurate numbers. إذا ما استخدمنا هذه المبرهنة ببساطة كما نستخدم مبرهنة فيثاغورث، فإن المتساوية المذكورة تثبت في سطر واحد..

نظرية نيكوماكوس Nicomachus's Theorem

مجموع أول n من المكعبات هو مربع العدد المثلثي النوني.

The sum of the first n cubes is the square of the n-th triangular number

و الأعداد المثلثية هي صنفٌ من الأعداد الشكلية يوضحها الشكل التالي:

و يكون:

$mimetex.cgi?{T_1} = 1,$

$mimetex.cgi?{T_2} = 1 + 2 = 3,$

$mimetex.cgi?{T_3} = 1 + 2 + 3 = 6.$

و العدد المثلثي النوني هو:

$mimetex.cgi?{T_n} = 1 + 2 + 3 + ... + (n$

و العدد المثلثي النوني هو مشابه (جمعي) لعملية المضروب (باستبدال الجمع بالضرب):

$mimetex.cgi?n! = n \times (n - 1)...2 \t$

و العلاقات التالية للأعداد المثلثية سهلة الإثبات:

$mimetex.cgi?T_n^2 + T_{n - 1}^2 = {T_{{n$

$mimetex.cgi?3{T_n} + {T_{n - 1}} = {T_{2$

$mimetex.cgi?3{T_n} + {T_{n + 1}} = {T_{2$

$mimetex.cgi?T_{n + 1}^2 - T_n^2 = {(n +$

و بدءاً بالأخيرة يمكننا إثبات مبرهنة نيكوماكوس و من ثم إثبات المتساوية موضع الاهتمام كالتالي:

$mimetex.cgi?{T_{{n^3}}} = {({T_n})^2}$

$mimetex.cgi? \Rightarrow \sum\limits_{k$

لقد فضلت هنا أن أعرض صورة عامة قد تكون فائدتها أكبر، عوضاً عن تفصيل فنيات برهان مفرد بذاته.. فالمتساوية و الأعداد الشكلية التي تمثل تأصيلاً لها مرتبطة بموضوعات هامة و ثرية في الرياضيات عامة و نظرية الأعداد خاصة..

هذه أيضاً مبرهنات أخرى تعزف على نفس المقام الموسيقي لمبرهنة نيكوماكوس و الأعداد الشكلية:

$mimetex.cgi?{T_{a + b}} = {T_a} + {T_b}$

$mimetex.cgi?{T_{ab}} = {T_a}{T_b} + {T_{$

$mimetex.cgi?\sum\limits_{k = 1}^{2n - 1}$

$mimetex.cgi?\sum\limits_{k = 1}^n {{{(2k$

$mimetex.cgi?Nu{m^ + } = \Delta + \Delta$

و الأخيرة هي صياغة معتادة لمبرهنة لجاوس Gauss و نصها: (كل عدد صحيح موجب يمكن تمثيله بمجموع ثلاثة مثلثات (أعداد مثلثية) على الأكثر)..

و مرفق بعض المصادر التي تحوي تفصيلاً للعديد من البراهين للمتساوية موضع النظر.. و هي شيقة و بسيطة..

The Sum of Cubes, An Extension of Archimedes' Sum of Squares.pdf

Summing cubes by counting rectangles.pdf

On the sum of consecutive cubes being a perfect square.pdf

Two quick combinatorial proofs.pdf

تحيــاتي..،

المرفقات

تم تعديل هذه المشاركة بواسطة YDVIPER في 20 أغسطس 2010 في 16:42

[bg=#000000]

La filosofia e scritta in questo grandissimo libro che continuamente ci sta aperto innanzi a gli occhi (io dico l’universo), ma non si pu o intender se prima non s’impara a intender la lingua e conoscere i caratteri ne’ quali e scritto. Egli e scritto in lingua matematica e i caratteri sono triangoli, cerchi, ed altre figure geometriche senza i quali mezi e impossibile a intenderne umanamente parola; senza questi e un aggirarsi vanamente per un oscuro laberinto.

Galileo

لقد كُتبت الفلسفة في هذا الكتاب العظيم الذي يوجد دائماً أمام أعيننا (و أعني به الكون)، و لكن لا يمكن لأحدٍ أن يفهمه ما لم يتعلم في البدء حروفَ اللغة التي كُتب بها. لقد كُتب بلغة الرياضيات، و الحروف هي مثلثاتٌ و دوائر و أشكالٌ هندسية أخرى؛ بدون هذه اللغة يكون من المستحيل على البشر أن يفهموا و لو كلمة، بدون هذه اللغة نُمسي كمن يتخبطُ بلا هدى في متاهةٍ مظلمة.

جاليليو

[/bg]

Yasser