Side 1 av 1
Olympiadeoppgave(12th grade)
Lagt inn: 15/04-2007 00:58
av Magnus
La n* være tallet man får etter å ha tatt et heltall n, og flyttet tallets siste siffer til første posisjon (f.eks , 7491* = 1749). Bestem en n>0 slik at 7n* = 2n .
Lagt inn: 15/04-2007 13:57
av sEirik
Dette ser ut som et problem som skal kunne løses ganske greit med brute-force
Litt kode i C#:
Kode: Velg alt
public static void Main()
{
int i,j;
i = 0;
while(true)
{
i++;
j = Stjerne(i);
int VS = 7*j;
int HS = 2*i;
if (VS == HS)
{
Console.WriteLine(i+" er en løsning.");
}
}
}
public static int Stjerne(int n)
{
string s = n.ToString();
char sistesiffer = s[s.Length-1];
string s2 = s.Remove(s.Length-1);
string s3 = sistesiffer + s2;
return int.Parse(s3);
}
Gir, etter ett sekund:
"538461 er en løsning."
Det kan sjekkes:
538461* = 153846
7*153846 = 1076922
2*538461 = 1076922
Venter i spenning på flere løsninger eller en litt penere, matematisk metode
Lagt inn: 15/04-2007 14:05
av Magnus
Den der måtte jo komme..
Lagt inn: 15/04-2007 14:10
av sEirik
Kunne man dratt en sånn på olympiaden da? Eller får man ikke bruke PC?
Lagt inn: 15/04-2007 14:12
av Magnus
Samme hjelpemidler som i abelkonkurransen ; )
Lagt inn: 15/04-2007 16:36
av Solar Plexsus
Denne oppgaven kan løses ved regning. La [tex]m[/tex] være antall siffer i [tex]n[/tex]. La [tex]x[/tex] være tallet (som har m-1 sifre) som blir igjen når vi fjerner siste siffer [tex]y[/tex] i [tex]n[/tex]. Da er
(1) n = 10x + y
og
(2) n[sup]*[/sup] = 10[sup]m-1[/sup]y + x.
Likningen 7n[sup]*[/sup] = 2n gir
[tex](3) \;\;\; y \;=\; \frac{13x}{7 \cdot 10^{m-1} \:-\: 2}[/tex]
I.o.m. at x har m-1 sifre, må x < 10[sup]m-1[/sup]. Dermed får vi vha. (3) at
[tex]y \;<\; \frac{13 \cdot 10^{m-1} }{7 \cdot 10^{m-1} \:-\: 2} \; < \; 2[/tex]
Herav følger at y = 1, som innsatt i (3) gir
[tex](4) \;\;\; x \;=\; \frac{7 \cdot 10^{m-1} \:-\: 2}{13}[/tex]
Ergo må [tex]7 \cdot 10^{m-1} \:-\: 2[/tex] være delelig med 13. Herav følger at m er delelig med 6, dvs. at m = 6k for et naturlig tall k. Dette i kombinasjon med (3) medfører at
[tex]n \;=\; 10x \:+\: y \;=\; 10 \, \cdot \, \frac{7 \cdot 10^{6k-1} \:-\: 2}{13} \:+\: 1 \;=\; \frac{7}{13} \, (10^{6k} \:-\: 1) \:=\: n(k).[/tex]
Altså blir n(1) = 538461. Et interessant poeng her er at n(2) = 538461538461, altså 538461 skrevet to ganger etter hverandre. Dette gjelder generelt: n(k) blir tallet bestående at 538461 skrevet k ganger etter hverandre. Forklaringen på dette fenomenet ligger i identiteten
[tex]\overbrace{n(1)n(1) \cdots n(1)}^{\mbox{k ganger}} \;=\; 538461 (10^{6(k-1)} \:+\: 10^{6(k-2)} \:+\: \ldots \:+\: 1) \;=\; \frac{7}{13}(10^6 \:-\: 1) \, \cdot \, \frac{10^{6k} \:-\: 1}{10^6 \:-\: 1} \;=\; n(k).[/tex]
Lagt inn: 15/04-2007 16:47
av Magnus
Veldig fint arbeid. Spesielt den generelle formelen.
Lagt inn: 15/04-2007 16:55
av Magnus
Legger med en oppgave til. Disse oppgavene ble gitt av en post.doc på NTNU ved et matteseminar forrige uke. Problemene er offisielt fra en kanadisk olympiade.
Anta [tex]E \subseteq \{1,2,3,\ldots,30\}[/tex] består av 8 elementer. Vis at det eksisterer ikke-tomme disjunkte delmengder av E som er slik at summen av elementene er like.
Lagt inn: 15/04-2007 21:55
av sEirik
Solar Plexsus skrev:Ergo må [tex]7 \cdot 10^{m-1} \:-\: 2[/tex] være delelig med 13. Herav følger at m er delelig med 6
hvorfor det?
Lagt inn: 15/04-2007 23:12
av Magnus
Hvorfor den må være delelig på 13 eller m være delelig med 6 ?
Lagt inn: 16/04-2007 01:23
av daofeishi
sEirik skrev:Solar Plexsus skrev:Ergo må [tex]7 \cdot 10^{m-1} \:-\: 2[/tex] være delelig med 13. Herav følger at m er delelig med 6
hvorfor det?
Vi har at [tex]7 \cdot 10^{m-1} \equiv 2 \ \pmod {13}[/tex]
2 er invers til 7 modulo 13
[tex]10^{m-1} \equiv 2 \cdot 2 \pmod {13}[/tex]
Fra faktum at 13 er prim, og multiplikasjon modulo 13 derfor former en gruppe, at [tex]10^5 \equiv 4 \pmod{13}[/tex] og [tex]10^6 \equiv 1 \pmod{13}[/tex], følger:
[tex]10^{m-1} \equiv 4 \equiv 10^{5 + 6k} \pmod{13}[/tex]
[tex]m-1 = 5 + 6k \\ m =6(k+1)[/tex]
Og dermed ser vi at m må være delelig med 6.
Lagt inn: 16/04-2007 01:55
av daofeishi
Magnus skrev:Legger med en oppgave til. Disse oppgavene ble gitt av en post.doc på NTNU ved et matteseminar forrige uke. Problemene er offisielt fra en kanadisk olympiade.
Anta [tex]E \subseteq \{1,2,3,\ldots,30\}[/tex] består av 8 elementer. Vis at det eksisterer ikke-tomme disjunkte delmengder av E som er slik at summen av elementene er like.
Enten har jeg oversett noe vitalt, eller så kan vi løse denne med nokså elementær "pigeonhole"-ing.
Størst mulig sum av en delmengde av E er 23 + 24 + ... + 30 = 212. Minst mulig er 0. (Summen av elementene i nullsettet.)
Dette betyr at det finnes maksimalt 212 + 1 = 213 ulike summer delmengdene kan ta.
Antall distinkte delmengder av E er 2^8 = 256.
Siden det finnes 256 delmengder, men kun 213 ulike summer, betyr dette at det må finnes minst 2 delmengder av E med samme sum. {Pigonhole principle.} Kall disse to delmengdene A og B.
Dersom A og B er disjunkte, er vi ferdige. Dersom A og B ikke er disjunkte, fjern deres felles elementer. Vi står nå igjen med to disjunkte delmengder med samme sum. At vi telte distinke delmengder betyr at A og B var ikke-tomme, og av umuligheten av to elementer med samme verdi, følger at A og B har 2 eller flere elementer. Vi har dermed bevist eksistens av delmengdene etter de gitte kriteriene.
Forresten, finnes det et godt norsk begrep for "pigeonhole principle"?
Lagt inn: 16/04-2007 02:27
av Janhaa
Kan ikke bidra med noe her. Men var innom pigeonhole begrepet i diskret matematikk for noen år sida. Tror det rett og slett ble oversatt med duebox prinsippet (problemet ).