|
На мен ми стана интересна тая задача и затова нахвърлях една програмка. За неголеми M и N може с груба сила да се намери максималният възможен брой турове T(M, N). Резултатите са дадени в долната таблица:
M= 2 3 4 5 6 7 8 9 10 11 12 13
N=
2 3 5 7 9 11 13 15 17 19 21 23 25
3 1 4 4 7 >=7
4 1 1 5 >=5
5 1 1 1 6 >=5
6 1 1 1 1
За по-големи M и N методът "с рогите" естествено сдава багажа.
Това, което се забелязва, е следното:
- Изглежда, че T(M,2)=2*M-1 за всяко M;
- При N>M T(M,N)=1 (това се доказва лесно);
- Може би T(M,M)=M+1 за всяко M.
Смятането на T(10,5) е май безнадеждно по "рогатия" метод, за разумно време успях да измайсторя само 5 тура:
{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25},{26,27,28,29,30},{31,32,33,34,35},{36,37,38,39,40},{41,42,43,44,45},{46,47,48,49,50}
{1,6,11,16,21},{2,7,12,17,22},{3,8,13,18,23},{4,9,14,19,24},{5,10,15,20,25},{26,31,36,41,46},{27,32,37,42,47},{28,33,38,43,48},{29,34,39,44,49},{30,35,40,45,50}
{1,7,13,19,25},{2,6,14,18,26},{3,9,11,17,27},{4,8,12,16,28},{5,21,29,31,37},{10,22,30,41,47},{15,32,38,44,50},{20,33,36,45,49},{23,34,40,42,48},{24,35,39,43,46}
{1,8,14,17,29},{2,9,13,16,30},{3,6,12,19,31},{4,7,11,18,32},{5,22,26,33,39},{10,21,27,45,48},{15,23,36,43,47},{20,28,40,44,46},{24,34,37,41,50},{25,35,38,42,49}
{1,9,12,18,33},{2,8,11,19,34},{3,7,14,16,35},{4,6,13,17,36},{5,23,27,38,41},{10,24,32,40,49},{15,21,30,42,46},{20,22,29,43,50},{25,26,37,44,48},{28,31,39,45,47}
Витае ми някаква мисъл, че винаги е възможно да се постигне въпросната горна граница без 1...
При N>M очевидно не може да се достигне. Иначе - не знам...Редактирано от Orнeдишaщ на 11.02.10 18:18.
|
Re: Комбинаторика [re: Reptile]
