Делим отрезок

[rGlory]

Извиняюсь, если было. Имеем отрезок целой длинны N. Случайным образом делим его два раза на три отрезка опять же целой (ненулевой) длинны. Какова вероятность, что из полученных отрезков можно построить треугольник?

[Иоп]

0.25?
Кажется, такая задачка уже была.

[venco]

Если считать только невырожденные треугольники и N>2:

Для чётных N p=0.25-0.75/(N-1)
Для нечётных p=0.25+0.75/(N-2)

[rGlory]

Если считать только невырожденные треугольники и N>2:

А откуда это следует (я имею в виду ответ)?

[Иоп]

[quote="venco"][/quote]
Т.е. ответ зависит от значения N? Тогда, в чем измеряется N?

[venco]

Если считать только невырожденные треугольники и N>2:

А откуда это следует (я имею в виду ответ)?

Я просто поделил число разбиений, дающих треугольник (3 неравенства), на число всех разбиений.

[venco]

Т.е. ответ зависит от значения N? Тогда, в чем измеряется N?

В единицах.
Вы условие прочитали?

[rGlory]

Я просто поделил число разбиений, дающих треугольник (3 неравенства), на число всех разбиений.

Ладно, буду думать - спасибо.
А вот это было?
Найти наибольшее число, у которого все десятичные цифры разные и не равны нулю, при этом само число делится на каждую из цифр, его составляющих.

PS Методом грубой силы я его нашел, конечно. Но как это аналитически решается?

[venco]

Найти наибольшее число, у которого все десятичные цифры разные и не равны нулю, при этом само число делится на каждую из цифр, его составляющих.

PS Методом грубой силы я его нашел, конечно. Но как это аналитически решается?

Сначала выбираем набор цифр, коротые в принципе способны дать такое число.
Далее перебираем перестановки этих цифр по убыванию величины с одним простым необходимым условием.
Тринадцатая перестановка даёт искомое число:

9867312

[rGlory]

Сначала выбираем набор цифр, коротые в принципе способны дать такое число.

Может я совсем отупел, но по какому критерию?

[venco]

Сначала выбираем набор цифр, коротые в принципе способны дать такое число.

Может я совсем отупел, но по какому критерию?

2 и 5 одновременно быть не могут, т.к. тогда число должно делиться на 10 и появится цифра 0.
Дальше, надо убрать ещё одну цифру, чтобы признак делимости на 9 и/или 3 выполнялся. Таким образом максимальное число цифр - 7. Варианты:
без 5 и 4: 9876321
без 2 и 7: 9854631
Первый вариант более перспективный, т.к. больше.
Дальше перебираем перестановки, т.к. чтобы делилось на 8 и 7, делимость на остальные цифры приложится.
Для делимости на 8 надо, как минимум, чтобы последняя цифра была чётной.
Поехали:
9876312
9876132
9873612
9873216
9873162
9873126
9872316
9872136
9871632
9871362
9871326
9871236
9867312 бинго
Это число получилось больше максимального из второго набора цифр, значит это и есть ответ.

[rGlory]

2 и 5 одновременно быть не могут, т.к. тогда число должно делиться на 10 и появится цифра 0.
...
9867312 бинго
Это число получилось больше максимального из второго набора цифр, значит это и есть ответ.

Вот мой метод грубой силы:

Code: Select all

#include <iostream>
#include <vector>

int main()
{
   std::vector< int > numbers;
   for( int i = 1; i < 10; ++i ) numbers.push_back( i );

   int max = 0;
   do {
      for( int k = 1; k < 10; ++k ) {
         int result = 0;
         for( int i = 0, pow = 1; i < k; ++i, pow *= 10 ) result += pow * numbers[ i ];
         bool div = true;
         for( int i = 0; i < k && div; ++i )
            if( result % numbers[ i ] ) div = false;
         if( !div ) continue;
         if( result > max ) max = result;
      }
   } while( std::next_permutation( numbers.begin(), numbers.end() ) );

   std::cout << "result is: " << max << std::endl;


   return 0;
}

result is: 9867312

[Иоп]

Вот мой метод грубой силы:

Ждем аналогичного метода для отрезков с треугольниками
Venco хоть и объяснил, но я недостаточно умный, чтобы понять - мне "на пальцах" нужно

[venco]

2 и 5 одновременно быть не могут, т.к. тогда число должно делиться на 10 и появится цифра 0.

Я только сейчас сообразил, что есть только один подходящий набор из 7 цифр.
Если 5 оставить, то убрать придётся не только 2 но и остальные чётные цифры.

[venco]

Ждем аналогичного метода для отрезков с треугольниками
Venco хоть и объяснил, но я недостаточно умный, чтобы понять - мне "на пальцах" нужно

Мне реально лениво переписывать все неравенства тругольника и суммирования подходящих вариантов. Там всё довольно просто, но длинно.
При суммировании получаются треугольные числа.
Скажу лишь для начала, что число всех разбиений отрезка N на 3 = (N-1)(N-2)/2.

[rGlory]

Вот мой метод грубой силы:

Ждем аналогичного метода для отрезков с треугольниками
Venco хоть и объяснил, но я недостаточно умный, чтобы понять - мне "на пальцах" нужно

Без проблем:

Code: Select all

#include <iostream>

void calc( int N )
{
   int able = 0;
   int total = 0;
   for( int i = 1; i < N - 1; ++i )
      for( int j = i + 1; j < N; ++j ) {
         const int a = i;
         const int b = j - i;
         const int c = N - j;
         if( a + b > c && a + c > b && b + c > a )
            ++able;
         ++total;
      }

   double p = 0.25 + 0.75 / ( N % 2 ? N - 2 : 1 - N );

   std::cout << "For N: " << N << " probability " << able << "/" << total << " or "
             << double( able ) / total << " where venco's p == " << p << std::endl;
}

int main()
{
   for( int N = 3; N < 21; ++N )
      calc( N );

   return 0;
}

результат:

Code: Select all

For N: 3 probability 1/1 or 1 where venco's p == 1
For N: 4 probability 0/3 or 0 where venco's p == 0
For N: 5 probability 3/6 or 0.5 where venco's p == 0.5
For N: 6 probability 1/10 or 0.1 where venco's p == 0.1
For N: 7 probability 6/15 or 0.4 where venco's p == 0.4
For N: 8 probability 3/21 or 0.142857 where venco's p == 0.142857
For N: 9 probability 10/28 or 0.357143 where venco's p == 0.357143
For N: 10 probability 6/36 or 0.166667 where venco's p == 0.166667
For N: 11 probability 15/45 or 0.333333 where venco's p == 0.333333
For N: 12 probability 10/55 or 0.181818 where venco's p == 0.181818
For N: 13 probability 21/66 or 0.318182 where venco's p == 0.318182
For N: 14 probability 15/78 or 0.192308 where venco's p == 0.192308
For N: 15 probability 28/91 or 0.307692 where venco's p == 0.307692
For N: 16 probability 21/105 or 0.2 where venco's p == 0.2
For N: 17 probability 36/120 or 0.3 where venco's p == 0.3
For N: 18 probability 28/136 or 0.205882 where venco's p == 0.205882
For N: 19 probability 45/153 or 0.294118 where venco's p == 0.294118
For N: 20 probability 36/171 or 0.210526 where venco's p == 0.210526

[Иоп]

Вы условие прочитали?

Ура! До меня дошло!

(сорри, я немножко "тугодум" в последнее время )

А если деление произвольное (т.е. не на целые отрезки), то вероятность 0.25 или я ошибся?

[Иоп]

Без проблем:

Спасибо!

[venco]

А если деление произвольное (т.е. не на целые отрезки), то вероятность 0.25 или я ошибся?

Да. Это предел при N->Inf.

[rGlory]

А если деление произвольное (т.е. не на целые отрезки), то вероятность 0.25 или я ошибся?

Ну да, тогда получается, что N стремится к бесконечности, а вероятность соотвественно к 0.25 (А бесконечность она четная или нет?)

[rGlory]

Ну тогда еще одну, напоследок:

Code: Select all

X X X X
      X
  X X X
      X
X X X X

По горизонтали и вертикали (сверху вниз) записаны числа, не начинающиеся с нуля и являющиеся квадратами. Сколько существует возможных решений?

[venco]

(А бесконечность она четная или нет?)

А это неважно, предел одинаковый.

[venco]

Ну тогда еще одну, напоследок:

Ну это только перебором:

Code: Select all

#! /usr/bin/perl
for $i (10..31) {
  ++$c3[$i*$i%10];
}
for $i (32..99) {
  ++$c4[$i*$i%10];
}
for $i (100..316) {
  $s=$i*$i;
  $c += $c4[int($s/10000)]*$c3[int($s/100)%10]*$c4[$s%10];
}
print "Total: $c\n";

Total: 45097

[rGlory]

Ну это только перебором:

Странно, наверное я неправильно перевел. По идее должна решаться аналитически. Извиняюсь.

[rvd]

...
Поехали:
9876312
9876132
9873612
9873216
9873162
9873126
9872316
...

какое же ето аналитическое решение? просто более грамотный перебор из меньшего числа вариантов. да и логика решения - компутерная, посему программируется на раз