• 0
Khaled Alshaya

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

سؤال

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

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

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
3

شارك هذا الرد


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

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

  • 0

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

لست متأكداً أنها الخوارزمية الأفضل ... لكنها جيدة بما فيه الكفاية ... كما أنها تعمل ! :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 !
}
}

تم تعديل بواسطه Speed_Of_Light
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

تحياتي...

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

هل تقصد بهذا استخدام متحولات 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 !
}
}

2

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

تحياتي...

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هيثم ؟

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

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


#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 مبهمين ؟ يبدو أنهما العكس ، لكني أخطأت .. المهم النتيجة .

2

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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
تم تعديل المعادلة بإضافة القوس المفقود - تن&a
5

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

9e9a547076c6820b95e439dd1a5d6a32.png

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

تم تعديل بواسطه Khaled.Alshaya
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

2

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

2

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

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

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

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

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

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

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

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

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

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

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

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

d=1

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

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

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

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

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

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

2

شارك هذا الرد


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

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

2

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

تم تعديل بواسطه عماد حمدي احمد
3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

هذا السطر


int inc = (max - min)/ELEMETNS_NUM;

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

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

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

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

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

3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

0

شارك هذا الرد


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

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

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

post-65407-085360700 1282311051_thumb.jp

و يكون:

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
9

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

@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

3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

0

شارك هذا الرد


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

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .