Трёхзначные числа

[wpoms.]

Сколько существует трехзначных чисел (то есть, чисел, больших 99 и меньших 1000), у которых средняя цифра больше двух других? У скольких из этих чисел все три цифры разные?

@темы: Комбинаторика

Comments

[Adjirranirr]

Полный перебор (без оптимизации кода, VS C++ 2012, /Ox);

#include <fstream>

void main () {
	std::ofstream A ("out.txt");
	int j = 0, k = 0;
	for (int i = 100; i < 1000; i++) {
		char a, b, c;
		a = i % 10;
		b = (i / 10) % 10;
		c = i / 100;
		if (b > a && b > c) {
//			A << i << std::endl;
			j++;
			if (a != c) k++;
		}		
	}
	A << j << " " << k << std::endl;
	A.close ();
}

Вывод:

240 204

Теперь по решению =)
Зафиксируем среднюю цифру, `b`. Очевидно, `b >= 2`; количество цифр, меньших `b`, которые могут стоять в старшем разряде числа, есть `b - 1` (нуля быть не может), которые могут стоять в младшем разряде — `b`. Таким образом, всего чисел, у которых средняя цифра больше первой и последней, `\sum_{b = 2}^{9} (b - 1)*b = 240`.
Из них чисел вида `\bar(aba)` всего `\sum_{b = 2}^{9} (b - 1) = 36`, а чисел, у которых все цифры различны, `240 - 36 = 204`.