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

Khaled Alshaya · 18 Aug 2010

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

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

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

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

تحياتي :)

تم تعديل 18 Aug 2010 بواسطه Khaled.Alshaya

Speed_Of_Light · 18 Aug 2010

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

لست متأكداً أنها الخوارزمية الأفضل ... لكنها جيدة بما فيه الكفاية ... كما أنها تعمل ! :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[i] > input[j]) {
                    int tmp = input[j];
                    input[j] = input[i];
                    input[i] = tmp;
                }
            }
        }

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

تم تعديل 18 Aug 2010 بواسطه Speed_Of_Light

Khaled Alshaya · 18 Aug 2010

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

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

تحياتي...

HGB · 18 Aug 2010

صدق لم أستطع أن أتمالك نفسي عندما رأيت السؤال قلت أسجل دخول سريع وأحله وأهرب من المنتدى , بعض المشيغلات هذه الأيام :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:

تم تعديل 19 Aug 2010 بواسطه HGB
تم تعديل المعادلة بإضافة القوس المفقود - تن&a

Speed_Of_Light · 18 Aug 2010

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

هل تقصد بهذا استخدام متحولات 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[i] > max) {
                max = input[i];
            }
            boolean b = false;
            for (int j = 0; j < input.length; j++) {
                if (input[j] == input[i] + 1) {
                    b = true;
                    break;
                }
            }
            if(!b && input[i] != max){
                return input[i] + 1;
            }
        }
        return -1; // Not found !
    }
}

Khaled Alshaya · 18 Aug 2010

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

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

تحياتي...

abshammeri · 18 Aug 2010

هيثم ؟

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

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


#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[i])
			minInt = arr[i];
		if(maxInt<arr[i])
			maxInt = arr[i];
		totalWithLost += arr[i];
	}
}
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 مبهمين ؟ يبدو أنهما العكس ، لكني أخطأت .. المهم النتيجة .

HGB · 18 Aug 2010

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

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

:)

تم تعديل 19 Aug 2010 بواسطه HGB
تم تعديل المعادلة بإضافة القوس المفقود - تن&a

Khaled Alshaya · 18 Aug 2010

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

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

$9e9a547076c6820b95e439dd1a5d6a32.png$

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

تم تعديل 18 Aug 2010 بواسطه Khaled.Alshaya

HGB · 18 Aug 2010

إضافة أخييرة وسأذهب :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:

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

عماد حمدي احمد · 19 Aug 2010

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

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

$2$

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

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

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

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

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

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

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

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

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

عماد حمدي احمد · 19 Aug 2010

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

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

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

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

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

d=1

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

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

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

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

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

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

abohammed · 19 Aug 2010

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

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

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

HGB · 19 Aug 2010

خذ الكود لكل الحالات .. سالبة , و/أو الأعداد بزيادة 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 لديك وإنتهينا :)

عماد حمدي احمد · 19 Aug 2010

خذ الكود لكل الحالات .. سالبة , و/أو الأعداد بزيادة 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;

أيضا لانحتاج لقانون متتاليات عام يكفي أن تجمع أكبر رقم + أصغر رقم وتضرب المجموع في نصف عدد ال 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 Aug 2010 بواسطه عماد حمدي احمد

HGB · 19 Aug 2010

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

هذا السطر


 int inc = (max - min)/ELEMETNS_NUM;

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

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

عماد حمدي احمد · 19 Aug 2010

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

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

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

caballero · 19 Aug 2010

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

إضافة أخييرة وسأذهب :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{$

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

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

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

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

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

عماد حمدي احمد · 19 Aug 2010

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

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

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

HGB · 19 Aug 2010

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

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

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

abohammed · 20 Aug 2010

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

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

YDVIPER · 20 Aug 2010

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

يبدو أن كل الأساتذة قد اجتمعوا لأمرٍ جلل.. :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

تحيــاتي..،

تم تعديل 20 Aug 2010 بواسطه YDVIPER

HGB · 20 Aug 2010

ياسر ماشاء الله لم تترك شيئا , أشبعت فضولي بشكل كامل وبالتحديد لخلفية التاريخية للمبرهنة ...

جزاكم الله خيرا .

caballero · 20 Aug 2010

جزاكم الله خيرا.

كعادته، الأخ ياسر دائما يضرب بمطرقة من حديد :)

@aohammed:

يمكن أن تفكر في ذلك المجموع على أنه تكامل، لذلك لجأنا إلى حساب دالة أصلية لـ n² والتي ستكون حدودية من الدرجة الثالثة.

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

بالإضافة إلى ما ذكره الأخ ياسر، هناك طريقة أخرى تعتمد على فكرة حساب دالة أصلية. لنر مثلا كيف يمكن حساب المجموع $mimetex.cgi?1^3 + 2^3 + \dots + n^3$

ننطلق من التكامل $mimetex.cgi?\int_k^{k+1} x^3 dx$

$mimetex.cgi?\int_k^{k+1} x^3 dx = \frac{$

ثم نحسب المجموع من 0 إلى n، مما يسمح لنا بالحصول على:

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

$mimetex.cgi?\Bigsum_{k=0}^{n} k^3 = \fra$

وبما أننا نعرف $mimetex.cgi?\Bigsum_{k=0}^{n} k^2$ و $mimetex.cgi?\Bigsum_{k=0}^{n} k$ ، فلا يبقى سوى التبسيط:

$mimetex.cgi?\Bigsum_{k=0}^{n} k^3 = \fra$

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

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

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

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

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

أي أن: $mimetex.cgi?1^3 + 2^3 + \dots + n^3 = \f$

يمكن حساب المجاميع السابقة بنفس الطريقة.

Sauf erreur

HGB · 20 Aug 2010

إثبات التكامل جميل وبسيط فعلا .. لم أفكر فيه .. بالتالي كل المجاميع كهذه يمكن إثباتها بالتكامل كما وضحت ياراغب ..

يحبذ وضع لافتة , عليك أن تتوخى الحذر عند الدخول لهذا القسم :D

YDVIPER · 21 Aug 2010

بارك الله فيكم إخواني..

راغب.. جميل الإثبات بتكامل دالة أصلية أيها الفارس.. :)

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

سؤال

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

26 إجابة على هذا السؤال .

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة

شارك الرد من خلال المواقع ادناه

شارك هذا الرد

رابط المشاركة