Threaded Mode | Linear Mode

***drdebcol*** · 12-30-2009, 10:08 PM

This is an mathematical task. You need to find all 6-digit numbers with odd number of odd digits.
That sounds hard. Well basically it is easy to write program for that than to find mathematical solution. I wrote a program and i had a solution, but i had to think a bot to understand it with using combinatorics, better said Enumerative combinatorics. More about combinatorics (part of math) you can find here :
http://en.wikipedia.org/wiki/Combinatorics
You can count all those manually. But it can take years because you have :
999 999 - 100 000 = 899 999 six-digit numbers.
And solution for this problem is 450 000. As you can see half + 1 elements are those which satisfy condition (899 999 div 2 + 1) .
That is a huge job, but it took me 3 minutes to solve it in programming language and 20 minutes to solve it mathematically.

Mathematical solution
6-digit number can have 1,3,5 odd digits as we can see, because 1,3,5 are odd numbers. And the task is to find odd number of odd digits.
First we need to see that those are variations with repetition n^k.
In this explanation i will use symbols :
E - Even digit (0,2,4,6,8)
O - Odd digit (1,3,5,7,9)
So we will divide this problem on 3 smaller problems :
CASE OF ONE ODD DIGIT
CASE OF FIVE ODD DIGITS
CASE OF THREE ODD DIGITS
As you can see i put five in front of three because it is a bit more complex.

CASE OF ONE ODD DIGIT
In this case we have to find all the cases when we have one odd digit and 5 even digits. When even digits are on the beginning we need to exclude cases when 0 is on the beginning because that is no more an 6-digit number.
You can see everything on the picture :
[Image: 29697_1odd.jpg]

In case of Odd number on the beginning, it is easy you just need to multiply all the cases.

CASE OF FIVE ODD DIGITS
This case is almost the same as the last one.
Cases of this :
E O O O O O - > ONLY CASE OF EVEN ON THE BEGINNING

O E O O O O
O O E O O O
O O O E O O THESE ARE 5 CASES WHEN ODD IS ON THE BEGINNING
O O O O E O
O O O O O E
As you can see on the picture :
[Image: 29698_5odd.jpg]

So this problem is also easy.

CASE OF THREE ODD DIGITS
Here is harder to do it, and this part we the biggest problem for me.
You need to find cases when there is even on the beginning and odd on the beginning. You have everything on the picture :
[Image: 29699_3odd.jpg]

So that is the greatest problem here and now let's add all those together and get a solution.

SOLUTION
[Image: 29700_solutionoddnumberofodddigits.jpg]

[Image: 29700_solutionoddnumberofodddigits.jpg]

As i said solution is 450 000.

Programming solution
This is easy to make. I solved it in TPW and in C++.
You can do it with 6 for loops too, but that is long to type and this is faster.
So here is the solution in TPW :

Code:

program odd_number_of_odd_digits;

uses wincrt;

var

i,br:longint;

function is_it(k:longint):boolean;

var

  br:longint;

begin

  br:=0;

  repeat

    begin

      if k mod 2 = 1 then

        br:=br+1;

        k:=k div 10;

    end;

  until (k=0);

  if br mod 2 = 1 then

    is_it:=true

  else

    is_it:=false;

end;

begin

br:=0;

 for i:=100000 to 999999 do

   begin

     if is_it(i) then

       br:=br+1;

   end;

   writeln(br);

end.

And in C++ :

Code:

# include <iostream>

# include <cstdio>

using namespace std;

bool is_it(int k)

{

 int br;

  br=0;

  while (k>0)

   {

      if (k % 2 == 1)

        br++;

      k=k/10;

  }

  if (br % 2 == 1) 

    return true;

  else

    return false;

}

int main()

{

    int i,br;

    br=0;

   for (i=100000;i<=999999;i++)

     if (is_it(i))

       br++; 

    cout<<br<<endl;

    system("pause");

}